A basic parser written in Haskell. Written as a learning exercise.

parse.hs

import Data.List


-- Evaluate a postfix expression
evalPostfix :: (Num a, Read a) => String -> a
evalPostfix = head . foldl comb [] . words
  where
    comb (x:y:ys) "*" = (x * y) : ys
    comb (x:y:ys) "+" = (x + y) : ys
    comb (x:y:ys) "-" = (y - x) : ys
    comb xs s = read s : xs


-- Apply the shunting-yard algorithm to turn an infix expression
-- into a postfix expression.
shunt :: [String] -> [String] -> [String] -> [String]
shunt o p [] = (reverse o) ++ p
shunt o [] (x:xs)
    | x `elem` ["*", "+", "-", "("] = shunt o [x] xs
    | x == ")" = error "mismatched parenthesis"
    | otherwise = shunt (x:o) [] xs
shunt o (p:ps) (x:xs)
    | x == "(" = shunt o (x:p:ps) xs
    | x == ")" = case (span (/= "(") (p:ps)) of
        (as, b:bs) -> shunt (as ++ o) bs xs
    | x == "*" = shunt o (x:p:ps) xs
    | x `elem` ["+", "-"] = case (p) of
        "*" -> shunt (p:o) (x:ps) xs
        "(" -> shunt o (x:p:ps) xs
        otherwise -> shunt (p:o) (x:ps) xs
    | otherwise = shunt (x:o) (p:ps) xs


-- | Convert an infix expression to postfix
toPostfix :: String -> String
toPostfix = intercalate " " . shunt [] [] . words


-- | Evaluate an infix expression
-- Note that parenthesis must have a space on either
-- RIGHT: 1 - ( 2 + 3 )
-- WRONG: 1 - (2 + 3)
eval :: (Num a, Read a) => String -> a
eval = evalPostfix . toPostfix