逆ポーランド記法
テンプレート:Infobox notation 逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法（ポーランド記法）がある。
逆ポーランド記法でも、演算子早出し逆ポーランド記法 ERP(early-operator reverse Polish notation)と、演算子遅出し(late-operator)逆ポーランド記法 LRP の分類があり、特に演算子早出し逆ポーランド記法は「その記号の配列順を些かも崩さずに和文に移せる」という特徴がある。
名称の由来は、演算子と被演算子の順序がポーランド記法の逆になっていることによる（「ポーランド記法」自体の由来についてはポーランド記法の記事を参照のこと）。
Contents
概要
例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。
3 + 4
一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。
3 4 +
逆ポーランド記法による表現は日本語などSOV型の言語の語順とよく似ており、上式であれば「3 と 4 を加算する」とそのままの順序で読み下せる。逆ポーランド記法を使うForthの影響を受けているプログラミング言語Mindでは、上式を「3と 4とを 足す」と記述する。（しかし、「1を 2から 引く」と「1から 2を 引く」で破綻する。以上のような類似は「たまたま一致する場合もある」だけに過ぎず、深入りするならきちんと言語学と日本語学や言語類型論を基礎から押さえる必要がある）
もう少し複雑な例として、中置記法による以下の式は、
(1 + 5) * (2 + 3)
逆ポーランド記法で記述すると以下の通りとなる。
1 5 + 2 3 + *
つまり、逆ポーランド記法では後で使われる演算子ほど、右に位置することになる（ポーランド記法では逆になり、左に位置する演算子ほど後で使われる）。ちなみに上式を日本語で読み下すと「1 と 5 を足したものに 2 と 3 と足したものをかけ合わせる」となる。
その他、逆ポーランド記法の特徴として括弧の使用法や区切り文字の必要性などがあるが、これらについてはポーランド記法と同様のため、そちらの項を参照のこと。
コンピュータへの応用
元々、逆ポーランド記法はポーランド記法をコンピュータでの利用に適した形に改変したものである。
逆ポーランド記法を使えば、式の計算をする（評価）には、先頭からひとつずつ順番に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を取り出して演算し結果をスタックに積む、という簡単な操作の繰り返しだけでよい。そのため、プログラミング初心者の練習課題として、逆ポーランド記法の電卓を作ることがよく行われる。
前述の手順であれば、スタックに積むのは値（たとえば後述する例では整数値）だけである（例を見て確認されたい）。もしこれが他の順序だったとしたら、演算子に相当するものを記憶するか、順番に読むだけでは済まず行きつ戻りつするか、などしなければならない。
プログラミング言語にForthやPostScriptなどのこの記法を採用したものがある。
ヒューレット・パッカード社の電卓（HP-35など）が有名で、他いくつかの電卓（特に関数電卓に採用がある）にもあるが、逆ポーランド記法順による入力方法を採用している電卓がある（近年の関数電卓のような数式入力ではなく、計算機械としてスタックモデルであり、それを直接操作しているという形なので、厳密なことを言うと逆ポーランド記法「順」ということになる）。
計算動作の例
（このような動作をベースとしている計算モデルやコンピュータを、スタックマシンと言う）
例題として以下の式を考える。スタックの他に1個のアキュムレータを持つ計算機だとする。
1 2 + 4 5 + *
[]はスタックの内容。左から右に積む。最初は空である。
- 1をスタックに積む [1]
- 2をスタックに積む [2 1]
- +が押されたら、
- スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 2） [1]
- スタックからデータを下ろしアキュムレータに足す（アキュムレータ += 1） []
- アキュムレータの内容は 3 になる (1 + 2 = 3)
- アキュムレータの内容をスタックに積む [3]
- 4をスタックに積む [4 3]
- 5をスタックに積む [5 4 3]
- +が押されたら、
- スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 5） [4 3]
- スタックからデータを下ろしアキュムレータに足す（アキュムレータ += 4） [3]
- アキュムレータの内容は 9 になる (4 + 5 = 9)
- アキュムレータの内容をスタックに積む [9 3]
- *が押されたら、
- スタックからデータを下ろしアキュムレータに入れる（アキュムレータ ← 9） [3]
- スタックからデータを下ろしアキュムレータに掛ける（アキュムレータ *= 3） []
- アキュムレータの内容は 27 になる (3 * 9 = 27)
- アキュムレータの内容をスタックに積む [27]
このように
- スタックにデータを積む (PUSH) 操作
- スタックからデータを下ろす (POP) 操作
- 二つのオペランド間の演算
だけで計算動作が可能である。
スタックトップの直接演算が可能な構造ならば、例えば最初の部分は
- 1をスタックに積む [1]
- 2をスタックに積む [2 1]
- +が押されたら、
- スタックからデータを下ろしレジスタに入れる（レジスタ←2） [1]
- スタックトップにレジスタの値を加算する [3]
と簡略化される。
文献
- 水谷静夫 「日本語の語順と逆ポーランド記法」 第7回 プログラミング・シンポジウム (1966)
- 水谷静夫 「和文の語順と逆ポーランド記法」 『国語学』第61集 (1965年6月30日)
- 斎藤正彦 『数のコスモロジー』、筑摩書房〈ちくま学芸文庫Math＆Science〉、2007年、189から192頁。