演算の順序を逆ポーランド記法で整理するメモ

括弧の入れ方のパターン

テンパズルの解答生成のロジックを考えるときに、中置記法で式を書いてevalするというロジックを考えたわけだが、括弧の挿入位置を考えるのが面倒で別の方法を考えていた次第。

以下の表は、中置記法での括弧の入れ方のパターンを逆ポーランド記法によって整理したもの。1, 2, 3, 4 には任意の値、x, y, z には任意の演算が入る。

中置記法	ポーランド記法 （前置記法）	逆ポーランド記法 （後置記法）
(((1 x 2) y 3) z 4)	z y x 1 2 3 4	1 2 x 3 y 4 z
((1 x 2) z (3 y 4))	z x 1 2 y 3 4	1 2 x 3 4 y z
((1 y (2 x 3)) z 4)	z y 1 x 2 3 4	1 2 3 x y 4 z
(1 z ((2 x 3) y 4))	z 1 y x 2 3 4	1 2 3 x 4 y z
(1 z (2 y (3 x 4)))	z 1 y 2 x 3 4	1 2 3 4 x y z

後はスタックマシンに食わせるだけ。やったね！