Evaluation of Arithmetic Expressions


Parsing


Any arithmetic expression can be expressed in three types of 
 expression froms namelythe infix , prefix and potfix forms..

These correspond to the diffrent order of flattening of binary trees.
Namely the inorder preorder and postorder forms..


given a binary tree of the following representation

data Tree a = Nil|Node (Tree a) a (Tree a)

Flattening of the tree into a list can be done in three orders


   flatten::Tree a->[a]
   flatten [Nil] = []


1. Inorder

   flatten (Node t1 val t2) = (flatten t1)++val++(flatten t2)
  

2. Preorder 

   flatten (Node t1 val t2) = val++(flatten t1)++(flatten t2)

3. Postorder
  
   flatten (Node t1 val t2) = (flatten t1)++(flatten t2)++val



Similarly for arithmetic expression

Given the expression 3+4*7+8

1.Infix 
 
  3+((4*7)+8)
  or
  ((3+4)*7)+8
  
2.Prefix

  +3+*478
  or
  ++3*478

3.Postfix 
  
  347*8++
  or
  3*47+8+

Note that prefix and postfix forms do away with brackets because there is no ambiguity in evauation.. Prefix and postix forms can be evaluated using stacks