infix notation ===> 2 + 3
(polish)prefix notation ===> + 2 3
(polish)postfix notation ===> 2 3 +

ex. 7 + ( 3*5 ) -4
prefix
-+7 * 3 5 4
postfix
7 3 5 * + 4 -

• advantage :

  prefix and postfix notation requires no parenthese

• postfix is easier than prefix in terms os expresion evaluation

  ex.

  (( 3x + 5) - 8 z) - 9y /5
  
  (((3*x) + 5) - (8*z)) - ((9*y)/5))
  
  prefix    - - + * 3 x 5 * 8 z / *9 y 5
  
  postfix   3 x *5 + 8 z * - 9 y * 5 / -
  

3 x * 5 + 8 z * - 9 y * 5 / -

1. some assumptions
   1. numbers separating by space
   2. no negative number

2. one stack : number stack

       there  is no need for operation stack
   because
          each operation is used when it is read
   

   eq. //ref. 7-10 on p.334

   

how to translate infix expression to postfix expression

ie.

((( A + 7 ) * ( B / C )) - ( 2 * D ))

===> A 7 + B C / * 2 D * -

1. fully parenthesized in fix expression

   
   

   Idea :

   move the operation to the location of crresponding
   and remore all parenthesis.

   eq.

   

   ===> 3 x * 5 + 8 z * - 9 y * 5 / -

   how : use stack to store " ( " and operator

   ex. ((( A + 7 ) * ( B / C ) ) - ( 2 * D ))
   

   

   eac " ) " triggers on pop action on stack
   

2. not fully parenthesized infix expression
   

   2 * ( A - B ) + 3 + C
   

   1. Strategy : used the precedence of operator
      ex. convent
      3 * x + ( y - 7 ) - z

      

   2. precedence
      1. ( ) first
      2. * / first + - later
      3. from left to right for * / or + -

   3. homework :
      1. A + 7 * ( B - C ) - 2 * D

      2. 3 / A + ( B + 12 ) - C