top page > computer > haskell > web_lecture > for_programmer > rev_polish.html
更新日:
文責: 重城良国

逆ポーランド記法電卓

rev_polish.hs

はじめに

演算子を後に書く記法が逆ポーランド記法だ。後置記法とも呼ぶ。スタックマシンとの相性が良いためポーランド記法よりもむしろ有名だ。

ウィキペディア: 逆ポーランド記法

同じ意味の中置記法の式と逆ポーランド記法の式だ。

(1 + 5) * (2 + 3)

1 5 + 2 3 + *

仕様

整数の四則演算のみとする。数値や演算子を文字列のリストとしてわたす。返り値は整数のリストのMaybe値だ。計算が完全に終われば1要素のみのリストとなる。演算子が足りず計算の途中ならば複数の整数がリストに残る。数値が足りず演算が実行できないときや文字列が演算子でも数値でもないときはNothing値を返す。

考えかた

命令リストを先頭から読みながら状態を変化させていくことを考える。

数値

数値を読み込んだらスタックに読み込んだ値を追加する。

演算子

演算子を読み込んだらスタックのうえふたつの数値に演算を適用しスタックにもどす。数値はさきにはいったものがスタックの下にあることに注意する。演算の第1引数にするのは下のほうの値で第2引数が上の値となる。

コード

準備

import Text.Read

演算子表

operators :: [(String, Integer -> Integer -> Integer)]
operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

関数rpolishIter

関数rplishIterは第1引数に蓄積変数として数値リストをとる。これをスタックとして使う。

第1引数に数値リストをとり第2引数に命令のリストをとる。返り値は数値リストとなる。数値リストはエラーに対応するためにMaybe値とする。

rpolishIter :: Maybe [Integer] -> [String] -> Maybe [Integer]

命令リストが空のとき

命令リストが空ならばそれ以上の命令がないということなのでそのときの蓄積変数(スタック)の値が結果の値となる。

rpolishIter mns [] = mns

数値リストのJust, Nothingによる分岐

数値リストがNothingのときは計算に失敗したということなので全体の値もNothingとなる。数値リストがJust値のときは数値リストでnsを束縛し命令列の先頭sと残りssとにわける。

rpolishIter (Just ns) (s : ss) = ...
rpolishIter _ _ = Nothing

演算子か数値か

命令sで演算子リストを検索して演算動作を探す。演算子リストの検索に失敗したら数値としての読み込みを試す。

rpolishIter (Just ns) (s : ss) = case lookup s operators of
Just o -> ...
_ -> ...

数値

数値として読み込めるならば数値リストに値を追加する。そうでないならNothing値を返す。

_ -> rpolishIter (maybe Nothing (Just . (: ns)) $ readMaybe s) ss

その結果を新しいスタックの値として関数rpolishIterに第1引数として与える。蓄積変数の値を変化させ命令リストから先頭を削って同じ関数に与えている。これは引数の値を変化させていくループだ。

演算子

命令が演算子として解釈されるならばまずは数値リストが2つ以上の整数を含んでいることを確認し、先頭の2整数を逆順で演算子に与える。そうでないなら全体の値はNothingとなる。

Just o -> case ns of
y : x : ns' -> rpolishIter (Just $ x `o` y : ns') ss
_ -> Nothing

くりかえしになるが、結果はスタックの新しい値として関数rpolishIterに第1引数として与えられる。蓄積変数と命令列を更新したループとなる。

関数rpolish

第1引数に数値リストの初期値を与える。

rpolish :: [String] -> Maybe [Integer]
rpolish = rpolishIter $ Just []

出来上がり

rpolishIter :: Maybe [Integer] -> [String] -> Maybe [Integer]
rpolishIter mns [] = mns
rpolishIter (Just ns) (s : ss) = case lookup s operators of
Just o -> case ns of
y : x : ns' -> rpolishIter (Just $ x `o` y : ns') ss
_ -> Nothing
_ -> rpolishIter (maybe Nothing (Just . (: ns)) $ readMaybe s) ss
rpolishIter _ _ = Nothing

rpolish :: [String] -> Maybe [Integer]
rpolish = rpolishIter $ Just []

まとめ

蓄積変数を使った反復的処理の例を見た。2変数を使ったループと考えられる。

「ポーランド記法電卓とたたみこみ(右)」へもどる 「逆ポーランド記法電卓とたたみこみ(左)」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics