Infix to Postfix conversion using stack in C -thebytewise

Updated: Oct 14, 2020

One of the applications of Stack is in the conversion of arithmetic expressions in high-level programming languages into machine-readable form. As our computer system can only understand and work on a binary language, it assumes that an arithmetic operation can take place in two operands only e.g., A+B, C*D, D/A, etc. But in our usual form, an arithmetic expression may consist of more than one operator and two operands e.g. (A+B)*C(D/(J+D)).

In this article, we will see how to convert an Infix expression to Postfix expression in a simple and short way.

The conversion is done using C, though it can be done using any language, once you know the concept you can implement it using any language of your choice.

Infix Expression

It follows the scheme of <operand><operator><operand> i.e. an <operator> is preceded and succeeded by an <operand>. Such an expression is termed infix expression. E.g., X+Y

Postfix Expression

It follows the scheme of <operand><operand><operator> i.e. an <operator> is succeeded by both the <operand>. E.g., XY+

Steps to convert Infix to Postfix

Let's take an example of the following expression: A+(B/C-(D*E)^F)*G

  • Here we will start with an empty table and start scanning the elements from left.

  • Every time we encounter an operand we will add it to the postfix notation.

  • When an operator is encountered we will PUSH it to the stack.

  • The operators will be PUSHed according to their precedence. And every time an operator whose's precedence is lower than the ones already inserted is encountered the other operators are POPed into the postfix expression till the first bracket. And these steps will be repeated till the last operand.

The resultant Postfix Expression: ABC/DE*F^-G*+

C program to convert INFIX expression to POSTFIX expression

//Infix to Postfix conversion


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

//push the element in the stack

void push(char x)
    stack[++top] = x;

char pop()
    if(top == -1)
        return -1;
        return stack[top--];

int priority(char x)
    if(x == '(')
        return 0;
    if(x == '+' || x == '-')
        return 1;
    if(x == '*' || x == '/')
        return 2;
    return 0;

int main()
    char exp[100];
    char *e, x;
    printf("Enter the expression : ");
    e = exp;

    //check the expression and call the appropriate functions
    while(*e != '\0')
            printf("%c ",*e);
        else if(*e == '(')
        else if(*e == ')')
            while((x = pop()) != '(')
                printf("%c ", x);
            while(priority(stack[top]) >= priority(*e))
                printf("%c ",pop());
 //print the expression
    while(top != -1) 
        printf("%c ",pop());

683 views0 comments
  • Facebook
  • Instagram

©2020 by thebytewise. All Rights Reserved