後置記法（逆ポーランド記法、RPN）とは

歴史と発展

論理学および算術における代替的な記法という考え方は、20世紀初頭の論理学者たちの研究にさかのぼる。ヤン・ウカシェヴィチは、論理式から曖昧さを除くため、1920年代に現在ポーランド記法（前置記法）と呼ばれるものを提案した。演算子を被演算子の後に置くという関連する考え方、すなわち後置記法または逆ポーランド記法は、コンピュータや電卓のための実用的な評価方式として20世紀半ばに発展し、普及した。チャールズ・ハンブリンは、論理学と計算機分野で後置記法を用いることの普及に重要な役割を果たした。人物および歴史に関する資料は、ハンブリンの業績、ウカシェヴィチ、およびポーランド記法の解説を参照。

仕組み：特徴と評価

後置式では、最初に被演算子を並べ、その後に演算子を置く。後置式を評価する標準的な手順は次のとおりである。

1. 式を左から右へ走査する。
2. 被演算子に出会ったら、それをスタックにプッシュする。
3. 演算子に出会ったら、必要な数の被演算子をスタックからポップし、演算子を適用して、結果をスタックへ戻す。
4. 最後に、スタックには結果が残る。

この単純なアルゴリズムにより、後置記法はスタックベースのハードウェアやインタプリタへの実装に適している。

例として、中置式「(3 + 4) * 5」は、後置記法では「3 4 + 5 *」となる。評価では、3と4をプッシュし、+を適用して7を得てから、5をプッシュし、次に*を適用して35を得る。チュートリアルで使われるより複雑な例に「5 1 2 + 4 * + 3 -」がある。これは14と評価され、括弧なしで入れ子の演算を表せることを示している。実装に関する注記は、電卓言語を参照。

用途と応用

• 電卓：多くのヒューレット・パッカード製ハンドヘルド電卓は、キー操作と括弧を減らせることから、RPNを主要な入力方式として採用した。HP電卓の歴史および製品資料の利用者向けガイドを参照。
• プログラミング言語と形式：グラフィックスおよびプリンタ向けの一部の言語や文書形式、特にPostScriptは、内部的に後置記法型の構文を用いる。これは、資源が限られた機器での構文解析を簡素化する。
• コンパイラとインタプリタ：後置記法は、コンパイラおよびスタックベースの仮想マシンにおける中間表現である。その評価モデルは、プッシュ／ポップのバイトコードに直接対応する。

手書きの代数式では一般的ではないものの、後置記法は決定的な評価と最小限の構文解析要件により、教育、計算機科学、組込みシステムにおいて重要であり続けている。また、式木と評価順序を理解するための有用な思考モデルでもある。

主な相違点：前置記法（ポーランド記法）では演算子を被演算子の前に置くのに対し、後置記法では後に置く。どちらも括弧を不要にするが、人間にとっての読みやすさ、および特定の機械や言語への適合の仕方は異なる。RPNはスタックというデータ構造と密接に結び付いており、一方を理解すると他方の理解も深まる。

さらに読むための資料やツールの実装は、入門書やオンライン資料から見つけられる。アルゴリズム、歴史的背景、実用的な用途を探究したい読者のために、上記にいくつかの入口を示した。