逆ポーランド記法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
逆ポーランド記法（ぎゃくポーランドきほう、英語:Reverse Polish Notation, RPN）とは、演算子を操作対象の後に記述する記法。後置記法 (Postfix Notation) とも言う。たとえば、
1 + 2
（1 に 2 を足す）は
1 2 +
と書く。このような記法を採用したものとしてヒューレット・パッカード社の電卓（HP-35）などが有名である[1]。この書き方は日本語の文法とよく似ている。この語順を日本語に読み替えた、日本語版のForth的な言語がMindである。Mindだと1 と 2 とを 足すというように、日本語の普通の書き方のように記述することができる。
この記法を計算機等の入力に採用した場合かっこ操作が必要なくなる。 例えば (1 + 2) × (3 + 4) を計算する場合、数式をそのまま入力する方式の計算機ではこれら全ての記号を入力する必要があるが、逆ポーランド記法を採用した場合は 1 2 + 3 4 + * と入力すればよい（1 と 2 とを 足したものと 3 と 4 とを 足したものとを 掛ける）。
これを実現するには、計算機内部では単純なスタック構造を構成すればよいので構造も複雑にはならない。そのためソフトウェア初心者の練習課題として、この逆ポーランド記法の電卓を作ることがよく行われる。
一方、この方法では数と数との間を区切る記号（デリミタ）が必要である。上の例では1と2との間の空白、3と4との間の空白がそれである。一般的な電卓で用いられる 1 + 2 = という方法（中置記法）は、演算子及び等号そのものがデリミタとして働くため、デリミタを明示する必要は無い。
[編集] 計算動作
例題: 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]
と簡略化される。
[編集] 性質
- 被演算子の順序（上記の例では数字）は、逆ポーランド記法にしても元と同じ。
- 演算の優先順位をあらわす括弧が不要。
- 後で使われる演算子ほど、逆ポーランド記法では右に位置する。
