Conversion from Infix to Postfix

Application of Stacks

Conversion from Infix to Postfix

The algorithm for converting an Infix expression to Postfix is as follows:

An Infix expression is converted into Postfix using two stacks, one for operator and another for operands.  The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:

• If symbol is an operand, push it in operand’s stack.
• Initialize operator stack with a dummy operator with the least precedence (say #).
• If the symbol is an operator, then do the following:
  • Pop an operator from the operator stack.
  • Check its precedence with the symbol.
  • If the precedence of the symbol is higher, then simply push the popped operator and then the symbol.
  • Else if the precedence of symbol is lower (or equal to) than the popped operator, pop two operands, (opnd2 and opnd1) and perform concatenation operation (opnd1, opnd2, optr).
  • Push the result in operand’s stack.
  • Repeat the above steps until the symbol becomes less than the popped operator.
• After the string ends, start popping an operator from the operator stack and two operands from operand stack.
• Repeat step (d) until dummy operator (#) is found.
• Pop the expression from the operand stack and return it, which is the desired Postfix equivalent of given Infix string.

           Equivalent Postfix expression

Program to convert and Infix expression to Postfix

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 15

struct opndstack
{
int top;
char items[MAX][MAX];
};

struct optrstack
{
int top;
char items[MAX];
};

void init_opndstack(struct opndstack *);
void pushopnd(struct opndstack *,char[]);
void popopnd(struct opndstack *,char arr[]);
int isoperand(char);
void pushoptr(struct optrstack *,char);
char pop(struct optrstack *);
int isoperator(char);

void init_opndstack(struct opndstack * s)
{int i;
for(i=0;i<MAX;i++)
strcpy(s->items[i],”");
s->top=-1;
}

void pushopnd(struct opndstack *s,char ch[])
{
if(s->top==MAX-1)
{printf(“\nStack full! Overflow.”);
exit(1);
}
else
{strcat(s->items[++(s->top)],ch);
}
}

void popopnd(struct opndstack *s,char str[])
{
if(s->top==-1)
{printf(“\nStack empty! Underflow.”);
exit(1);
}
else
{strcpy(str,s->items[s->top]);
strcpy(s->items[s->top--],”");
}
}

int isoperand(char ch)
{return(ch>=’0′ && ch<=’9′);
}

void pushoptr(struct optrstack *s,char ch)
{
if(s->top==MAX-1)
{
printf(“\nStack full! Overflow.”);
exit(1);
}
else
{
s->items[++(s->top)]=ch;
}
}

char popoptr(struct optrstack *s)
{
if(s->top==-1)
{printf(“\nStack empty! Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)--]);
}
}

int isoperator(char ch)
{
switch(ch)
{
case ‘+’:
case ‘-’:
case ‘*’:
case ‘/’:
case ‘^’:
return 1;
default :
return 0;
}
}

int precedence(char ch)
{
switch(ch)
{
case ‘#’:return 0;
case ‘+’:
case ‘-’:return 1;
case ‘*’:
case ‘/’:return 2;
case ‘^’:return 3;
default :printf(“\nInvalid operator!”);
exit(1);
}
}

void main()
{struct opndstack opndstk;
struct optrstack optrstk;
optrstk.top=-1;
pushoptr(&optrstk,’#');

char str[MAX],outstr[MAX],instr[MAX];
char ch,soptr,soptrarr[MAX];
char opnd1[MAX],opnd2[MAX],res[MAX];
strcpy(res,”");
int i;

clrscr();

printf(“\nEnter a string in infix form?”);
gets(str);

for(i=0;(instr[0]=str[i])!=’\0′;i++)
{instr[1]=’\0′;
ch=instr[0];
if(isoperand(ch))
pushopnd(&opndstk,instr);
if(isoperator(ch))
{soptr=popoptr(&optrstk);
if(precedence(ch)>precedence(soptr))
pushoptr(&optrstk,soptr);
else
{while(precedence(ch)<=precedence(soptr) && (soptr!=’#'))
{
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
strcat(res,opnd1);
strcat(res,opnd2);
soptrarr[0]=soptr;
soptrarr[1]=’\0′;
strcat(res,soptrarr);
pushopnd(&opndstk,res);
strcpy(res,”");
soptr=popoptr(&optrstk);
}
if(soptr==’#')
pushoptr(&optrstk,’#');
}
pushoptr(&optrstk,ch);
}
}
soptr=popoptr(&optrstk);
while(soptr!=’#')
{
strcpy(res,”");
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
soptrarr[0]=soptr;
soptrarr[1]=’\0′;
strcat(res,opnd1);
strcat(res,opnd2);
strcat(res,soptrarr);
pushopnd(&opndstk,res);
soptr=popoptr(&optrstk);
}
strcpy(outstr,”");
strcpy(outstr,res);

printf(“\nInfix expression is: %s”,str);
printf(“\nEquivalent Postfix expression is: %s”,outstr);

getch();
}