数式の表記方法にはいくつかの種類がありますが、その中でも「逆ポーランド記法（Reverse Polish Notation, RPN）」は、一見すると風変わりながら、非常に合理的な構造を持っています。この記事では、RPNの特徴と、その簡潔なHaskellによる実装例を紹介します。
逆ポーランド記法とは
通常の数式（中置記法）では、演算子はオペランドの間に記述されます。たとえば：
(3 + 4) * 2
これを逆ポーランド記法で書くと、次のようになります：
3 4 + 2 *
演算子が後置されるため、RPNは「後置記法（Postfix notation）」とも呼ばれます。
RPNの利点
逆ポーランド記法の最大の利点は、括弧が不要である点です。演算の順序はスタックベースの評価ルールによって自動的に決まります。以下の特徴が評価されています：
- 構文解析が簡潔になる（特に再帰下降構文解析器で有利）
- 括弧を使わずに複雑な式が表現可能
- 実装がシンプルで、評価も効率的
RPNの評価方法
RPNの式は、左から右へとトークンを処理していきます。数値はスタックに積み、演算子に出会ったらスタックから必要な数値を取り出して演算を行い、結果をスタックに戻します。
例
5 1 2 + 4 * + 3 -
この式は以下のように評価されます：
-
1 2 +→3 -
3 4 *→12 -
5 + 12→17 -
17 - 3→14
中置記法では：
5 + ((1 + 2) * 4) - 3
Haskellで書くRPN電卓
RPNの処理は、スタック操作に基づくため、関数型言語での実装に非常に向いています。以下はHaskellによる簡潔な実装例です。
solveRPN :: String -> Double
solveRPN = head . foldl foldingFunction [] . words
where foldingFunction (x:y:ys) "*" = (y*x):ys
foldingFunction (x:y:ys) "+" = (y+x):ys
foldingFunction (x:y:ys) "-" = (y-x):ys
foldingFunction (x:y:ys) "/" = (y/x):ys
foldingFunction (x:y:ys) "^" = (y**x):ys
foldingFunction (x:xs) "ln" = log x:xs
foldingFunction xs "sum" = [sum xs]
foldingFunction xs numberString = read numberString:xs
この関数は文字列を空白で分割し、foldl を用いて左から順にスタック操作を行います。演算子や関数はパターンマッチで定義されており、読みやすく拡張もしやすい構成です。
使用例（GHCiにて）
> solveRPN "10 4 3 + 2 * -"
-4.0
> solveRPN "2.7 ln"
0.9932517730102834
> solveRPN "1 2 3 4 5 sum"
15.0
おわりに
逆ポーランド記法は、単なる記法の違いにとどまらず、式の評価戦略そのものを変える力を持っています。特に、式の評価をシンプルに、かつ決定的に行いたい場合に非常に有効です。
関数型言語との相性も良く、特にHaskellでは高階関数とパターンマッチによって明快な実装が可能です。小さな電卓アプリや言語処理系を作る際の参考としても価値のある題材と言えるでしょう。
ぜひ皆さんも作ってみてください。