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.

Ancestors (11)

  1. 2
  2. Functional programming, design and analysis of algorithms
  3. 2015
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version