そろそろ再帰が、本当の意味で価値あるレベルの話をしようと思う。
数式というのがある。ここでは、四則演算を実際にやってみようと思う。
-(1-2*3)-(4-5)*(6*7-8)/9 みたいな括弧付で、優先順位も考えないといけない式を
ちゃんと計算してしまうCの関数を作ってみようと思う。
数式の定義を再帰的に書いて説明し、それに基づいてプログラムを書いてしまえば 単純に終るのであるが、そんな非教育的なことはここではしない。
まず最初に、１行を入力しては、それを文字列用に用意したchar型配列に 取り込むところだけを作ってみた。
int main( int argc, char **argv )
{
char buffer[1000]; /* 式入力バッファ */
for(;;) {
printf( "\nexpr:" );
if( fgets( buffer, sizeof(buffer), stdin ) == NULL )
break;
printf( "\tbuffer=%s", buffer );
}
}
expr1.c である。
main()もあって、ちゃんと動く形になっている。
$ expr expr:123+345 buffer=123+345 expr:1*2+3/4 buffer=1*2+3/4 $入力した通りの文字がbufferに入っていることが分かろう。
入力バッファに読み込むところはできたが、数式処理をするためには、 入力された文字列を、記号や数字に分解しなくてはならない。
トークンというのは、文字列として与えられた数式を、最小のまとまりの 単位に分けたものである。それをどのようにして利用するとかいろいろ考えて、 トークン関連の部分を作り上げるのだが、ここでは、
char buffer[1000]; /* 式入力バッファ */ char *bufferptr; /* 入力バッファポインタ */ char token[100]; /* トークン */という配列を用意し、与えられた文字列からトークンに分けることにする。 なお、元になる文字列用のバッファと、その文字列に対するポインタ(解釈開始位置)も 以上のようにグローバルに定義してしまった。
しかし、ここでは、与えられた文字列に対して、空白は読み飛ばすが、 それ以上の処理はしない、１文字を１トークンとみなす、まあ無茶苦茶無能な トークン取り出し関数 gettoken() を用意した。
char *gettoken( void )
{
char *tp = token;
*tp = '\0';
while( isblank(*bufferptr) )
++bufferptr;
if( (*bufferptr == '\n') || (*bufferptr == '\0') )
return NULL;
*tp++ = *bufferptr++;
*tp = '\0';
return bufferptr;
}
expr2.c である。
まだ、意味のあるような動作はしないが、一応入力した文字列をバラバラに扱える ことは分かると思う。
$ expr expr:12+34 token:1: token:2: token:+: token:3: token:4: expr: $12も34もそれぞれ2つのトークンとして処理されてしまっている。 数は、１つのまとまったものとして処理してくれないと困るであろう。 １文字単位では、トークンという概念を考える意味もないではないか。
というので、gettoken()に手を入れてみたら次のようになった。
char *gettoken( void )
{
char *tp = token;
*tp = '\0';
while( isblank(*bufferptr) )
++bufferptr;
if( (*bufferptr == '\n') || (*bufferptr == '\0') )
return NULL;
if( isdigit(*bufferptr) ) {
/* 数字なので、数字が続く限りtokenにコピー */
while( isdigit(*bufferptr) )
*tp++ = *bufferptr++;
} else {
/* 数字でないので１文字だけの記号と解釈 */
*tp++ = *bufferptr++;
}
*tp = '\0';
return bufferptr;
}
ソース全体は
expr3.c である。
まだ、意味のあるような動作はしないが、一応入力した文字列をバラバラに扱える ことは分かると思う。
$ expr expr:12+34*567 token:12: token:+: token:34: token:*: token:567: expr: $こんどは、数字は１つのまとまりとして処理されていることが分かろう。 何とか gettoken() は考えたように動き出したらしい。
数 { 演算記号 数 } ...
のような式が計算できるかどうか考えてみよう。
つまり、次のような簡単な式がちゃんと計算できるかである。
1+2+3+4 123-45 2*3+4 2+3*4このために、式評価関数 eval() を用意した。
int eval( void )
{
int value, v;
char op;
gettoken();
value = atoi(token);
while( gettoken() ) {
op = token[0];
gettoken();
v = atoi(token);
switch( op ) {
case '+': value += v; break;
case '-': value -= v; break;
case '*': value *= v; break;
case '/': value /= v; break;
}
}
return value;
}
数を示す文字列を整数に変換するのにatoi()を用いている。
ソース全体は expr4.c である。
まあ、深く考えるのはやめて、とりあえず動かしてしまおう。
$ expr expr:1+2+3+4 value = 10 expr:123-45 value = 78 expr:2*3+4 value = 10 expr:2+3*4 value = 20 expr:だいたい計算はうまくできているようだ。
しかし、最後の 2+3*4 が 20 になってしまっているが、これはプログラムから 明らかなように、 乗除 と 加減 がまったく同じ優先度になっていて、単純に 左から順番に処理されているからである。つまり、
2+3*4 → 5*4 → 20と処理されてしまったのである。 予定通りであるが、このままでは実用にならない。
式 ＝ [ '+' | '-' ] 項 { [ '+' | '-' ] 項 } ...
項 ＝ 因子 { [ '*' | '/' ] 因子 } ...
因子 ＝ 数 | '(' 式 ')'
こんな感じによく本に出ているが、意図していることはお分かりだろうか。
最も小さな単位が因子(factor)で、数そのもの、あるいは 式を 括弧で括った
ものである。つまり、因子とは一塊として扱える最小単位と考えても良い。
項(factor)というのは、そういう因子同士の乗除したもので、
いくら乗除を繰り返しても良いのである。
1*2 だけでなく、 8*7*6/2/3 なども項となる。
式とは、項に符号がついたもの、またはそれに項を加減したもので、加減は何度
繰り返してもよいのである。
-1+2 だけでなく、 8*7-6/2+3 なども式となる。というか、数と、加減乗除記号と、
括弧を組み合わせてできる式はなんでも OK のはずである。
これをプログラムで実現するために、いままで expr() だけであったが、 上の定義にしたがって、以下の関数を用意した。
int factor( void ) int term( void ) int expr( void )ちょっと長くなってしまうので、直接ソースプログラム expr5.c を見て確認して欲しい。
これを実行すると、
$ expr expr:2+3*4 value = 14 expr:-(1-2*3)-(4-5)*(6*7-8)/9 value = 8 expr:一応動作しているようだ。 ただし、エラー処理など何もやっていないので、変な入力を行うとどういう 動きをするかは一切感知していない。まあ、それらは、以上のプログラムの中に、 検査をちょこちょこ書き加えることで可能ではあるが、ここでは実用になるプログラムを 作るのが目的ではなく、再帰の説明が目的なので省略する。
gettoken() を呼ぶタイミングが、factor()、term()、expr()の３つでまちまちになっている。 expr() はその中で最初に gettoken() を呼んでいるのだが、factor()、term() の２つは、 呼ばれた時点では、gettoken() は既に呼ばれていて、配列 token にトークンが設定済み となっている。
３つの関数でこんなに違うのは良くない。いずれの関数でも、 「gettoken() は既に呼ばれていて、配列 token にトークンが設定済み」となるようにしよう。 すると、１つ問題が出て来る。それは、最初に expr() が呼ばれる時である。 もし、gettoken() が呼ばれていると仮定すると、main() の中で、トークンを意識しなくては ならなくなる。
ということで、ちょっと細工をしよう。exprではなく、
その代り、トークン関係の初期化などは、expressin()がすることになる。
まあ、そんな感じで書き換えてみたのが、 expr6.c である。
動作は何も変わっていない筈である。
ここでは簡単な再帰の実験ということだったので、１つのファイルにまとめてしまったが、 ちゃんと作るのだったら、 expressin だけをグローバルな関数として作り、他の部分は 見えなくしてしまうのが良いだろうが、そのあたりは勝手に工夫して欲しい。
ここで、再帰について、これが階乗や組合せよりもちょっと複雑になっているのが お分かりだろうか。階乗や組み合わせは、引数に対しての処理だけであったが、 今回は入力した文字列を解釈しながらトークンを切り出すという作業が こっそり進行しているのである。要するに、状態が次第に変化しているのである。 この状態変化こそが非常に重要な部分なのである。 こういう部分がまったくない再帰というのは、定義上は非常に複雑でも、 プログラム的には極めて簡単であり、定義を書き写すだけで済む。 パズルの場合、再帰と言っても、色々関数の外側の状態(外界)が再帰の計算が進むと 変わってしまうことが多い。 変わって良い場合もあれば、必要に応じて戻してやらなければならないこともある。 それらは、そのうち分かるようになるだろう、きっと。
２００１年９月３日