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

逆ポーランド記法（Reverse Polish Notation / RPN）は、演算子をオペランドの後に置く後置記法です。 例えば、中置式 3 + 4 * 2 は RPN で 3 4 2 * + と表現されます。括弧が不要で、スタック1つで評価できるため、コンパイラやインタープリタの内部表現として広く使われます。

Shunting-yard アルゴリズム（中置→RPN変換）

エドガー・ダイクストラが1961年に考案したアルゴリズムです。演算子スタックと出力キューを用いて、演算子の優先度・結合性・括弧を正しく処理しながら中置式をRPNに変換します。計算量はO(n)です。

• 数値はそのまま出力キューへ
• 演算子は、スタック上の優先度が高い（左結合の場合は同等も含む）演算子をすべてポップしてから、スタックへプッシュ
• ( はスタックへプッシュ。) は対応する ( が見つかるまでポップ
• 最後にスタック上の残り演算子をすべてポップ

RPN の評価（スタックマシン）

RPNの評価はスタック1つで行えます。数値ならプッシュ、演算子なら2つポップして計算し結果をプッシュするだけです。最終的にスタックに残った1つの値が答えです。

演算子の優先度と結合性

• +-: 優先度 1（左結合）
• */%: 優先度 2（左結合）
• ^: 優先度 3（右結合）— 2^3^2 = 2^(3^2) = 512

活用例

• コンパイラ・インタープリタの式評価
• HP の電卓（RPN 入力方式）
• PostScript 言語
• Java Virtual Machine のオペランドスタック
• 式木（AST）の後順走査