Evaluation of Postfix Expression

Convert infix expression 8*(6+2)-16/4 into postfix using above points

Token	ICP	Stack Contents	ISP	Output	Remarks
		!	-1		Puts ! in stack
8		!	-1	8
*	2	!*	2	8
(	4	!*(	0	8
6				86
+	1	!*(+	1	86
2				862
)	-	!*	2	862+
-	1	!-	1	862+*
16		!-	1	862+*16
/	2	!-/	2	862+*16
4		!-/	2	862+*164
#		!	-1	862+*164/-

Evaluation of Postfix :

            To evaluate postfix expression, we scan the expression from left to right.  We assume that postfix expression ends with ‘#’.

Case 1:  while scanning the expression from left to right, if operand is

              encountered push into the stack.

Case 2:  if operator is encountered, delete two elements from the    

              stack. Perform the indicated operation on these two element 

              such that first  element deleted is a right operand and second 

              element deleted is the left operand.  Push the result into the  

              stack.

Case 3: if ‘#’ is encountered then it indicates the end of the postfix

             expression is reached.  And the result is present in the stack.

Consider the postfix expression  8,6,2,+,*,16,4,/,-

		2				4
	6	6	8		16	16	4
8	8	8	8	64	64	64	64	60

The result of postfix expression is 60.

Procedure to  Postfix Expression

Procedure PostfixEvaluate(e: Expression)

  x: Token

  y,z,k : integers

begin

     Top=0;                         { Initialize the stack }

      x=NextToken(e);         { gets first token  }

      while (x<>’#’)

       begin

           if x is operand then

                push(x);

           else

             begin

                 y=pop();

                 z=pop();

                 k= z x y;

                 push(k);

             end

           x=NextToken(e);

       end 

end

Converting postfix to infix is same as evaluation of postfix except that evaluation is not performed on deleted element.

Consider a postfix expression 12,7,3,-,/,2,1,5,+,*,+

							5
		3				1	1
	7	7	(7-3)		2	2	2
12	12	12	12	12/(7-3)	12/(7-3)	12/(7-3)	12/(7-3)

(1+5)
2	(2*(1+5))
12/(7-3)	12/(7-3)	(12/(7-3)) + (2*(1+5))

Infix expression is (12/(7-3)) + (2*(1+5))

							5
		3				1	1
	7	7	4		2	2	2
12	12	12	12	3	3	3	3

6
2	12
3	3	15

            The result of postfix expression is 15.