= Solution
Maintain a <stack> of values of the complete subexpressions encountered so far, with the newest value at its head:
``
evalRP :: RPolish -> Int
evalRP = finish . foldl push []
where
push :: [Int] -> Elem -> [Int]
push stack (Number n) = n : stack
push (right:left:stack) (Operator op) =
applyOp op left right : stack
push _ (Operator _) = error "missing operand"
finish :: [Int] -> Int
finish [value] = value
finish _ = error "malformed expression"
``
The <left fold> processes tokens in their order. A number pushes its own value; an operator replaces the two latest subexpression values by their combination. The top value is the \b[right] operand, so preserving the order in `applyOp op left right` is necessary for <subtraction> and <division>. Induction on the consumed token prefix proves this <stack machine> invariant. A complete valid expression finishes with exactly one value.
Back to article page
