Infix to Postfix Conversion in C [Program and Algorithm]

In this tutorial you will learn about program and algorithm for infix to postfix conversion in C with an example.

In infix notation or expression operators are written in between the operands while in postfix notation every operator follows all of its operands.

 
Example:
Infix Expression: 5+3*2
Postfix Expression: 5 3 2*+.
 

Infix to Postfix Conversion Algorithm

Let Q be any infix expression and we have to convert it to postfix expression P. For this the following procedure will be followed.
 
1. Push left parenthesis onto STACK and add right parenthesis at the end of Q.
 
2. Scan Q from left to right and repeat step 3 to 6 for each element of Q until the STACK is empty.
 
3. If an operand is encountered add it to P.
 
4. If a left parenthesis is encountered push it onto the STACK.
 
5. If an operator is encountered, then
  • Repeatedly pop from STACK and add to P each operator
    which has same precedence as or higher precedence than the operator
    encountered.
  • Push the encountered operator onto the STACK.
6. If a right parenthesis is encountered, then
  • Repeatedly pop from the STACK and add to P each operator
    until a left parenthesis is encountered.
  • Remove the left parenthesis; do not add it to P.
7. Exit
 
 
An example of converting infix expression into postfix form, showing stack status after every step is given below. Here RPN stands for reverse polish notation (postfix notation).
 
An example of converting infix expression into postfix form, showing stack status after every step

Program for Infix to Postfix Conversion in C

 

C Program and Algorithm for Conversion of an Expression from Infix to Postfix
 
If you have any doubts regarding above infix to postfix conversion in C tutorial then feel free to comment below.

 

3 thoughts on “Infix to Postfix Conversion in C [Program and Algorithm]

  1. Shivakrishna

    Good article.

    Few observations i made:
    Precedence is taken care but the asscociativity is not taken care. A+B-C will give o/p ABC-+, where as actual o/p would have been AB+C- due to left to right associativity property.

    Thanks,
    Shiva

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *