逆ポーランド記法
例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。
一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後(右)に置いて、以下のよう記述する。
逆ポーランド記法による表現は日本語などSOV型の言語の語順とある程度似ており、上式程度であれば「3 と 4 を加算する」とそのままの順序で読み下せる。逆ポーランド記法を使うForthの影響を受けているプログラミング言語Mindでは、「3と 4とを 足す」と書く。
もう少し複雑な例として、中置記法による以下の式は、
逆ポーランド記法で記述すると以下の通りとなる。
つまり、逆ポーランド記法では後で使われる演算子ほど、右に位置することになる(ポーランド記法では逆になり、左に位置する演算子ほど後で使われる)。ちなみに上式を日本語で読み下すと「3 と 4 を足したものに 1 から 2 を引いたものをかけ合わせる」となる。
その他、逆ポーランド記法の特徴として区切り文字の必要性などがあるが、これらについてはポーランド記法と同様のため、そちらの項を参照のこと。
(このような動作をベースとしている計算モデルやコンピュータを、スタックマシンと言う)
例題として以下の式を考える。スタックの他に1個のアキュムレータを持つ計算機だとする。
[]はスタックの内容。左から右に積む。最初は空である。
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]