プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

中置記法を逆ポーランド記法に変換、逆ポーランド記法の計算法

あっれぇ?
大分前にJavaScriptで色を逆ポーランド方に変換してから計算するスクリプトを作ってから何回か逆ポーランド記法で検索かけてきた人たちがいるんだよねぇ。


どうせ需要ないしいいだろとか思ってたんだけど……必要?
まぁ、やりっ放しで放置ってのもどうかなので一応ざっくり解説しておこうか。

まず、中置記法というは、私たちが普段使っている書き方。
5+8*(4+5)
こんな感じの奴ね。数字と数字の間に演算子が来るから中置です。

逆ポーランド記法は上の例だと
5 8 4 5 + * +
となります。()が必要ない記述方なのでコンピューターで扱いやすいです。
プログラムで中置記法式を計算しにくいので逆ポーランド記法に変換してから計算します。



まずは、決め事をしておきます。中置記法では演算子の優先順位という物があります。上の式では先に5+8を計算してはダメですね。
よって、式に出てくるオペランド(数値)とオペレーター(演算子)に優先順位の番号を付けておきます。

オペランド(数値)0 
 * / %
1
 + -
2
()
3 


数値が若いほど優先度が高くなります。
()は数値と見なせますが、逆ポーランド記法では要らなくなるので特に設定する必要はないですので、最大値にしておきます。


書き換え結果を保存するための双方向リストpと途中で必要なスタックsを用意します。(それぞれが意味不明という人はリンク先参照) pは計算を実際にするときも考えて双方向にしたが、スタック構造でも実際は構わない。


流れはこんな感じだ。
①式の左から数、演算子を一つ取り出す。
②sの一番上の優先度が①で盗った値よりも高くなるまでpに値を移し、sに①を積む
③ただし、(が来た場合は何もせずにsに(を積み、)が来た場合は最初の(に当たるまでsの値をpに移していく。( と )は移さずに捨てる。

④式の最後までこれをくり返す。
⑤最後にsに残っている値をpに移す



終わったらpを下から読み込めば逆ポーランド記法に変換完了だ。(pもスタック構造の場合はpをsに移し替えれば良し)

次に計算をする。先に謝罪するが、図中では式が全て逆になっている。(割り算がないので結果は間違っていない)

①式から一つ読み出す。
②①が数値なら左に積む。
③①が演算子なら左から2つ数を取り出し演算をし、結果を左に積む。割り算の場合、先に取り出した方で割り、後で取り出した方を割る。%についても同様。
④繰り返し
⑤最後に残ったのが答え


(5+4=9,9*8=72,72+5=77ではなく、4+5=9,8*9 = 72,5+72=77が正しい)

以上で解説を終わります。