DS – Infix to Postfix Conversion

Algorithm to convert Infix to Postfix using STACK:

1. Read next element in the input expression.
2. If it is an operand, output it.
3. If it is an opening parenthesis, push on to the Stack.
4. If it is an operator, then
   1. If the Stack is empty, push operator on Stack
   1. If the Top of stack is Opening parenthesis, push operator on to the Stack.
   1. If the operator has higher priority than top of the Stack, push operator on to the Stack else Pop operator from the Stack and output it, repeat Step 4
5. If the is a closing parenthesis, pop operators from stack and output them until opening parenthesis is encountered. POP and discard opening parenthesis.
6. If there is more input Go to step 1.
7. If no more input, unstuck all operators from stack and output.

Note: Prefix and Postfix expressions do not contain parenthesis. In conversion part, we remove parenthesis using algorithm rules.

Expression: 2*3/(2-1) + 5*(4-1)