= Solution
Use an auxiliary <parser> that returns both a value and the unconsumed suffix. The arithmetic helper is:
``
applyOp :: Op -> Int -> Int -> Int
applyOp Add x y = x + y
applyOp Sub x y = x - y
applyOp Mul x y = x * y
applyOp Div x y = x `div` y
``
For the integer-valued expression language, this chooses <integer division> with `div`'s rounding convention. The result is evaluated under the intended arithmetic model; bounded-`Int` overflow is separate from parsing.
``
evalP :: Polish -> Int
evalP input =
case parse input of
(value, []) -> value
_ -> error "trailing tokens"
where
parse :: Polish -> (Int, Polish)
parse [] = error "missing operand"
parse (Number n : rest) = (n, rest)
parse (Operator op : rest) =
let (left, rest1) = parse rest
(right, rest2) = parse rest1
in (applyOp op left right, rest2)
``
A number consumes one token. An operator consumes the two successive complete expressions that follow it, so nested operators are handled by <recursion>. <Structural induction> on the expression proves that `parse` consumes exactly its <Polish notation> and returns its value. Keeping the suffix is essential: neither operand has a fixed token count. Division by zero need not be treated separately under the stated input convention.
Back to article page
