第 15 回 状態遷移図

本日の内容

• 15-1. atoi
• 15-2. 状態遷移図
• 15-3. 計算の状態遷移図の最適化
• 15-4. 優先度のある演算処理

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

15-1. atoi

今回は計算をコンピュータで行うためのアルゴリズムを取り上げます。 はじめに、文字列を読んで数字の列を数に変換するプログラムを考えます。 実際、この処理はしばしば使われるため、システムで提供しています。 stdlib.h にある atoi 関数や、stdio.h にある sprintf 関数などです。 しかし、ここではこれらの関数を用いずに、どのようにすれば関数を実現でき るかを考えましょう。

文字が 2 3 4 とならんでいた時、これが二百三十四であるということをどう やったら計算できるのでしょうか? まず、以前大文字小文字の変換で説明したように、 C 言語では文字同士の足 し算引き算ができ、また、文字は順番にならんでいることを仮定できることを 思い出しましょう。 すると、文字 '2' と文字 '0' は 2 だけ離れているので、 '2'-'0' は 2 に なります。同じように数字を表すそれぞれの文字に対して、 '0' を引くこと で、その数字単独で表す数が得られます。

次に数字の列をどのようにしたら一つの数として計算できるかを考えましょう。 各数字は桁を表しています。 2 3 4 だと、 2 が百の位、 3 が十の位、 4 が一の位です。 従って、百が 2 個、十が 3 個、一が 1 個を合わせると二百三十四が得られ ることになります。つまり、 2 × 100 ＋ 3 × 10 ＋ 4 × 1 を計算すれば よいことになります。 ところが、数は常に 3 桁ではありません。文字列を左から見ていく時、どの ように位取りをすれば良いでしょうか?

ここで帰納的に考えてみましょう。 もし、数字の列を左から計算できたとします。そして、次の文字を読み込んだ ことを考えます。 例として、 "2 3 4" に対し、 "2 3" を読み込んで正しく二十三と計算した後、 '4' を読み込んだことを考えます。 この時、どのようにすれば 二百三十四を計算できるでしょうか? 筆算で考えると、二十三を左に移動して、四を足せば良いことが分かります。

このためには既に分かっている値に 10 をかけてから、読んだ文字の示す値を 足せば良いことが分かります。 プログラムにすると次のようになります。

int atoi(char *p){
  int res=0;
  while(*p!='\0'){
    res *= 10;
    res += *p - '0';
    p++;
  }
  return res;
}

このようにすると文字列中の数字の列の表す数を計算することができます。

演習15-1

上の関数をテストするプログラムを書き、実際に文字列を数字に変換できるこ とを確かめなさい。

15-2. 状態遷移図

次に、1+1= のような「『数1』『演算子』『数2』=」 という形の式を計算す ることを考えましょう。 プログラムとしては、数1を読み込み、演算子を読み、数2を読み込み、=を読 んだら計算をするという手順を取ります。 このプログラムの手順は、入力の文字の種類に応じて変化します。 数を読み始めたら『数1を読み込み』という手順に入り、数以外(演算子)を読 んだら『演算子を読み』の手順に移り、再び数を読み込んだら『数2を読み込 み』の手順に移ります。 このように入力にしたがってプログラムの状態が変化する様子を整理する図に 状態遷移図があります。

丸が各状態を表し、矢印が状態の移り変わりを示します。 何もないところから入ってくる矢印がついている丸は開始状態で、二重丸は終 了状態です。 矢印の上に入力される文字を記入します。 1 番の状態では数字を読み込み数を計算します。 2 番の状態で演算子を記憶し、 3 番の状態で再び数字を読み込み数を計算し ます。最後の状態で値を計算します。

この状態遷移図をプログラムにするには、基本的には if 文と goto 文を使え ば済みますが、現在のプログラミングスタイルには適合しません。 ここでは enum 宣言と while 文と switch 文を使う手法を説明します。

enum 宣言

有限個の値を取る変数を使いたい場合に、その値を列挙した値だけの型を定義 できます。このような型を列挙型と言います。C 言語では enum 宣言で列挙型を作ることができます。 enum 宣言は次のように使います。

enum threestate {first, second, third};
enum threestate state;
state=first;
if(state==second){
  ...
}

enum も struct 同様に typedef が使用できます。typedef を使うと次のよう に書けます。

typedef enum {first, second, third} threestate;
threestate state;
state=first;
if(state==second){
  ...
}

switch 文

switch 文は if()else if()else if() ... という構文を簡略化したものです。 但し、比較には整数値、文字、列挙型の値しか使えません。構文は次のように なります。

switch(変数){
case 値1: 文1-1;
          文1-2;
          break;
case 値2: case 値3:
          文2-1;
          break;
default: 文3-1;
         文3-2;
}

変数が case で示される値に一致するとそこに書かれている文を 次々と実行します。 case は複数重ねられますので、次の case が来てもそこで文の実行は終らず、 次々と文を実行します。 どの case にも適合しなかった場合、defalutの後の文を実行しま す。 文の実行を止めるには break 文を使います。break 文を使うと switch 文の外に実行が移ります。 break 文は switch 文だけでなく while, for 文などで使うことができます。

状態遷移図の実現

switch 文と enum を利用して上記の状態遷移図をプログラムにしたものを示 します。 状態を enum で定義し、 while 文の中に状態の変数に対する switch 文を入 れます。 そして各 case で処理を実行します。

#include <stdio.h>
typedef enum {NUM1, OP, NUM2, END, ERROR} STATE;
int isnum(int c){
  return (c>='0')&&(c<='9');
}
int isop(int c){
  return (c=='+')||(c=='-')||(c=='*')||(c=='/');
}

int main(void){
  int c;
  STATE s=NUM1;
  int num1=0;
  int num2=0;
  int result=0;
  char op;
  while((c=getchar())!=EOF){
    switch(s){
    case NUM1:
      if(isnum(c)){
	s=NUM1;
      }else if(isop(c)){
#ifdef DEBUG
	printf("%d\n",num1);
#endif
	s=OP;
      }else{
	s=ERROR;
      }
      break;
    case OP:
      s=NUM2;
      break;
    case NUM2:
      if(isnum(c)){
	s=NUM2;
      }else if(c=='='){
	s=END;
#ifdef DEBUG
	printf("%d\n",num2);
#endif
      }else{
	s=ERROR;
      }
      break;
    }
    switch(s){
    case NUM1:
      num1 *= 10;
      num1 += c -'0';
      break;
    case OP:
      op=c;
      break;
    case NUM2:
      num2 *= 10;
      num2 += c -'0';
      break;
    case END:
      switch(op){
      case '+':
	result=num1+num2;
	break;
      case '-':
	result=num1-num2;
	break;
      case '*':
	result=num1*num2;
	break;
      case '/':
	result=num1/num2;
	break;
      }
      break;
    }
    if(s==END){
      printf("%d\n",result);
      break;
    }else if(s==ERROR){
      printf("ERROR\n");
      break;
    }
  }
  return s==END?0:1;
}

演習15-2

このプログラムが正常に動くことを次の式を計算させて確かめなさい。

1. 23+45=
2. 45-12=
3. 12*34=
4. 39/13=

演習15-3

マイナスの値を扱うにはどうすれば良いですか?

1. マイナスの値を扱えるように状態遷移図を書き直しなさい。 (ヒント: 数を受け取る状態では、マイナスを受け取れる状態と、マイナスを 受け取れない状態(すでにマイナスを受け取ったか、数字が始まったか)の二つ の状態が必要になります)
2. その状態遷移図を元にプログラムを作りなさい。

演習15-4

連続した計算を行うにはどうすれば良いですか? 但し、ここでは安い電卓のように、完全に左から計算を行い、かけ算が優先さ れるなどのルールはないとします。

1. 連続した計算を行うように状態遷移図を書きなさい。 (ヒント: 最初の数を読み込んだ後、(『演算子』『数』)が = が出てくるまで繰返し になります)
2. プログラムを作りなさい。

参考

状態遷移図のより詳しい内容を知りたい時、「オートマトン」をキーワードと して探して下さい。 また、正規表現はオートマトンと密接な関係があります。 他に、コンパイラの字句解析にも詳しい解説があります。

15-3. 計算の状態遷移図の最適化

ここで作ったプログラムは数字を読み込む部分が二箇所あるなど冗長でした。 1+2+3= など連続して演算子と数字を読み込むことを許し、マイナス記号の処 理も可能なように書き直すと次のようになります。

結果と読み込み中の数をそれぞれ result と num で表すことにします。 そして、演算子を op で表すことにします。 通常、電卓のように次の演算子を読み込んだ時や = を読み込んだ時に、計算 を行ないます。 例えば、 1 + 2 - 3 = であれば、 1 + 2 まで読み込み、次の - を読み込んだ 時に 1 + 2 を計算し、次の = を読み込んだ時に、 3 - 3 を計算します。 つまり、演算子を読み込んだ時の処理は次のようになります。

1. いままでの計算結果 result と今読み込んだ数 num と記憶しておいた演 算子 op を使って、新しい result を計算します。
2. 今読み込んだ演算子を op に記憶します。

ここで問題なのは一番最初の数を読み込んで、次の演算子を読み込んだ時です。 この時、新しい result を計算するのに op には何も入ってません。 そこで、この場合は今読んだ数 num をそのまま result に入れることにしま す。

#include <stdio.h>
typedef enum {NUM, OP, END, ERROR} STATE;
int result=0,num,sign;
int op=' ';
void calc(void){
  switch(op){
  case ' ':
    result = num*sign;
    break;
  case '+':
    result += num*sign;
    break;
  case '-':
    result -= num*sign;
    break;
  case '*':
    result *= num*sign;
    break;
  case '/':
    result /= num*sign;
    break;
  }
}
int isnum(int c){
  return (c>='0')&&(c<='9');
}
int isop(int c){
  return (c=='+')||(c=='-')||(c=='*')||(c=='/');
}

int main(void){
  int c;
  STATE s=OP;
  while((c=getchar())!=EOF){
    switch(s){
    case OP:
      if(isnum(c)){
	num=c-'0';
	sign=1;
	s=NUM;
      }else if(c=='-'){
	num=0;
	sign=-1;
	s=NUM;
      }else{
	s=ERROR;
      }
      break;
    case NUM:
      if(isnum(c)){
	num*=10;
	num+=c-'0';
	s=NUM;
      }else if(isop(c)){
	calc();
	op=c;
	s=OP;
      }else if(c=='='){
	calc();
	printf("result = %d\n",result);
	return 0;
      }
      break;
    case ERROR:
      printf("ERROR\n");
      return 1;
    }
  }
  return 0;
}

15-4. 優先度のある演算処理

ここでは通常の数式をどのように計算するかを考えます。 問題を簡単にするため、足し算とかけ算だけからなる式を考えます。 かけ算は足し算より優先されるので、足し算の後にかけ算が来た場合はかけ算 が優先されます。 つまり注目している演算子が足し算だった時、次がかけ算の場合があるので足 し算をすぐに実行できません。 数式を左から見ていった時、どのように計算すればいいか整理するため、次の 表を作りました。

6 の例に注目すると、計算途中で二種類の値(足し算の左辺、かけ算の左辺)を記憶し ておく必要があることがわかります。 この観点からもう一度表を作ると次のようになります。

前回までの計算の仕方では次の演算子を読んだ時、数字の終りを検出して、そ れまでの計算を行うというものでした。 ここで、1?2? まで読んだ状態と、1?2?3? まで読んだ状態を比較してみます。

この表から、 3 とその次の演算子を読んだ時にしなければならないことを導 きます。

このようにすると + と * の演算子を読み込んだ時は、それぞれしなければなら ない処理が違うことがわかります。

* を読み込んだ時

1. かけ算の左辺と読み込んだ値を処理する。かけ算の左辺の値がない場合はその まましまい、値があったらかける。
2. 足し算の左辺は変更しない。

+ を読み込んだ時

1. かけ算の左辺と読み込んだ値を処理する(その前の演算子が + の時、 かけ算の左辺の値がないとして、上のかけ算と同じ処理をする)。
2. そして、その結果を足し算の左辺へ加えて、
3. かけ算の値を初期化する。

このようにすれば優先順位がある数式も処理可能です。

#include <stdio.h>
typedef enum {NUM, OP, END, ERROR} STATE;
int result=0,mresult=0,num,sign;
int op=' ',mop=' ';
void calcmul(void){
  switch(mop){
  case ' ':
    mresult = num*sign;
    break;
  case '*':
    mresult *= num*sign;
    break;
  case '/':
    mresult /= num*sign;
    break;
  }
}
void calc(void){
  calcmul();
  switch(op){
  case ' ':
    result = mresult;
    break;
  case '+':
    result += mresult;
    break;
  case '-':
    result -= mresult;
    break;
  }
  mresult=0;
  mop=' ';
}
int isnum(int c){
  return (c>='0')&&(c<='9');
}
int main(void){
  int c;
  STATE s=OP;
  while((c=getc(stdin))!=EOF){
    switch(s){
    case OP:
      if(isnum(c)){
	num=c-'0';
	sign=1;
	s=NUM;
      }else if(c=='-'){
	num=0;
	sign=-1;
	s=NUM;
      }else{
	s=ERROR;
      }
      break;
    case NUM:
      if(isnum(c)){
	num*=10;
	num+=c-'0';
	s=NUM;
      }else if((c=='*')||(c=='/')){
	calcmul();
	mop=c;
	s=OP;
      }else if((c=='+')||(c=='-')){
	calc();
	op=c;
	s=OP;
      }else if(c=='='){
	calc();
	printf("result = %d\n",result);
	return 0;
      }else{
	s=ERROR;
      }
      break;
    case ERROR:
      printf("ERROR\n");
	return 1;
    }
  }
}

なお、この分析法は簡単ですが、C 言語のように 15 種類も演算の優先度があ るような場合は適応できません(表が膨大になり、。 そのような一般の演算子に関する解析は、構文解析の手法にある演算子 順位法を使います。 これに関してはコンパイラなどの本を参照して下さい。

中置記法でのカッコの取り扱い

では本来の中置記法での計算はどうやったら実現できるでしょうか? 中置記法を逆ポーランド記法に変換すればあとは上に示したスタックを使った 計算で値を求めることができます。 しかし、ここでは直接値を求めることを考えましょう。 カッコをどうやって処理すればよいかがポイントですが、次のように考えます。

• 開きカッコが来たら、演算を途中で止め記憶し、新しい計算ができるよう に準備する
• 閉じカッコが来たら、カッコの中を計算して値を求める。そして、記憶し ておいた演算を元に戻す。

これを前回作ったプログラムに追加するとカッコに対応することができます。 プログラムでは計算の結果は result に入り、演算子は op に入り、読み 込んだ値は num に入り、num の符号は sign に入ります。 この場合に、上の処理は次のように具体化できます。

• 数字を読み込む代わりに開きカッコを読み込んだら、num の値を計算する のを止めて result と op をスタックに push する。 新たな計算を始める意味で result=0, op=' ' とする。
• 数字を読み込んでいて閉じカッコを読み込んだら、そこまでの値を計算す る。 計算結果を num に入れ、スタックから result と op を pop する。

なお状態が一つ増えているのは閉じカッコが来た時、次に数字が来ることを許 さないからです。 入力される式で閉じカッコの直後に数字が来ないことがわかっていれば次のよ うに手抜きができます。

演習15-5

前述したプログラムにカッコの処理を付け足しなさい。

演習15-6

上記のプログラムに対してカッコの処理を加えて、完全な数式処理を実現しな さい