|
3. 計算式解析
計算式を解析する場合，大きく分けて2つの方法が考えられます．
1つは，各種プログラム言語コンパイラで採用されているように，字句解析器にてトークンに分類し，構文解析器によって式を解析，実行する方法です．また他の手段としては，一旦逆ポーランド式に変換してから実行する，というものがあります．
前者の方法は非常に厳密にエラーチェックが可能で，また計算式以外のものについても解析が可能ですが，実装するにはあまりに大掛かりであり，今回のBASICにおいてはそれほどは必要ではありません．従って，BASICあるいはFortranなどで一般的に実装されているように，計算式解析ルーチンには逆ポーランド変換ルーチンを採用することにします．
3.1. 逆ポーランド変換
世間一般で目にする数式の場合，式中の演算子の優先順位によって，計算をする順番が入り乱れるため，プログラムでこれを行なうのは，非常に都合が悪いと言えます．
一方，逆ポーランド式では，演算子の強度に関係なく，式の先頭から順に計算をしていけば良いため，こちらはプログラムによって処理する上で非常に都合が良いと言えます．
逆ポーランド式は，演算対象1,演算対象2,演算子,演算対象1,演算対象2,...の形で表現された式のことを言います．一般的な式のように，演算子に優先順位があったり，あるいは括弧があったりということはありません．逆ポーランド式は式の先頭から順に計算されていくため，優先順位の高い演算子とそれが対象としている演算対象は，式の先頭のほうに配置されることで優先順位とされます．
例えば，次の式を逆ポーランド式に変換したとすると，このようになります．
式： c*(256-t)+(-c)
生成される逆ポーランド式: c 256 t - * c -
+
3.2. 逆ポーランド式の生成規則
逆ポーランド式の生成規則は以下の通りです．
| I. |
定数はそのまま出力 |
| II. |
演算子がきて，かつスタックに既に詰まれている演算子がないなら，演算子をスタックに積む |
| III. |
演算子がきて，かつスタックに既に積まれている演算子があるなら，もし積もうとしている演算子の優先順位が既にあるものより高いなら，演算子をスタックに積む |
| IV. |
(III)の第一条件下で，積もうとしている演算子の優先順位が既にあるものよりも低いか同じなら，スタックにある，優先順位の高い演算子を全て出力してから新しい演算子をスタックに積む |
| V. |
与式を全て処理したなら，スタックの演算子を全て出力 |
次に，変換の様子を示します．
| スタック |
未処理式 |
出力結果 |
適合規則 |
| (例1) |
a*b+c |
|
|
| |
*b+c |
a |
(I) |
| * |
b+c |
a |
(II) |
| * |
+c |
a b |
(I) |
| + |
c |
a b * |
(IV) |
| + |
|
a b * c |
(I) |
| |
|
a b * c + |
(V) |
| |
|
|
|
| (例2) |
c*(256-t)+(-c) |
|
|
| |
*(256-t)+(-c) |
c |
(I) |
| * |
(256-t)+(-c) |
c |
(II) |
| * |
-t+(-c) |
c 256 |
(I) |
| *- |
t+(-c) |
c 256 |
(III) |
| *- |
+(-c) |
c 256 t |
(I) |
| + |
(-c) |
c 256 t - * |
(IV) |
| +- |
c |
c 256 t - * |
(III) |
| +- |
|
c 256 t - * c |
(I) |
| |
|
c 256 t - * c -
+ |
(V) |
3.3. 逆ポーランド式の実行(計算)
逆ポーランド式に変換された式を解釈／計算するには，逆ポーランド式を構成する要素を先頭から順にスタックに積んでいき，演算子が発生した段階でスタックの内容との演算を行ない，その結果を再びスタックへ積むようにする．
今，逆ポーランド式b - c d * + 512 t - sqr -が与えられたとした場合，以下のような経緯で数式の処理がなされる．
| プロセス |
スタックの状況 |
演算子 |
演算内容 |
結果 |
| (I) |
b |
- |
-b |
(A) |
| (II) |
(A) c d |
* |
c*d |
(B) |
| (III) |
(A) (B) |
+ |
(A)+(B) |
(C) |
| (IV) |
(C) 512 t |
- |
512-t |
(D) |
| (V) |
(C) (D) sqr |
sqr |
sqr(D) |
(E) |
| (VI) |
(C) (E) |
- |
(C)-(E) |
(F) |
最終的に全ての演算子を処理し，スタックの先頭に残った(F)が，この式の解です．
3.4. 式解析における注意点
(A)
括弧の処理について
スタックに演算子を積む際に，演算子の強度も同時に積んでしまうようにしておく．
括弧が直前にあった場合，演算子強度に括弧レベル(現在いくつ目の括弧の中か)の
値を加えて積むようにすれば，括弧外のいかなる演算子よりも優先順位が高くなる．
(B)
再帰的呼び出しについて
例えば
printf( "%d\n", sqrt( sin( deg2rad( r ) ) )
);
などの場合，sqrt()で数式解析が発生し，処理中にsin()内の数式解析が起動されて
しまうため，再起呼び出しを考慮しておかなければならない．
(C)
エラー処理
この方法の最大の欠点は，エラーの検出がしにくいことである．
妙な式が通ってしまい．変な解答がでてくることがあるため，注意すること．
|
