Javaで逆ポーランド記法変換・計算プログラムを作ってみた(準備編)

どうもこんにちは、食べられないタイプのポテト君です。(？)

ということで今回は、Javaを使って逆ポーランド記法(Reverse Polish Notation:RPNまたは後置記法)というものを扱っていきます。
(逆ポーランド記法は長いのでRPNで呼ぶことにします)

逆ポーランド記法(RPN)とは

まずはRPNってなんだ？というところから話していきます、
RPNとは、計算式の記述方法の1種です。
もちろん逆があるならポーランド記法(Polish Notationまたは前置記法)もありますが、RPNの方が有名です。

大まかに言うと、コンピューターが処理しやすいように書き換えられた計算式の記法です。
一般に使われる人間が理解しやすい記法は中置記法(infix notation)といいます。

中置記法→RPN

実際にどんなものなのか見ていきます。
後置記法と言われるぐらいなので、何かを後ろに置くわけです。
その何かは、演算子のことを指します。
例えば
a+b(中置記法)
は、RPNでは
ab+
となります。
これが分かっていれば、中置記法の式はRPNに変換できます。
変換の際は、優先度(かっこ内が先、加減算より乗除法の方が先など)に注意してください。
例：
a+b*(c-d)/e
↓(c-d)=cd-=f
a+b*f/e
↓b*f=bf*=bcd-*=g
a+g/e
↓g/e=ge/=bcd-*e/=h
a+g
↓a+g=ag+
abcd-*e/+

RPNを計算する

スタックとは

では、逆ポーランド記法を計算するにはどうすればいいのでしょうか。
この時に、スタックというものを使います(これがコンピューターの扱いやすい理由でもあります)。
スタックとは、複数の値を入れる箱のようなものです。
上向きに空いた箱に、ぴったり入る本を表紙が見えるように入れる状況を考えてみてください。
その本を取り出すとき、最後に入れた本から先に取り出されて、最初に入れた本は最後に出されますね。
これと同じようにスタックでは入れた順番と逆に値が取り出されます。
このことをFILO(First In Last Out)と言ったりもします。

計算方法

実際にスタックを使ってRPNを計算してみます。
例えばab+なら
1:aをスタックに入れる
2:bをスタックに入れる
3:スタックから2つの値を取り出し、足し合わせる
といったように、RPNを使えば、
先頭から式を読み取り
値ならスタックに入れる
演算子ならスタックから２つの要素を取り出して演算をする(演算後の結果をスタックに戻す)
といった処理をすれば計算ができます。
-や*の演算をするとき、最初にスタックから取り出した要素は演算子の後に付かないと結果が変わってしまうことに注意してください。
例:
スタック：空、式：ab+c*d-
→スタック：a、式：b+c*d-
→スタック：ab、式：+c*d-
→スタック：(a+b)、式：b+c*d-
→スタック：(a+b)c、式：*d-
→スタック：((a+b)*c)、式：d-
→スタック：((a+b)*c)d、式：-
→スタック：(((a+b)*c)-d)、式：
→結果：(((a+b)*c)-d)

その他

説明では文字式を使いましたが、今回は具体的な数値が与えられてる式を扱います。
(その時には、2つの数が1つにならないように、変数の代わりに数を[ ]で囲うものとします。
例:1+4→[1][4]+)
変数を使う場合、使用出来る数が限られてしまうので…
まあab+c*d-を(((a+b)*c)-d)にしても計算しないならあまり意味がない(((
中置記法をRPNに変換するプログラムに関しては

数式を逆ポーランド記法に変換 - Qiita

この記事を参考にさせて頂きました。
ただし、このプログラムには計算上致命的な欠点があるのでそのまま使用している部分は少ないです。
加減算の例としてこのプログラムではa-b+cは
abc+-
となりますが
ab-c+
が正解です。
abc+-を計算すると
a-(b+c)
となってしまい、計算結果が変わってしまいます。
またこれは乗除法についても同様のミスが起こってしまいます。
これらのミスを直したことにより、( )の処理についても書き直さなければいけないため、あまり原形をとどめていない部分が多いです。
また、今回は変数を使わず、実数を[]で囲んで使用するため、その対応も行っています。