逆ポーランド表記法

平成28年秋季　問03．　逆ポーランド表記法

問題文「逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の甲や演算子を左から右に順に入力し処理する。スタックが図の状態の時、入力が演算子となった。この時に行われる処理はどれか。ここで演算は中置表記法で記述するものとする。」





ここで問題文にある逆ポーランド表記法その他の記述方式は以下の通り（Wikipediaより）：
☆逆ポーランド表記法（後置法）：　二つの演算の対象の後ろに演算子（＋など）をつけて表記する
　※１＋２　⇒　１２＋　と表記される
　※X＝１＋２　⇒　X１２＋＝　と表記される
☆中置法：　通常の演算と同様に、演算の対象の間に演算子をつけて表記する。
　※１＋２　⇒　１＋２
　※X＝１＋２　⇒　X＝１＋２
☆ポーランド表記法（前置法）：　演算の対象の前に演算子をつけて表記する。
　※１＋２　⇒　＋１２
　※X＝１＋２　⇒　＝X＋１２？？？（ポーランド表記法については具体例が見つからず。。。

問題文以降出現するものが全て演算子だったと仮定し、「＋、－、＝」で入力されたとすると：
逆ポーランド表記法では「CD＋」となり、これを中置法で記述すると「C＋D」つまり「C演算子D」が答えとなる。

続いて「C＋D」の結果がスタックに積まれ、その後に「－」が入力されるので：
逆ポーランド表記法では「B結果－」となり、中置法で記述すると「B－結果」となる。

さらに続いて「B－結果」の結果（便宜上「結果２」とする）がスタックに積まれ、「＝」が入力されて：
逆ポーランド表記法では「A結果２＝」となり、中置法では「A＝結果２」となる。

最後に「＝」が入力されて完結するため、全体を逆ポーランド表記法で表記すると：
ABCD＋－＝
となる？？？

これをさらに中置法で変換すると
A＝B－（C＋D）

逆にもっと複雑な式を考えてみると
A＝（B＋C）＊（D＋E）　は逆ポーランド表記法でいくと
ABC＋DE＋＊＝

これを順にスタックに積むと
Cまで入った順でBC＋が行われ結果1がスタックに積まれる。さらにDEがスタックに積まれてDE＋が行われて結果2がスタックに積まれる。
さらに演算子「＊」が入力され、スタックに残っている結果1と結果2が結果1結果2＊で算出され、その結果3がスタックに積まれ、最後に入力される「＝」で「A結果3＝」が行われて結果3がAに代入される。

文章を中置法に置き換えると
（B＋C）＊（C＋D）の結果がAに代入される　⇒　A＝（B＋C）＊（C＋D）　となるので考え方としてはあってそうである。

ここで何故ポーランド表記法ではなく、逆ポーランド表記法ばかりが注目されるのか？という疑問と何故スタックと一対になって問題になったのか？という疑問が出てきて色々考えてみたところ、実際のメモリの使い方として利用されることが多いからか？と想像してみた。

メモリの使われ方がある基準点からどれだけ移動しながら使用するか？ということに着目した場合、逆ポーランド表記法の場合は一つ一つの演算対象と演算子の動きとメモリの利用状況が非常にわかりやすくなるからだと想像したのだ。

具体的に言うと
中置法：　A＝（B＋C）＊（D＋E）
逆ポーランド表記法：　ABC＋DE＋＊＝
これをメモリのスタックの状態遷移で考えてみるとわかりやすいかもしれない？

ABC＋DE＋＊＝
これを1ステップずつ考えてみる。ちなみにメモリのスタックは下に積まれる（メモリの基準点の先頭位置が一番上で、次の値が入った場合に基準点から1つずれたところに二つ目が入る）

１．　A入力
Aは演算対象（オペランド）なので、メモリに記憶される：
*****メモリ*****
A
*****以　上*****

2．　B入力
オペランドでメモリに記憶
*****メモリ*****
A
B
*****以　上*****

3．　C入力

オペランドでメモリに記憶
*****メモリ*****
A
B
C
*****以　上*****

4．　＋入力

演算子（オペレータ）なので演算処理、2つ前のオペランドと1つ前のオペランドをオペレータに従って計算し、結果Xをメモリに格納

*****メモリ*****
A
X
*****以　上*****

5．　D入力

オペランドなのでメモリに格納

*****メモリ*****
A
X
D
*****以　上*****

6．　E入力

オペランドなのでメモリに格納

*****メモリ*****
A
X
D
E
*****以　上*****

7．　＋入力

オペレータなので演算処理を2つ前と1つ前のオペランドに行い、結果Yをメモリに格納

*****メモリ*****
A
X
Y
*****以　上*****

8．　＊入力
オペレータなので演算処理を2つ前と1つ前のオペランドに行い、結果Zをメモリに格納

*****メモリ*****
A
Z
*****以　上*****

9．　＝入力

オペレータの演算処理として、2つ前の値に1つ前の値を代入する。

*****メモリ*****
Z
*****以　上*****

結果としてオペレータ（＝）までの算出結果をAに代入して演算を終わるため、増えたり減ったりしながらメモリの使用量を最小限に抑えつつ、コンピュータが理解しやすいように一つ一つの作業が簡潔に伝えられるからなのではないか？

この点についてはより深い勉強が必要だけど、とりあえずこんな感じで覚えてみた。