In infix to postfix conversion we will use stack data structure. We have operator’s stack, output’s stack and one input string. Operator’s stack works as FILO(First In Last Out). Output’s stack works as FIFO (First In First Out).
Algorithm to convert infix to postfix
Iterate the given expression from left to right, one character at a time
Step 1: If the scanned character is an operand, put it into postfix expression.
Step 2: If the scanned character is an operator and operator's stack is empty, push operator into operators' stack.
Step 3: If the operator's stack is not empty, there may be following possibilities.
If the precedence of scanned operator is greater than the top most operator of operator's stack, push this operator into operator 's stack.
If the precedence of scanned operator is less than the top most operator of operator's stack, pop the operators from operator's stack until we find a low precedence operator than the scanned character.
If the precedence of scanned operator is equal then check the associativity of the operator. If associativity left to right then pop the operators from stack until we find a low precedence operator. If associativity right to left then simply put into stack.
If the scanned character is opening round bracket ( '(' ), push it into operator's stack.
If the scanned character is closing round bracket ( ')' ), pop out operators from operator's stack until we find an opening bracket ('(' ).
Repeat Step 1,2 and 3 till expression has character
Step 4: Now pop out all the remaining operators from the operator's stack and push into postfix expression.
Step 5: Exit
Example of Infix to Postfix Conversion
Infix Expression : A+(B*C+D)/E
| Input Token | Stack | Postfix Expression | Action |
| A | A | Add A into expression string | |
| + | + | A | Push ‘+’ into stack |
| ( | +( | A | Push ( into stack |
| B | +( | AB | Add B into expression string |
| * | +(* | AB | Push ‘*’ into stack |
| C | +(* | ABC | Add C into expression string |
| + | +(+ | ABC* | ‘+’ operator has less precedence than ‘*’, so pop * and add to expression string |
| D | +(+ | ABC*D | Add D into expression string |
| ) | + | ABC*D+ | ) has come so pop + and add it to expression string |
| / | +/ | ABC*D+ | / has higher precedence than + so push / into stack |
| E | +/ | ABC*D+E/+ | Add E into expression string and pop all operators one by one from stack and add it to expression string |
[wpusb]