計算式には様々な演算子あがあります。一般的には+-*/の4種類ですね。ただ演算子には優先順位があり、ただ単純に左から右に計算するわけにはいきません。
人間ならぱっと見なんとなくで計算できるのですが、コンピュータにはそれを苦手とするので、コンピュータに解釈しやすいように専用の記法を使うことになります。それが逆ポーランド記法です。
逆ポーランド記法の仕組み
逆ポーランド記法は主にスタックを利用した計算方法です。
スタックというのは、後入れ先出しのリスト(配列)というもの。
簡単にいえば、数字を1,2,3,4の順番で追加(Push)したら、4,3,2,1の順番で取り出す(Pop)ことができるリストです。
とりあえず書き方を勉強する前に動きを先に見た方がわかりやすいと思います。書き方も後述します。
と言ってもわかりにくいので仕組みをアニメーションで見てみましょう。
左から順番に処理をしていくもので、数字ならスタックに追加、演算子なら数字を2つ取り出して計算し、その結果をスタックに戻すというものです。
並び替え方/書き方
先ほどのアニメーションの例で見てみましょう。
例えば、10 + 20 * 30 = という計算式があるとします。
まず計算しないといけないのは(20) * (30)です。なのでこれを20 30 * の順番に並び替えます。
その次に計算しないといけないのは (10) + (20*30)です。なのでこれを10と先ほどの20 30 *と演算子の+を組み合わせて10 20 30 * +と並び替えます。
これで完成です。
普通の計算式 10 + 20 * 30 =が
逆ポーランド記法では10 20 30 * + =と並び変わりました。
書き方には複数種類ある
注目していただきたいところなのですが、逆ポーランド記法の書き方には複数種類あります。
例えば、先ほどの式と同等の式はこんなものもあります。
(途中の計算式が抜けていますが、お察しください)
並びは違うのに同じように計算して同じ結果が出てきましたね。
並び替える手段は複数あるのです。
並び替えるアルゴリズム
並び替えるプログラムを作ったのですが、手元にソースコードがないのでやり方だけ書きます。
まず、演算子には複数種類ありますが、優先順位というものがあります。
なので、優先順位順番に二次配列を作ってあげます。言語はC#ですが、他の言語でも似たような感じになると思う。
public readonly string[][] Operators = new string[][] {
new string[] { "*", "/" },
new string[] { "+", "-" },
new string[] { "=" }
};
あとは、優先順位順番に演算子を検索→左右が数字だったらそれを配列に追加→最後に演算子を追加→追加した数字と演算子は元のリストから削除というのを繰り返せば、変換できます。
…といってもわかりづらいと思うので近日中に公開します…。
追記: 公開しました。
逆ポーランド記法専用電卓
過去に作った作品があるので、実際に計算してみたい方はどうぞ。
