逆ポーランド記法
逆ポーランド記法（ぎゃくポーランドきほう、英語:Reverse Polish Notation, RPN）とは、数式やプログラムを記述する方法（記法）の一種。演算子（オペレータ）を被演算子（オペランド）の後（右）に記述することから、後置記法（Postfix Notation）とも言う。
|
| ポーランド記法 |
| 中置記法 |
| 逆ポーランド記法 |
その他の記法として、演算子を被演算子の中間に記述する中置記法、前（左）に記述する前置記法（ポーランド記法）がある。
名称の由来は、演算子と被演算子の順序がポーランド記法の逆になっていることによる。
概要
例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。
3 + 4
一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。
3 4 +
逆ポーランド記法による表現は日本語の文法とよく似ており、上式であれば「3 と 4 を加算する」とそのままの順序で読み下せる。逆ポーランド記法を使うForthの影響を受けているプログラミング言語 Mind では、上式を「3 と 4 とを 足す」と記述する。
もう少し複雑な例として、中置記法による以下の式は、
(1 + 5) * (2 + 3)
逆ポーランド記法で記述すると以下の通りとなる。
1 5 + 2 3 + *
つまり、逆ポーランド記法では後で使われる演算子ほど、右に位置することになる（ポーランド記法では逆になり、左に位置する演算子ほど後で使われる）。
その他、逆ポーランド記法の特徴として括弧の使用法やデリミタの必要性などがあるが、これらについてはポーランド記法と同様のため、そちらの項を参照のこと。
コンピュータへの応用
元々、逆ポーランド記法はポーランド記法をコンピュータでの利用に適した形に改変したものである。
逆ポーランド記法を使えば、式の計算をする（評価）には、先頭からひとつずつ順番に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を取り出して演算し結果をスタックに積む、という簡単な操作の繰り返しだけでよい。そのため、プログラミング初心者の練習課題として、逆ポーランド記法の電卓を作ることがよく行われる。
前述の手順であれば、スタックに積むのは値（たとえば後述する例では整数値）だけである（例を見て確認されたい）。もしこれが他の順序だったとしたら、演算子に相当するものを記憶するか、順番に読むだけでは済まず行きつ戻りつするか、などしなければならない。
ヒューレット・パッカード社の電卓（HP-35など）は、逆ポーランド記法による入力方法を採用していることで有名である。他いくつかの電卓（特に関数電卓に採用がある）や、プログラミング言語にForthやPostScriptなどのこの記法を採用したものがある。
計算動作の例
例題として以下の式を考える（[]はスタックの内容。左から右に積む。最初は空だとする）。
1 2 + 4 5 + *
- 1をスタックに積む [1]
- 2をスタックに積む [2 1]
- +が押されたら、
- スタックからデータを下ろしレジスタ2に入れる（レジスタ2←2） [1]
- スタックからデータを下ろしレジスタ1に入れる（レジスタ1←1） []
- レジスタ1とレジスタ2の和を得る (1 + 2 = 3)
- 結果をスタックに積む [3]
- 4をスタックに積む [4 3]
- 5をスタックに積む [5 4 3]
- +が押されたら、
- スタックからデータを下ろしレジスタ2に入れる（レジスタ2←5） [4 3]
- スタックからデータを下ろしレジスタ1に入れる（レジスタ1←4） [3]
- レジスタ1とレジスタ2の和を得る (4 + 5 = 9)
- 結果をスタックに積む [9 3]
- *が押されたら、
- スタックからデータを下ろしレジスタ2に入れる（レジスタ2←9） [3]
- スタックからデータを下ろしレジスタ1に入れる（レジスタ1←3） []
- レジスタ1とレジスタ2の積を得る (3 * 9 = 27)
- 結果をスタックに積む [27]
このように
- スタックにデータを積む (PUSH) 操作
- スタックからデータを下ろす (POP) 操作
- 二つのオペランド間の演算
だけで計算動作が可能である。
スタックトップの直接演算が可能な構造ならば、例えば最初の部分は
- 1をスタックに積む [1]
- 2をスタックに積む [2 1]
- +が押されたら、
- スタックからデータを下ろしレジスタに入れる（レジスタ←2） [1]
- スタックトップにレジスタの値を加算する [3]
と簡略化される。
文献
- 水谷静夫 「日本語の語順と逆ポーランド記法」 第7回 プログラミング・シンポジウム (1966)