Interview Question: Write code to convert In-Fix to postfix notation

Given an arithmetic expression in in-fix notation. Write code to convert that algorithm in corresponding post-fix notation. For example:

Infix             postfix
------            --------
a+b               ab+
(a+b)*c           ab+c*
a+b*c             abc*+
a*(b+c)-d/e       abc+*de/-

To solve this expression, we need a Stack. Let the Infix expression be in a String, and postfix expression will go in another string.

Initially the Stack will be empty and postfix expression will also be empty.

1. Read the tokens(characters) from the infix string one at a time from left to right
2. If token is an operand, add it to the Postfix string.
3. If token is a Left parentheses, Push it on to the Stack
4. If the token is a Right parentheses
1. Repeatedly Pop the stack and add the poped out token in to postfix string until a left parenthesis is encountered.
2. Remove left parenthesis from the stack and ignore it
5. If token is an operator
1. If the stack is empty push the operator in to the stack      
2. If the stack is not empty compare the precedence of the operator with the element on top of the stack
1. If the operator in the stack has higher precedence than the token Pop the stack and add the poped out element in to the string S. else Push the operator in to the stack                  
2. Repeat this step until the stack is not empty or the operator in the stack has higher precedence than the token        
6. Repeat this step till all the characters are read.
7. After all the characters are read and the stack is not empty then Pop the stack and add the tokens to the string S
8. Return the Postfix string S

Code:

Try writing it yourself. If you get into problems, I will write a separate post for the code.


---------------------------------------------------------------------------

Interview Questions Archive:

         To see all the questions in the category click here...