Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-03

逆ポーランド記法電卓

07:18

苦労して作ったら、案の定ずっと良いのがあった。涙目。


自作版。訳あって Rational で結果を返したかったので。

import Char (isDigit,digitToInt,isSpace)
import Ratio
import System
import Debug.Trace

stringToRatio :: String -> Rational
stringToRatio xs = (foldl1 (\s x -> s*10 + x) $ map (toInteger.digitToInt) xs) % 1

isOp :: Char -> Bool
isOp x = x `elem` "+-*/"

toOp :: Char -> (Rational -> Rational -> Rational)
toOp '+' = (+)
toOp '-' = (-)
toOp '*' = (*)
toOp '/' = (/)

dropWhileSpace = dropWhile isSpace

parse :: ([Rational],String) -> ([Rational],String)
parse (mem, []) = (mem, [])
parse (mem, (x:xs))
    | (trace.show) (mem,x) False = (mem,x:xs)   -- for debugging
    | isOp x    = let ([arg2,arg1],mem') = splitAt 2 mem
                      op = toOp x
                   in parse ( (op arg1 arg2):mem', dropWhileSpace xs)
    | isDigit x = let (ns,xs') = span isDigit xs
                   in parse ( (stringToRatio (x:ns)):mem, dropWhileSpace xs')

poland :: String -> Rational
poland str = head $ fst $ parse ([], dropWhileSpace str)

main = do
        str  <-  getLine
        print $ poland str 

実行。

% runghc poland.hs
1 2 + 3 4 + *
([],'1')
([1%1],'2')
([2%1,1%1],'+')
([3%1],'3')
([3%1,3%1],'4')
([4%1,3%1,3%1],'+')
([7%1,3%1],'*')
21%1

Wikipedia 版

calc :: String -> [Float]
calc = foldl f [] . words
  where 
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f xs y = read y : xs

すごい簡潔。。words という素晴しい関数があったのか。read y : xs の部分も思いつかなかったなあ。。

って全部やん。


次の目標。禁則処理をちゃんとしたい。

自分のコードで parse の返り値を Maybe にすると、再帰部分まで書き換えるのが大変… ここは素直に Wikipedia 版を使おうかな。


とりあえずやってみた

import Char (isDigit)
import Ratio
import System

calc :: String -> Maybe [Rational]
calc = foldl poland (Just []) . words
  where
    poland :: Maybe [Rational] -> String -> Maybe [Rational]
    poland stack string = stack >>= flip f string -- (\stk -> f stk string) 

    f :: [Rational] -> String -> Maybe [Rational]
    f (x:y:zs) "+" = Just (y+x:zs)
    f (x:y:zs) "-" = Just (y-x:zs)
    f (x:y:zs) "*" = Just (y*x:zs)
    f (x:y:zs) "/" = Just (y/x:zs)
    f xs y         = if all isDigit y
                then Just (toRational (read y) : xs)
                else Nothing

main = do
        str  <-  getLine
        print $ calc str

Wikipedia 版で、禁則処理を入れるとこうなるのかなあ。気になる点が、

  1. f 関数の中で "Just" を使いすぎてて汚い。
  2. foldl に渡す初期値を Just [] としなければいけないのはダサい。

1番目は、f を純関数 (というのか?) にして禁則処理を別で定義すればいけるんだろうか?

2番目は難しそう。foldl の性質上、返る値が Maybe なら入れる値も Maybe でないといけない。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090603
 |