How to convert infix expression to postfix expression using stack?, Algorithm for converting infix expression to postfix expression, solved examples for postfix conversion
Algorithm - Infix to Postfix using Stack
- 1: Read the input string from left to right character by character.
- 2: If the input character is an operand, then send it to the output.
- 3: If the input character is an operator, then call PUSH operation based on the following;
- 3a: If the stack is empty, then PUSH the character into the stack.
- 3b: If the stack is not empty, then compare the priority of the top element in the stack with that of the new operator to be pushed.
- If the new operator is with higher priority, then PUSH the operator into stack.
- If the new operator is with lower priority, then POP the top element from the stack and add it to the output.
- Repeat 3b until stack is empty or the top element is with lower priority than the operator to be pushed.
- 4: Repeat steps 2 to 3b for entire input string.
- 5: If you have reached the end of the input string and the stack is empty then the output is your postfix expression.
Infix Expression: A + B * C
Input
character
|
Operation
|
Stack
|
Output
|
A
|
Empty
|
A
|
|
+
|
PUSH
|
+
|
A
|
B
|
+
|
AB
|
|
*
|
PUSH
|
+*
|
AB
|
C
|
+*
|
ABC
|
|
End of input
|
POP
|
ABC*+
|
Postfix expression: ABC*+
******************
Go to Data structures home page
Go to Programs for implementing data structures page