Data Structures-Infix to Postfix Conversion

Infix to Postfix Conversion

What is infix expression?

It is an expression where the operator is in between the operands, i.e in the form of A <op> B.

What is postfix expression?

It is an expression where an operator follows every pair of operands, i.e in the form of A B <op>.

Why postfix expression is used?

The compiler scans from left to right, or from right to left, this makes it efficient. It first adds the operands, then the operator or vice versa, therefore postfix expression is best. Postfix expressions can be evaluated easily using a stack.

Algorithm

Firstly the infix expression is scanned.
Then the operand is given as the output.
If the scanned value is “(“ then it is pushed to the stack, if it is “)” then the stack is popped till “(“ is encountered.
Then the output is printed.
Pop and output from the stack until empty.

Example:

C program to convert infix into postfix.

// Operator supported: +,-,*,/,%,^,(,)
// Operands supported: all single character operands
 
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
 
#define MAX 50
 
typedef struct stack
{
    int data[MAX];
    int top;
}stack;
 
int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int);
int top(stack *);   //value of the top element
void infix_to_postfix(char infix[],char postfix[]);
 
void main()
{
    char infix[30],postfix[30];
    printf("Enter an infix expression(eg: 5+2*4): ");
    gets(infix);
    infix_to_postfix(infix,postfix);
    printf("\nPostfix expression: %s",postfix);
}
 
void infix_to_postfix(char infix[],char postfix[])
{
    stack s;
    char x,token;
    int i,j;    //i-index of infix,j-index of postfix
    init(&s);
    j=0;
 
    for(i=0;infix[i]!='\0';i++)
    {
        token=infix[i];
        if(isalnum(token))
            postfix[j++]=token;
        else
            if(token=='(')
            push(&s,'(');
        else
            if(token==')')
                while((x=pop(&s))!='(')
                      postfix[j++]=x;
                else
                {
                    while(precedence(token)<=precedence(top(&s))&&!empty(&s))
                    {
                        x=pop(&s);
                        postfix[j++]=x;
                    }
                    push(&s,token);
                }
    }
 
    while(!empty(&s))
    {
        x=pop(&s);
        postfix[j++]=x;
    }
 
    postfix[j]='\0';
}
 
int precedence(char x)
{
    if(x=='(')
        return(0);
    if(x=='+'||x=='-')
        return(1);
    if(x=='*'||x=='/'||x=='%')
        return(2);
 
    return(3);
}
 
void init(stack *s)
{
    s->top=-1;
}
 
int empty(stack *s)
{
    if(s->top==-1)
        return(1);
 
    return(0);
}
 
int full(stack *s)
{
    if(s->top==MAX-1)
        return(1);
 
    return(0);
}
 
void push(stack *s,int x)
{
    s->top=s->top+1;
    s->data[s->top]=x;
}
 
int pop(stack *s)
{
    int x;
    x=s->data[s->top];
    s->top=s->top-1;
    return(x);
}
 
int top(stack *p)
{
    return (p->data[p->top]);
}

Reference

Infix to Postfix Conversion