Aritalab:Lecture/Algorithm/PolishNotation

ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を考えます。

演算子を後置する逆ポーランド記法

演算子を後置する逆ポーランド記法はスタックを利用して簡単に演算をおこなえるメリットがあります。まず、入力文字列から数値を順番に切り出し（トークン token と呼びます）、スタックに積んでいきます。もし演算子トークンがきたら、スタックから演算を施す数値（オペランド operand と呼びます）を取り出して演算結果を再びスタックに積みます。

入力文字列が終わりにきたとき、最後の演算子を用いてスタックの中身を処理すると、スタックに は一つだけ数値が残されているはずです。これが計算の最終結果になります。

演算子を中置する通常の電卓

普通の数式を処理するには、演算子の優先度を考慮しなくてはなりません。 たとえば

2 + 3 * 5

と書かれたら、掛け算を先に処理して結果が30になります。

2 + log 3 * 5

と書かれたら、log を計算してから掛け算、足し算の順番になります。この式が左から順番 に読み込まれたと仮定しましょう。スタックには、

2, +, log, 3

が積まれます。次に * を読み込んだ時点で 3, log と逆に pop し、 log 3 = 1.09 を push します。その後、掛け算、足し算と処理を進めます。

つまり、演算子の優先度は、

log などの単項演算子 > 乗除算 > 加減算

です。

括弧つきの数式

1 / (2 + 3) * 5

と書かれたら、括弧の中身を先に計算せねばなりません。また括弧は入れ子状に書けます。 括弧つきの数式を処理するには、スタックに積んである情報をいったん退避させ、新しい数式が始まると考えなくてはいけません。例えば以下の式を考えてみましょう。

2 + log ( ( 2 + 3 ) * 5 + 2 ) + 1

括弧の外側にある log は、括弧の中身が全て計算された後に適用します。 プログラム中では、左括弧をみつけたらトークンを読み込む関数を再帰呼び出しし、右括弧が数式の最後であるかのように処理します。