Use a sum type whose two constructors distinguish a number from an operator:Then the supplied
data Elem = Number Int | Operator OpPolish and RPolish aliases can both be lists of Elem. Constructor tags distinguish tokens without attempting to encode operators as special numeric values. The numeric type Int agrees with the supplied abstract syntax tree.Pass an already constructed suffix through the traversal:The invariant is that
convert :: Expr -> RPolish
convert e = go e []
where
go :: Expr -> RPolish -> RPolish
go (Num n) rest = Number n : rest
go (App op left right) rest =
go left (go right (Operator op : rest))go e rest is the reverse Polish notation of e followed by rest. It holds at a numeric leaf. At an application, the result is the left subtree's tokens, then the right subtree's tokens, then the operator, then rest, exactly as required.Each vertex of the abstract syntax tree creates one output list cell and performs constant local work. Thus producing the complete result takes time for an expression with vertices. No repeated list concatenation copies a previously traversed subtree. This suffix-passing construction is a difference list traversal.
Use an auxiliary parser that returns both a value and the unconsumed suffix. The arithmetic helper is:For the integer-valued expression language, this chooses integer division with 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
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` ydiv'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)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.Maintain a stack of values of the complete subexpressions encountered so far, with the newest value at its head: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 right operand, so preserving the order in
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"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. Articles by others on the same topic
There are currently no matching articles.