第 13 回状態遷移図

本日の内容

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

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

13-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;
}

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

演習13-1

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

13-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} STATE;
main(){
  char c;
  STATE s=NUM1;
  int num1=0;
  int num2=0;
  int result=0;
  char op;
  while((c=getchar())!=EOF){
    switch(s){
    case NUM1:
      if((c>='0')&&(c<='9')){
	s=NUM1;
      }else{
#ifdef DEBUG
	printf("%d\n",num1);
#endif
	s=OP;
      }
      break;
    case OP:
      s=NUM2;
      break;
    case NUM2:
      if((c>='0')&&(c<='9')){
	s=NUM2;
      }else if(c=='='){
	s=END;
#ifdef DEBUG
	printf("%d\n",num2);
#endif
      }
      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;
    }
  }
}

演習13-2

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

23+45=
45-12=
12*34=
39/13=

演習13-3

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

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

演習13-4

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

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

参考

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

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

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

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

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

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


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

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

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

	計算式の左側	計算して良い部分
1	1+2+3+4...	1+2+3
2	1+2+3*4...	1+2 と 3*4
3	1+2*3+4...	2*3を計算した後 1 との和を求める
4	1+234...	2*3 を計算した後 4 との積を求める
5	1*2+3+4...	1*2 を計算した後 3 との和を求める
6	12+34...	12 の計算と 34 の計算を別にしておく
7	123+4...	123
8	123*4...	123*4

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

	計算式の左側	足し算の左辺	かけ算の左辺
1	1+2+3+4...	1+2+3	4
2	1+2+3*4...	1+2	3*4
3	1+2*3+4...	1+2*3	4
4	1+234...	1	234
5	1*2+3+4...	1*2+3	4
6	12+34...	1*2	3*4
7	123+4...	123	4
8	123*4...	0	123*4

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

	計算式の左側	1?2? まで読んだ時		1?2?3? まで読んだ時
	計算式の左側	足し算の左辺	かけ算の左辺	足し算の左辺	かけ算の左辺
1	1+2+3+...	1+2	なし	1+2+3	なし
2	1+2+3*...	1+2	なし	1+2	3
3	1+2*3+...	1	2	1+2*3	なし
4	1+23...	1	2	1	2*3
5	1*2+3+...	1*2	なし	1*2+3	なし
6	12+3...	1*2	なし	1*2	3
7	123+...	なし	1*2	123	なし
8	123*...	なし	1*2	なし	123

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

	計算式の左側	1?2? まで読んだ時		1?2?3? まで読んだ時
	計算式の左側	足し算の左辺	かけ算の左辺	足し算の左辺への計算	かけ算の左辺への計算
1	1+2+3+...	1+2	なし	足し算の左辺へ 3 を足す	なし
2	1+2+3*...	1+2	なし	そのまま	3 を入れる
3	1+2*3+...	1	2	かけ算の左辺と3の積を求め、足し算の左辺と加える	消す
4	1+23...	1	2	そのまま	かけ算の左辺と3の積を求める
5	1*2+3+...	1*2	なし	足し算の左辺に 3 を足す	なし
6	12+3...	1*2	なし	そのまま	3 をしまう
7	123+...	なし	1*2	かけ算の左辺に 3 をかけ、足し算の左辺にする	消す
8	123*...	なし	1*2	なし	かけ算の左辺に 3 をかける

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

* を読み込んだ時

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

+ を読み込んだ時

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

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


#include <stdio.h>
typedef enum {NUM, OP, END} STATE;
int result=0,mresult=0,num,sign;
char op=' ',mop=' ';
void calcmul(){
  switch(mop){
  case ' ':
    mresult = num*sign;
    break;
  case '*':
    mresult *= num*sign;
    break;
  case '/':
    mresult /= num*sign;
    break;
  }
}
void calc(){
  calcmul();
  switch(op){
  case ' ':
    result = mresult;
    break;
  case '+':
    result += mresult;
    break;
  case '-':
    result -= mresult;
    break;
  }
  mresult=0;
  mop=' ';
}
main(){
  char c;
  STATE s=OP;
  while((c=getchar())!=EOF){
    switch(s){
    case OP:
      if((c>'0')&&(c<='9')){
	num=c-'0';
	sign=1;
	s=NUM;
      }else if(c=='-'){
	num=0;
	sign=-1;
	s=NUM;
      }
      break;
    case NUM:
      if((c>'0')&&(c<='9')){
	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;
      }
      break;
    }
  }
}

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

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

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

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

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

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

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

演習13-5

補足で作成したプログラムを利用して、カッコの処理を付け足しなさい。

演習13-6

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

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 13 回 状態遷移図