Application of stacks – evaluation of arithmetic expressions

Application of stacks – evaluation of arithmetic expressions

• 
  Stacks are useful for backtracking problems (eg: navigating a maze)  previous states are recorded so that algorithmic progress may occur from them at a later time
  
• 
  Stacks are the implementation technique used for embodying backtracking
  
• 
  some compilers convert the infix expressions used in programming to postfix expressions, and generate machine code to evaluate them.
  
  • 
    In infix the operator is written between the operands:
    A * B + (C - D / E)
    
  • 
    In postfix the operator is written after the operands:
    A B * C D E / - +
    
  • 
    In postfix notation, ()s are needed. ie. the evaluation is unambiguous and does not rely on operator precedence.
    

• 
  Converting infix to postfix:
  
  • 
    By hand, add ()s to all subexpressions, then move the operators to the position of the corresponding ), and delete (s. eg.
    

((A * B) + (C - (D / E)))

((A B* (C (D E/-+

A B* C D E/-+

• 
  Here is an algorithm that uses backtracking via a stack for converting infix to postfix:
  
  • 
    the stack contains the elements: + - * / (
    
  • 
    this algorithm can be augmented to detect incorrect syntax
    

• 
  eg run: (top of the stack is the leftmost element)
  

Infix	Stack	Postfix
A * B + (C - D / E)	Empty
* B + (C - D / E)	Empty	A
B + (C - D / E)	*	A
+ (C - D / E)	*	AB
(C - D / E)	+	AB*
C - D / E)	(+	AB*
- D / E)	(+	AB*C
D / E)	-(+	AB*C
/ E)	-(+	AB*CD
E)	/-(+	AB*CD
)	/-(+	AB*CDE
Empty	+	AB*CDE/-
Empty	Empty	AB*CDE/-+

• 
  Evaluating postfix:
  
  • 
    once an expressions has been parsed from infix to postfix, another backtracking algorithm is used to evaluate the expression
    
  • 
    the contents of the stack here are: variable names & values
    

• 
  eg: A = 5, B = 3, C = 6, D = 8, E = 2
  

  Postfix	Stack
  AB*CDE/-+	Empty
  B*CDE/-+	A
  *CDE/-+	BA
  CDE/-+	15
  DE/-+	C 15
  E/-+	DC 15
  /-+	EDC 15
  -+	4 C 15
  +	2 15
  Empty	17

• 
  And the answer is 17.