Infix to Postfix conversion using stack in C -thebytewise

Updated: Oct 14

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

#include<stdio.h>
#include<ctype.h>

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;
    else
        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 : ");
    scanf("%s",exp);
    printf("\n");
    e = exp;

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



155 views
  • Facebook
  • Instagram

©2020 by thebytewise. All Rights Reserved