Converting Infix to Postfix (Simple Way)

Hello friends ,

I am back again and this time i am going to post a tutorial for Converting Infix to Postfix With Simple way from basic way.

So before we go ahead we have to understand first what is Infix notation why we need to convert this to prefix or postfix notation so you have many question.

First of all before really going to learn this thing you have some basic knowledge of c/c++ and in that stack and Tree.

So Now introduction about this topic

So think if you are making programmable calculator and you can perform 10+10 operation easily but what if you want to do3 * 2 / (5 + 45) % 10 ?

We human can do easily by calculator or normal mind but what if we have to do this thing from our program?

How can we do this things ?

Answer is yes we can do but for this we have to convert above notation in prefix or postfix. So this prefix and postfix notation can be understand by machine or (Computer) .

How to Convert Infix to Postfix?

If A+B is given than we can simply convert this to postfix and prefix notation as below

POSTFIX :- AB+

PREFIX  :- +AB

So now you have some basic idea of this how  to convert it manually. This is about just two operands and one operator what if there notation like A + B * ( C + D ) this ? For this we have to use of priority of the operators like + and – same priority so simply we can decide this by

B O D M A S

Bracket Open -> Division -> Multiplication -> Addition -> Subtraction

[MAX. PRIORITY] [MIN. PRIORITY]

So now we can decide the priority and we can convert any notation to postfix or prefix

[INFIX TO POSTFIX]

:: A + B * ( C + D )

1: A + B * C D +

3: A B C D + * +

So we know now how to do it manually now we have to do this same thing with C language I have little and simple algorithm which can do this stuff.

Algorithm infix2postfix(infix exp ression string, postfix exp ression string)
{
   char *i,*p;

   i = first element in infix exp ression
   p = first element in postfix exp ression

   while i is not null
   {
          while i is a space or tab
          {
                 increment i to next character in infix exp ression;
          }

          if( i is an operand )
          {
                 p = i;
                 increment i to next character in infix exp ression;
                 increment p to next character in postfix exp ression;
          }

          if( i is '(' )
          {
                 stack_push(i);
                 increment i to next character in infix exp ression;
          }

          if( i is ')' )
          {
                 while( element at top of stack != '(' )
                 {
                        p = element at top of stack;
                        increment p to next character in postfix exp ression;
                 }
                 increment i to next character in infix exp ression;
          }

          if( i is an operator )
          {
                 if( stack is empty )
                         stack_push(i);
                 else
                 {

                        while priority(element at top of stack) >= priority(i)
                        {
                           p = element at top of stack;
                           increment p to next character in postfix expression;
                        }
                        stack_push(i);
                 }
                 increment i to next character in infix expression;
          }
   }
   while stack is not empty
   {
          p = stack_pop()
          increment p to next character in postfix expression;
   }
   p = '';
}

Now above is just algorithm to convert Infix to postfix notation you can just follow the step and check that its getting correct output or not.

Now for C code . There are two type of Technique to implement this one is STACK and another is TREE so for now I am using STACK

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

#define MAX 10
#define EMPTY -1

struct stack
{
        char data[MAX];
        int top;
};

int isempty(struct stack *s)
{
        return (s->top == EMPTY) ? 1 : 0;
}

void emptystack(struct stack* s)
{
        s->top=EMPTY;
}

void push(struct stack* s,int item)
{
        if(s->top == (MAX-1))
        {
                printf("\nSTACK FULL");
        }
        else
        {
                ++s->top;
                s->data[s->top]=item;
        }
}

char pop(struct stack* s)
{
        char ret=(char)EMPTY;
        if(!isempty(s))
        {
                ret= s->data[s->top];
                --s->top;
        }
        return ret;
}

void display(struct stack s)
{
        while(s.top != EMPTY)
        {
                printf("\n%d",s.data[s.top]);
                s.top--;
        }
}

int isoperator(char e)
{
        if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
                return 1;
        else
                return 0;
}

int priority(char e)
{
        int pri = 0;

        if(e == '*' || e == '/' || e =='%')
                pri = 2;
        else
        {
                if(e == '+' || e == '-')
                        pri = 1;
        }
        return pri;
}

void infix2postfix(char* infix, char * postfix, int insertspace)
{
        char *i,*p;
        struct stack X;
        char n1;
        emptystack(&X);
        i = &infix[0];
        p = &postfix[0];

        while(*i)
        {
                while(*i == ' ' || *i == '\t')
                {
                        i++;
                }

                if( isdigit(*i) || isalpha(*i) )
                {
                        while( isdigit(*i) || isalpha(*i))
                        {
                                *p = *i;
                                p++;
                                i++;
                        }
                        /*SPACE CODE*/
                        if(insertspace)
                        {
                                *p = ' ';
                                p++;
                        }
                        /*END SPACE CODE*/
                }

                if( *i == '(' )
                {
                        push(&X,*i);
                        i++;
                }

                if( *i == ')')
                {
                        n1 = pop(&X);
                        while( n1 != '(' )
                        {
                                *p = n1;
                                p++;
                                /*SPACE CODE*/
                                if(insertspace)
                                {
                                        *p = ' ';
                                        p++;
                                }
                                /*END SPACE CODE*/
                                n1 = pop(&X);
                        }
                        i++;
                }

                if( isoperator(*i) )
                {
                        if(isempty(&X))
                                push(&X,*i);
                        else
                        {
                                n1 = pop(&X);
                                while(priority(n1) >= priority(*i))
                                {
                                        *p = n1;
                                        p++;
                                        /*SPACE CODE*/
                                        if(insertspace)
                                        {
                                                *p = ' ';
                                                p++;
                                        }
                                        /*END SPACE CODE*/
                                        n1 = pop(&X);
                                }
                                push(&X,n1);
                                push(&X,*i);
                        }
                        i++;
                }
        }
        while(!isempty(&X))
        {
                n1 = pop(&X);
                *p = n1;
                p++;
                /*SPACE CODE*/
                if(insertspace)
                {
                        *p = ' ';
                        p++;
                }
                /*END SPACE CODE*/
        }
        *p = '';
}

int main()
{
        char in[50],post[50];

        strcpy(&post[0],"");
        printf("Enter Infix Expression : ");
        fflush(stdin);
        gets(in);
        infix2postfix(&in[0],&post[0],1);
        printf("Postfix Expression is : %s\n",&post[0]);

        return 0;
}
/* SAMPLE OUTPUT:
Enter Infix Expression : A + B + C / (E - F)
Postfix Expression is : A B + C E F - / +
*/

So if you have any question or doubt you can ask me via Leaving comment here and for getting more tutorials like this than just be active here.

Regards,

Mihir Soni

Incoming search terms for the article:

• infix to postfix
• why we want to convert infix to postfix
• program on converting infix exp to postfix exp
• convert infix to postfix online
• infix to postfix priority
• how to convert c to infix to postfix
• infix to postfix online
• stack for infix to postfix conversion
• method of converting infix to postfix
• c program to find infix to postfix