Write an algorithm to evaluate postfix expression. Give a suitable example.

Let ‘operandstk’ be an empty stack then the algorithm to evaluate postfix expression is:

1.   Start

2.   Input a postfix expression in the ‘postfix’ string.

3.   for each character ‘ch’ of  ‘postfix’ string

if(‘ch’ is an operand)

  push ‘ch’ in ‘operandstk’

else

   {

     opnd2= pop an operand from ‘operandstk’

     opnd1= pop an operand from ‘operandstk’

     value= result of applying ‘ch’ in ‘opnd1’ and ‘opnd2’

     push ‘value’ to ‘operandstk’

   }

4.   pop the top element of the stack ‘operandstk’ which is the required result.

5.   Exit

TRACING THE ALGORITHM:

postfix expression: 6 2 3 + - 3 8 2 / + * 2 $ 3 +

ch	opnd1	opnd2	value	operandstk
6				6
2				6,2
3				6,2,3
+	2	3	5	6,5
-	6	5	1	1
3	6	5	1	1,3
8	6	5	1	1,3,8
2	6	5	1	1,3,8,2
/	8	2	4	1,3,4
+	3	4	7	1,7
*	1	7	7	7
2	1	7	7	7,2
$	7	2	49	49
3	7	2	49	49,3
+	49	3	52	52

∴The result of the postfix expression: 6 2 3 + - 3 8 2 / + * 2 $ 3 +

 is pop(operandstk)= 52.