前回
プログラムで解析しやすくするため、入力の側において形式を変化させるという手法を採用しました。実際のシステム構築などでも、この方法が適用できる場合はあると思います。
今回は入力の形式を維持したまま、プログラム側で頑張って解析します。
字句解析
目的
次の式を文字列として入力するとします。
(-3*4+ 5) + (11 * 13 / 6 - 9) * (111 % 8)
これを、次のようなイメージで内部に持たせるようにするのが目的です。数値、演算子、括弧がそれぞれきちんと切り離されて保存されています。以後、これをトークン列と呼び、一つずつをトークンと呼びます。
["(", "-", "3", "*", "4", "+", "5", ")", "+", "(", "11", "*", "13", "/", "6", "-", "9", ")", "*", "(", "111", "%", "8", ")"]
状態の変化と文字列の蓄え
ここでは、状態と蓄えをそれぞれ Q, S と表すことにします。
- Q は、通常 (P)、数値読み込み状態 (N) のどちらかをとる。初期状態は P である。
- S は、 Q = N のとき、読んだ数字を追加することで蓄え、 Q = P になったときに空にする。初期状態は空文字列である。
この状況で、文字列を左から1文字ずつ読んでいき、その文字を c として次の処理を実行します。
- c が数値であれば、 Q = N に変更し、 S に c を追加。
- c が演算子であれば、 Q = P に変更する。 S の内容を数値としてトークン列に追加し、 S を空文字列にする。さらに、演算子をトークン列に追加する。
- c が空白であれば、 Q = P に変更する。 S の内容を数値としてトークン列に追加し、 S を空文字列にする。
注意
演算子を読み込んだときに演算子をトークン列にすぐ突っ込めるのは、今回扱う演算子が全て1文字であるからです。
例えば ++ のような演算子が存在した場合、 + を読み込んだ時点で、その次が + なのかそれ以外なのかの分岐が発生します。 Q には N, P の他に + を1文字だけ読み込んだ新しい状態が追加され、処理もその分だけ分岐により増えます。
構文解析
今度は、字句解析によって生成されたトークン列を読み込んで、計算を行った結果を数値として返します。
さて、工夫すべきポイントがあります。
- 乗算 (*)、除算 (/, %) は、加算 (+) 、減算 (-) より優先して計算する。
- 括弧の中は先に計算する。
何らかのプログラムを書いたとき、多くの場合は文字列もリストも左から順番に処理していくので、上記の対応が難しくなります。
関数 evaluate は、トークン列を入力とし、計算結果の数値（あるいは入力ミスによる計算不能）を返すものとして定義します。
アルゴリズムの特徴
- トークン列を左から読んでいく。
- 右括弧がいきなり現れた場合はエラー。
- 左括弧が位置 L に現れた場合、対応する右括弧が現れるまで読み進める。左括弧が連続した場合、同じ個数の右括弧が出るまで。対応する右括弧が位置 R の場合、 L から R までのトークン列を新たに入力として evaluate を行う。
- トークン列に括弧がない場合、左から順番に読んでいき、乗算、除算があればそれを計算する。
- 加算、減算を計算する。
3 によって、括弧があればその中だけを見るという操作になるので、括弧の対応が複雑に入り込んでいても、一つずつ取り払われていき、最終的に4以降の処理に進むことになります。プログラム自体は再帰を用いることになるので、思考は複雑にはなります。
参照
自作コード： https://github.com/tfull/arithmetic_operations/tree/main/normal