Q. Write down an algorithm to evaluate an expression given to you in postfix notation. Show the execution of your algorithm for the following given expression.
AB^CD-EF/GH+/+*
Ans.
Algorithm to evaluate Post fix Expression is shown as follows
Opndstk = the empty stack;
/*scan the input string reading one */
/*element at a time into symb */
while ( not end of input){
symb = next input character;
if (symb is an operand)
push (opndstk, symb);
else
{
/* symb is an operator */
opnd 2 = Pop (opnd stk);
opnd 1 = Pop (opnd stk);
value = result of applying symb to opnd 1 and opnd 2;
push (opndstk,value);
}/*end else */
}/*end while */
return (pop (opnd stk));
AB^CD-EF/GH+/+*
|
Symb
|
Opnd1
|
Opnd2
|
Value
|
Opndstk
|
|
A
|
|
|
|
A
|
|
B
|
|
|
|
A,B
|
|
^
|
A
|
B
|
A^B
|
A^B
|
|
C
|
A
|
B
|
A^B
|
A^B,C
|
|
D
|
A
|
B
|
A^B
|
A^B,C,D
|
|
-
|
C
|
D
|
C-D
|
A^B,C-D
|
|
E
|
C
|
D
|
C-D
|
A^B,C-D,E
|
|
F
|
C
|
D
|
C-D
|
A^B,C-D,E,F
|
|
/
|
E
|
F
|
E/F
|
A^B,C-D,E/F
|
|
G
|
E
|
F
|
E/F
|
A^B,C-D,E/F,G
|
|
H
|
E
|
F
|
E/F
|
A^B,C-D,E/F,G,H
|
|
+
|
G
|
H
|
G+H
|
A^B,C-D,E/F,G+H
|
|
/
|
E/F
|
G+H
|
(E/F)/(G+H)
|
A^B,C-D, (E/F) /(G+H)
|
|
+
|
C-D
|
(E/F)/(G+H)
|
(C-D)+(E/F)/(G+H)
|
A^B,(C-D)+
(E/F)/(G+H)
|
|
*
|
A^B
|
(C-
D)+(E/F)/(G+H)
|
A^B*((C-D)+
(E/F)/(G+H))
|
A^B*((C-D)+
(E/F)/(G+H))
|