Conversion from Infix to Prefix

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])!=’\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);
soptrarr[0]=soptr;
soptrarr[1]=’\0′;
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]=’\0′;
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();
}