前回

プログラムで解析しやすくするため、入力の側において形式を変化させるという手法を採用しました。実際のシステム構築などでも、この方法が適用できる場合はあると思います。

今回は入力の形式を維持したまま、プログラム側で頑張って解析します。

字句解析

次の式を文字列として入力するとします。

入力例

(-3*4+ 5) + (11 * 13 / 6 - 9) * (111 % 8)

これを、次のようなイメージで内部に持たせるようにするのが目的です。数値、演算子、括弧がそれぞれきちんと切り離されて保存されています。以後、これをトークン列と呼び、一つずつをトークンと呼びます。

["(", "-", "3", "*", "4", "+", "5", ")", "+", "(", "11", "*", "13", "/", "6", "-", "9", ")", "*", "(", "111", "%", "8", ")"]

ここでは、状態と蓄えをそれぞれ Q, S と表すことにします。

この状況で、文字列を左から1文字ずつ読んでいき、その文字を c として次の処理を実行します。

演算子を読み込んだときに演算子をトークン列にすぐ突っ込めるのは、今回扱う演算子が全て1文字であるからです。

例えば ++ のような演算子が存在した場合、 + を読み込んだ時点で、その次が + なのかそれ以外なのかの分岐が発生します。 Q には N, P の他に + を1文字だけ読み込んだ新しい状態が追加され、処理もその分だけ分岐により増えます。

今度は、字句解析によって生成されたトークン列を読み込んで、計算を行った結果を数値として返します。

さて、工夫すべきポイントがあります。

何らかのプログラムを書いたとき、多くの場合は文字列もリストも左から順番に処理していくので、上記の対応が難しくなります。

関数 evaluate は、トークン列を入力とし、計算結果の数値（あるいは入力ミスによる計算不能）を返すものとして定義します。

アルゴリズムの特徴

トークン列を左から読んでいく。
右括弧がいきなり現れた場合はエラー。
左括弧が位置 L に現れた場合、対応する右括弧が現れるまで読み進める。左括弧が連続した場合、同じ個数の右括弧が出るまで。対応する右括弧が位置 R の場合、 L から R までのトークン列を新たに入力として evaluate を行う。
トークン列に括弧がない場合、左から順番に読んでいき、乗算、除算があればそれを計算する。
加算、減算を計算する。

3 によって、括弧があればその中だけを見るという操作になるので、括弧の対応が複雑に入り込んでいても、一つずつ取り払われていき、最終的に4以降の処理に進むことになります。プログラム自体は再帰を用いることになるので、思考は複雑にはなります。