Stacks- Infix To Postfix Conversion

By using stack, we will convert an infix expression to postfix expression. It is very easy to convert, if the character is an operand ,we will insert directly into the postfix expression. If the character is an operator or parentheses, we will push them into the stack and according to their precedence and rules, insert them in postfix expression.

Let us see the precedence order of the operators

1. ‘+’ or ‘-’

2. ‘*’ or ‘/’

3. ‘^’

The following are the rules to be applied for the conversion

• If the character is ‘( ’{left parentheses} , push the operators into the stack irrespective of the precedence of the operators, which are left to ‘(’ .
• > If the character is ‘)’ {right parentheses} , pop all the operators from the stack and insert them into the postfix expression until it reaches ‘(’ in the stack.
• Do not insert ‘( ’ or ‘)’ in the expression.
• If the precedence of the character is greater than precedence of operator at top, push into the stack.
• If the precedence of the character is lesser than or equal to the precedence of operator at top elements , pop the operators until the character’s precedence is greater than top’s precedence then push the character into the stack.
• The popped operators should be inserted into the postfix, respectively the order they popped out.

Algorithm to Convert infix to postfix:

1. Start
2. Read the infix expression.
3. Check character by character in infix expression.
4. If the character is alphabet or number ,directly insert into the postfix expression .
5. If the character is ‘(’ , push the operator into the stack.
6. If the character is ‘+’ or ‘-’ or ‘*’ or ‘/’ or ‘^’ then check the precedence of the character and the precedence of top element in the stack.
7. If the precedence of the character is greater than the precedence of the top element, push the character .
8. Else pop the operators continuously till the precedence of character is greater than the precedence of the top element and then push the character in to the stack.
9. The popped elements should be inserted in to the postfix expression.
10. Continue the above process until the pointer reaches the last character.
11. Pop all the remaining operators in the stack and insert into the postfix.
12. Write postfix.
13. Stop.

The above is the algorithmic approach. Now we will see programic approach:

C:

This is all about conversion of an infix expression to postfix expression.

In the next story we will see the conversion of infix expression to prefix expression.

Thank you.