Reverse Polish Notation

INF1 FP Exam Dec 2013

-- This is from the Morning Exam

rpn :: Expr -> [String]
rpn X = ["X"]
rpn (Const n) = [show n]
rpn (a :+: b) = (rpn a) ++ (rpn b) ++ ["+"]
rpn (a :*: b) = (rpn a) ++ (rpn b) ++ ["*"]
rpn (Neg a)   = (rpn a) ++ ["-"]
-- NB: I can't really remember how negation was 
-- represented, this might not be it...



evalrpn :: [String] -> Int -> Int
evalrpn rpn x = head $ doe rpn x []
  where
    doe :: [String] -> Int -> [Int] -> [Int]
    doe []       x hold       = hold
    doe ("X":rs) x hold       = doe rs x (x:hold)
    doe ("*":rs) x (a:b:hold) = doe rs x ((a*b):hold)
    doe ("+":rs) x (a:b:hold) = doe rs x ((a+b):hold)
    doe ("-":rs) x (a:hold)   = doe rs x ((-a):hold)
    doe (c:rs)   x hold       = doe rs x ((read c :: Int):hold)