Home > Computer science and math, English > Reverse Polish notation calculator in Haskell

Reverse Polish notation calculator in Haskell

December 22nd, 2008 Leave a comment Go to comments

Just a few lines of code, written when I was slightly bored.

module Main where
 
data Token = Plus | Minus | Divide | Times | Num Integer
 
rpnEval :: [Token] -> Integer
rpnEval = rpnEval' [] where
		rpnEval' (i:s) [] = i
		rpnEval' s ((Num i):t) = rpnEval' (i:s) t
		rpnEval' (a:b:s) (op:t) = rpnEval' ((evalOp op a b):s) t
 
		evalOp Plus = (+)
		evalOp Minus = (-)
		evalOp Times = (*)
		evalOp Divide = div
 
toToken :: String -> Token
toToken "+" = Plus
toToken "-" = Minus
toToken "*" = Times
toToken "/" = Divide
toToken s = Num (read s)
 
main = do
	l <- getContents
	mapM print $ map (rpnEval . (map toToken) . words) (lines l)

Update: See comments for better solution.

Categories: Computer science and math, English Tags: ,
  1. anon
    January 25th, 2009 at 15:08 | #1
    Reply | Quote

    Nice:) A bit shorter version:

    module Main where

    data Token = Binary (Integer -> Integer -> Integer) | Num Integer

    rpnEval :: [Token] -> Integer
    rpnEval = rpnEval’ [] where
    rpnEval’ (i:s) [] = i
    rpnEval’ s ((Num i):t) = rpnEval’ (i:s) t
    rpnEval’ (a:b:s) ((Binary op):t) = rpnEval’ ((op a b):s) t

    toToken :: String -> Token
    toToken “+” = Binary (+)
    toToken “-” = Binary (-)
    toToken “*” = Binary (*)
    toToken “/” = Binary div
    toToken s = Num (read s)

    main = do
    l <- getContents
    mapM print $ map (rpnEval . (map toToken) . words) (lines l)

  2. ponton
    January 25th, 2009 at 16:28 | #2
    Reply | Quote

    Thanks. :)

  3. Reader
    January 28th, 2009 at 04:21 | #3
    Reply | Quote

    Great! Thank you very much!
    I always wanted to write in my site something like that. Can I take part of your post to my site?
    Of course, I will add backlink?

    Regards, Timur I. Alhimenkov

    • ponton
      January 28th, 2009 at 04:46 | #4
      Reply | Quote

      You’re very welcome. All my source codes are under GPL and blog content under Creative Commons BY-SA.

  4. Tener
    February 11th, 2009 at 13:12 | #5
    Reply | Quote

    Those lines:
    > main = do
    > l mapM print $ map (rpnEval . (map toToken) . words) (lines l)
    Can be shortened to:
    > main = interact (unlines . map (rpnEval . (map toToken) . words) . lines))

    Haskell FTW! :-)

  5. ponton
    February 16th, 2009 at 01:58 | #6
    Reply | Quote

    Dzięki za przypomnienie o ,,interact”. ;) Oczywiście jeszcze po ,,rpnEval” trzeba zrobić ,,show”, bo ,,unlines” bierze listę napisów, a nie liczb.

  6. monoidal
    May 6th, 2010 at 17:38 | #7
    Reply | Quote

    Wikipedia gives on http://en.wikipedia.org/wiki/Haskell_features#More_complex_examples version using fold:

    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

    Using a view pattern you can obtain a minimalistic version:

    {-# LANGUAGE ViewPatterns #-}
    module Main where

    main = interact $ unlines . map (show . head . foldl f [] . words) . lines
    where
    f (x:y:zs) (operator -> Just o) = (o x y):zs
    f xs y = read y : xs
    operator o = lookup o [("+",(+)),("-",(-)),("*",(*)),("/",div)]

  1. No trackbacks yet.