逆ポーランド記法 (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）の後順走査

逆ポーランド記法を学ぶ手順

STEP 1括弧や演算子を含む通常の数式を入力します。
STEP 2中置式からRPNへ変換される順序をステップ実行します。
STEP 3評価時のスタックの積み下ろしと最終結果を追います。

具体的な利用例

3 + 4 × 2は「3 4 2 × +」へ変換されます。演算子の優先順位が出力キューと演算子スタックへどう反映されるかを見ることで、構文解析の流れを具体的に理解できます。

結果を見るときの注意点

対応する演算子、単項マイナス、関数の扱いは実装ごとに異なります。学習用の可視化として利用し、金額計算や科学技術計算など精度が重要な用途では専用ライブラリの仕様を確認してください。

入力データの扱い

処理はこのブラウザ内で完結し、入力したテキストやファイルは変換・解析のために外部サーバーへ送信されません。共有端末を使う場合は、作業後に入力欄とクリップボードの内容も消去してください。