逆ポーランド記法

出典: くみこみックス

逆ポーランド記法（ぎゃくポーランドきほう）【Reverse Polish Notation】

　コンパイラによる数式処理でよく用いられるテクニックの一つ．複雑な数式でも，スタック操作の概念を導入し，比較的単純な操作に置き換えることができる．RPN（Reverse Polish Notation）と呼ばれることもある．

　具体的にRPNで1＋2×3を求めてみよう．この式は，RPNでは1，2，3，×，＋と表現される．この操作は「1に2と3を×したものを＋する」と読めば分かりやすい．式をRPNで記述するには，数値（または変数）は式の左から現れた順に，演算子は式の右側から書き出していく．RPNでは，乗算と加算の演算順位にかかわらず，かっこを含む式でも簡単なアルゴリズムで計算できる．例えば，5×（4＋3）ならRPNでは5，4，3＋×となる．すなわち，5に4と3を＋したものを×すると読めば，演算順位の判定やかっこなしで答えが得られる．実際の計算機内での処理は，数値（変数）を5，4，3の順にスタックに積み上げ，式の左側から演算子を取り出し，スタックから二つの数値（変数の値）を取り出して演算し，結果を再びスタックに積む．以後，スタックから二つの数値（変数の値）を取り出し，次の演算子による演算操作を行い，結果をスタックに積む，という操作を繰り返す．やがて最後にスタックに積んだ値が式の答えとなる．

　かつて，RPNを採用した電卓がHewlett-Packard社から販売されていた．この電卓の特徴は，かっこと＝のキーがないことである．RPNの場合，最後に得られる値が答えになるため，これらのキーは必要ない．

【出典】Interface編集部 編；組み込み技術用語集，Interface 2007年8月号 別冊付録，CQ出版社，2007年8月．