Application of Stacks
Conversion from Infix to Prefix
The algorithm for converting an Infix expression to Prefix is as follows:
An Infix expression is converted into Prefix 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 (optr, opnd1, opnd2).
- 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 Prefix equivalent of given Infix string.
Program to convert an Infix expression to Prefix:
#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])!=’�’;i++)
{instr[1]=’�’;
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);
soptrarr[0]=soptr;
soptrarr[1]=’�’;
strcat(res,soptrarr);
strcat(res,opnd1);
strcat(res,opnd2);
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]=’�’;
strcat(res,soptrarr);
strcat(res,opnd1);
strcat(res,opnd2);
pushopnd(&opndstk,res);
soptr=popoptr(&optrstk);
}
strcpy(outstr,””);
strcpy(outstr,res);
printf(“nInfix expression is: %s”,str);
printf(“nEquivalent Prefix expression is: %s”,outstr);
getch();
}