Infix to Postfix Conversion - C Program

The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are -

• Infix notation
• Prefix (Polish) notation
• Postfix (Reverse Polish) notation

Infix notation: 

Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands – "infixed operators" – such as the plus sign in "2 + 2". Infix notation is more difficult to parse by computers than prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ).

Postfix notation:

Postfix notation is a notation for writing arithmetic expressions in which the operands appear before their operators. There are no precedence rules to learn, and parentheses are never needed. Because of this simplicity, some popular hand-held calculators use postfix notation to avoid the complications of the multiple parentheses required in nontrivial infix expressions. You are to write a computer program that simulates how these postfix calculators evaluate expressions.

Procedure for Postfix Conversion:

1. Scan the Infix equation form  left to right.
2. If the scanned character is operand, add it to postfix string.
3. If scanned character is operator and stack is empty, push it to stack.
4. If scanned character is operator and stack is not empty, then compare the precedence of character with the element on the top of stack.
5. If the scanned operator has greater precedence than the top element of stack, then push the scanned operator to the stack.
6. Else, pop the operator from the stack until the precedence of the top element of stack is greater than or equal to the scanned operator. Push scanned operator to the stack.
7.   If the scanned character is an ‘(‘, push it to the stack.
8. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
9. Repeat steps 2-6 until infix expression is scanned. 
10. Pop and output from the stack until it is not empty.

Here is source code of the C Program to convert Infix to postfix using Stack data structure. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

#include<stdio.h>
#include<ctype.h>
#define MAX 50

int top = -1;
char stack[MAX];

void push(char elem);
char pop();
int pre(char elem);

void main()
{
    int i=0, j=0, prec;
    char infx[50], pofx[50], ch;

    printf("Enter the Infix equation: ");
    scanf(" %s", &infx);

    while (infx[i] != '\0')
    {
        if (infx[i] == '(')
        {
            push('(');
        }
        else if (isalnum(infx[i]))
        {
            pofx[j++] = infx[i];
        }
        else if (infx[i] == ')')
        {
            while (stack[top] != '(')
            {
                pofx[j++] = pop();
            }
            pop();
        }
        else
        {
            while (pre(stack[top]) >= pre(infx[i]))
            {
                pofx[j++] = pop();
            }
            push(infx[i]);
        }
        i++;
    }

    while (top != -1)
    {
        pofx[j++] = pop();
    }
    pofx[j] = '\0';

    printf("\nPostfix equation: %s", pofx);
}

void push(char elem)
{
    stack[++top] = elem;
}

char pop()
{
    return (stack[top--]);
}

int pre(char elem)
{
    switch(elem)
    {
        case '#': return 0;
        case '(': return 1;
        case '+':
        case '-': return 2;
        case '*':
        case '/': return 3;
    }
}

Output:

Enter the Infix equation: (A+B)*C-(D-E)*(F+G)

Postfix equation: AB+C*DE-FG+*-

Share on Google Plus

About AlgoStream

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.