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