Algorithm for converting infix expression to postfix expression

Algorithm

POSTFIX (Q, P)

Suppose Q is an expression written in infix notation. This algorithm finds equivalent postfix expression P.

1) Push ‘(‘onto stack, and add ‘)’ to the end of Q.
2) Scan Q from left to right and repeat step3 to step6 for each symbol of Q until the stack is empty.
3) If an operand is encountered, add it to P.
4) If an left parenthesis is encountered, push it onto stack
5) If an operator  encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) which has same or higher precedence than.
b) Push  onto stack.
6) If an right parenthesis encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) until left parenthesis is encountered.
b) Remove left parenthesis from stack.
[Do not add left parenthesis to P]
7) Exit.