Infix to Postfix using Stack :
If ( ‘(‘ )
push in stack
If ( ‘)‘ )
pop until left parenthesis is popped
If ( operator )
1. Lower priority (w.r.t to Stack Top ) is in input then pop
2. Higher priority input in input then push
3. Same priority then pop
If ( operand )
ignore
Now using the above algorithm , let us evaluate A + B * (C + D) / F + D * E :
Steps |
Stack Element |
Output |
Step 1 : Ignore A (as it’s operand )
|
|
A |
Step 2: Since Stack is empty push ‘+’
|
+ |
A |
Step 3: Ignore B (as it’s operand )
|
|
AB |
Step 4 : * has Higher priority than + so push
|
* + |
AB |
Step 5 : push ‘ ( ‘ in stack
|
( * + |
AB |
Step 6 : Ignore C (as it’s operand )
|
( * + |
ABC |
Step 7 : push ‘+’ in stack
|
+ ( * + |
ABC |
Step 8 : Ignore D (as it’s operand )
|
+ ( * + |
ABCD |
Step 9 : pop until left parenthesis is popped
|
*+ |
ABCD+ |
Step 10 : ‘/’ has same priority as ‘*’ , so pop ‘*’ and push ‘/’ into stack as ‘/’ has higher priority than ‘+’
|
/+ |
ABCD+* |
Step 11 : Ignore F (as it’s operand )
|
/+ |
ABCD+*F |
Step 12 : ‘+’ has lower priority than ‘/’ , so pop ’/’ and push ’+’
|
++ |
ABCD+*F/ |
Step 13 : Ignore D (as it’s operand )
|
++ |
ABCD+*F/D |
Step 14 : push ‘*’ as it has higher preceedence than ‘+’
|
*++ |
ABCD+*F/D |
Step 15 : Ignore E (as it’s operand )
|
*++ |
ABCD+*F/DE |
Step 16 : We have ‘*’ , ‘+’ , ‘+’ in the stack . Just empty the stack
|
|
ABCD+*F/DE*++ |
Correct Ans : Option ( B ) ABCD+*F/DE*++