Program to Convert Infix to Prefix using Stack

/* Program to convert infix expression in to pre fix expression */
#include<iostream.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
#define MAX 20
class stack
{
char s[MAX];
int top;
public:
stack()
{
top=-1;
}

void push(char );
char pop();
int isfull();
int isempty();
void display();
void convert(char *str);
int priority(char ch);
};
void stack:: push(char x)
{
if(isfull()==1)
{
cout<<“\n stack full”;
return;
}
else
{
top++;
s[top]=x;
}
}
char stack:: pop()
{
char ele=’\0′;
if(isempty()==1)
{
cout<<“stack empty “;
return ele;
}
else
{
ele=s[top];
top–;
}
return ele;
}
void stack::display()
{
int i;
for(i=top;i>=0;i–)
cout<<“\n”<<s[i];
}
int stack:: isempty()
{
int i=0;
if(top==-1)
i=1;
return i;
}
int stack:: isfull()
{
int i=0;
if(top==MAX)
i=1;
return i;
}

void stack:: convert(char *s)
{
cout<<“\n reversed string is “<<s;
char opr;
int t;
char target[20];
t=0;
while(*s!=’\0′)
{
if( *s==’ ‘ || *s==’\t’)
{
s++;
continue;
}
if(isdigit(*s) || isalpha(*s))
{
target[t]=*s;
s++;
t++;
}
if(*s==’)’)
{
push(*s);
s++;
}
if(*s==’*’ || *s==’+’ || *s==’/’ || *s==’%’ || *s==’-‘ || *s==’$’)
{
if(top!=-1)
{
opr=pop();
if(opr==’)’)
{
push(opr);
push(*s);
s++;
continue;
}
else if (priority(opr)>priority(*s))
{
target[t]=opr;
t++;
opr=pop();
}
push(opr);
push(*s);
}
else
{
push(*s);
}
s++;
}
if(*s=='(‘)
{
opr=pop();
while(opr!=’)’)
{
target[t]=opr;
t++;
opr=pop();
}
s++;
}
}
while(top!=-1)
{
opr=pop();
target[t]=opr;
t++;
}
t++;
target[t]=’\0′;
cout<<“\n prefix string “<<strrev(target);
}
int stack :: priority(char ch)
{
if(ch==’^’||ch==’$’)
return 3;
else if(ch==’*’||ch==’/’|| ch==’%’)
return 2;
else if(ch==’+’ || ch==’-‘)
return 1;
else
return 4;
}
void main()
{
stack st1;
char exp[20];
clrscr();
cout<<“\n enter expression “;
cin>>exp;
strrev(exp);
st1.convert(exp);
getch();
}

Leave a Reply