Convert the infix expression to postfix expression using stack data structure. Infix to postfix conversion explained step-by-step. Infix to postfix conversion using stack example
Convert the following infix expression into postfix expression
using stack data structure; show the steps involved;
(A+B)*C-D
Solution:
At the starting of this algorithm;
- Input string: A+B*C-D
- Stack is empty
- Output is NULL
Input character
|
Operation
|
Stack
|
Output
|
Description
|
A
|
A
|
The input character is an operand. So send
the character to output.
|
||
+
|
PUSH
|
+
|
A
|
The input character is an operator. PUSH
the operator onto the stack.
|
B
|
+
|
AB
|
Input is operand, send to output.
|
|
*
|
PUSH
|
+*
|
AB
|
Input is operator, priority of ‘*’ is
higher than ‘+’ in the stack. So PUSH the operator onto the stack.
|
C
|
+*
|
ABC
|
Input is operand, send to output.
|
|
-
|
POP
POP
PUSH
|
+
-
|
ABC*
ABC*+
ABC*+
|
Input is an operator. Priority of ‘-‘ is
lower than the priority of top element ‘*’. Hence, POP ‘*’ and add to the
output.
Yet, ‘–‘ is small or equal in priority
with ‘+’. So POP ‘+’ and add to the output.
Now the stack is empty, so PUSH ‘–‘ onto the
stack.
|
D
|
-
|
ABC*+D
|
Input is an operand, so add it to the
output
|
|
End of input
|
POP
|
ABC*+D-
|
End of input string is reached. POP all
the operators from stack and add to the output.
|
****************