Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 2 / c / Solution 2026-10-31
View more
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.
Read the full article
Reverse Polish notation 2026-10-31
View more
Place each operator after its operands. A binary application encodes its first subtree, then its second subtree, then the operator, a postorder traversal. A stack machine evaluates the tokens in one pass, popping the right operand before the left one. Reversing a Polish notation token list also reverses operand order: prefix subtraction - a b would become b a - rather than the required a b -.
Read the full article