To convert Infix to prefix using the stack, first reverse the infix expression and at last again reverse the output expression to get prefix expression. 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).
Infix to Prefix Conversion Algorithm
- Iterate the given expression from left to right, one character at a time.
Step 1:
- Reverse the given expression.
Step 2:
- If the scanned character is an operand, put it into the prefix expression.
Step 3:
- If the scanned character is an operator and the operator’s stack is empty, push the operator into the operator’s stack.
Step 4:
- If the operator’s stack is not empty, check the following possibilities:
- If the precedence of the scanned operator is greater than the topmost operator of the operator’s stack, push this operator into the stack.
- If the precedence of the scanned operator is less, pop operators from the operator’s stack until you find a lower precedence operator.
- If the precedence is equal, then:
- Check the associativity of the operator.
- If left-to-right, simply push into the stack.
- If right-to-left, pop operators from the stack until a lower precedence operator is found.
- If the scanned character is an opening bracket
(, push it into the operator’s stack. - If the scanned character is a closing bracket
), pop operators from the stack until an opening bracket(is found.
- Repeat Steps 2, 3, and 4 until all characters of the expression are processed.
Step 5:
- Pop out all the remaining operators from the operator’s stack and append them to the prefix expression.
Step 6:
- Exit
Infix to Prefix conversion example
Infix Expression: (A+B)+C-(D-E)^F
First reverse the given infix expression
After Reversing: F^)E-D(-C+)B+A(
| Input Token | Stack | Expression | Action |
| F | F | Add F into expression string | |
| ^ | ^ | F | Push ‘^’ into stack |
| ) | ^) | FE | Push ‘)’ into stack |
| E | ^) | FE | Add E into expression string |
| – | ^)- | FE | Push ‘-‘ into stack |
| D | ^)- | FED | Add D into expression string |
| ( | ^)- | FED- | ‘(‘ Pair matched, so pop operator ‘-‘ |
| – | – | FED-^ | ‘-‘ operator has less precedence than ‘^’, so pop ^ and add to expression string |
| C | – | FED-^C | Add C into expression string |
| + | + | FED-^C- | Pop – because – and + have left associativity |
| ) | +) | FED-^C- | Push ‘)’ into stack |
| B | +) | FED-^C-B | Add B into expression string |
| + | +)+ | FED-^C-B | Push ‘+’ into stack |
| A | +)+ | FED-^C-BA | Add A into expression string |
| ( | + | FED-^C-BA+ | ‘(‘ Pair matched, so pop operator ‘+’ |
| FED-^C-BA++ | Pop all operators one by one as we have reached end of the expression |
Now reverse the expression to get prefix expression ++AB-C^-DEF
What did you think?