読者です 読者をやめる 読者になる 読者になる

ジンジャー研究室

長めのつぶやき。難しいことは書きません。

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

括弧の入れ方のパターン

テンパズルの解答生成のロジックを考えるときに、中置記法で式を書いて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

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