逆ポーランド記法 【RPN】 Reverse Polish Notation / 後置記法 / postfix notation

概要

解説 日常的な算術や数学では、演算子を対象の真ん中に挟む「中置記法」（infix notation）が一般的で、「1と2の和」を「1+2」のように表記する。この記法は演算子の結合順序のルール（優先順位）や括弧による計算順の指定が必要で、「1+2×3+4」と「（1+2）×（3+4）」は違う式になる。

一方、逆ポーランド記法は演算子を後ろに置く表記法で、「1と2の和」は「1 2 +」のように表記する。四則演算などの二項演算子のみを利用する場合、結合順の指定が無くても一意に計算順序を決定できる。例えば、中置記法の「1+2×3+4」は「1 2 3 × + 4 +」、「（1+2）×（3+4）」は「1 2 + 3 4 + ×」と表記される。

値の間に必ず演算子が挟まる中置記法と異なり、値同士を並べて記述するため、どこが値の境界なのか明確になるよう区切り記号（コンピュータの場合は空白文字など）を挟むなどして分かち書きをする必要がある。

この記法はポーランドの論理学者、ヤン・ウカシェヴィチ（Jan Łukasiewicz）が考案した「ポーランド記法」（Polish notation）の逆順であるため、このように呼ばれる。ポーランド記法では「+ 1 2」のように演算子の後に被演算子の列を記載する。

ポーランド記法も逆ポーランド記法も、コンピュータプログラムが数式を扱う際に都合が良いため、数式処理のためのデータ構造などに応用されることがある。両者の特徴はほとんど同じだが、逆ポーランド記法はスタック構造を利用して単純な操作の繰り返しで数式を評価するプログラムを記述できるため、電卓プログラムを作るプログラミング課題などの形でよく取り上げられる。