#include<stdlib.h>
#include<iostream>
#include<string.h>
#define max 30
using namespace std;
struct node
{
char data;
struct node *next;
};
class stack
{
node *top;
char x;
public:
stack()
{
top= NULL;
}
int empty()
{
if(top==NULL)
{
return(1);
}
else
{
return(0);
}
}
void push(char x)
{
node *p;
p=new node;
p->data=x;
p->next=top;
top=p;
}
char pop()
{
if(!empty())
{
node *p;
p=new node;
p=top;
top=top->next;
x=p->data;
delete p;
return(x);
}
else
{
cout<<"stack is empty"<<endl;
return(0);
}
}
char pop1()
{
if(!empty())
{
node *p;
p=new node;
p=top;
//top=top->next;
x=p->data;
//delete p;
return(x);
}
else
{
cout<<"stack is empty"<<endl;
return(0);
}
}
};
int precedence(char x);
void infix_to_prefix(char infix[],char prefix[]);
void infix_to_postfix(char infix[],char postfix[]);
void eval_prefix(char prefix[]);
void eval_postfix(char postfix[]);
int evaluate(char x,int op1,int op2);
int main()
{
char infix[30],prefix[30],postfix[30];
int op;
do{
cout<<"
Menu::
1)Infix to Prefix with Evaluation
2)Infix to Postfix with Evaluation
3)Quit
Enter your choice:: ";
cin>>op;
switch(op)
{
case 1:
cout<<"
Enter the infix expression::"<<endl;
cin>>infix;
infix_to_prefix(infix,prefix);
cout<<"
Prefix expression is "<<prefix<<endl;
cout<<"
Evaluation of Prefix expression";
eval_prefix(prefix);
break;
case 2:
cout<<"
Enter the infix expression::"<<endl;
cin>>infix;
infix_to_postfix(infix,postfix);
cout<<"
Postfix expression is "<<postfix<<endl;
cout<<"
Evaluation of Postfix expression";
eval_postfix(postfix);
break;
}
}while(op!=3);
return 0;
}
void infix_to_prefix(char infix[],char prefix[])
{
int i,j;
char temp,in1[30];
cout<<"
After step 1...
Entered infix is...";
for(i=0;i<=strlen(infix)-1;i++)
{
cout<<infix[i];
}
for(i=strlen(infix)-1,j=0;i>=0;i--,j++)
in1[j]=infix[i];
in1[j]=' ';
cout<<"
After step 2...";
for(i=0;i<=strlen(in1)-1;i++)
{
cout<<in1[i];
}
for(i=0;in1[i]!=' ';i++)
{
if(in1[i]=='(')
in1[i]=')';
else
if(in1[i]==')')
in1[i]='(';
}
cout<<"
After step 3...";
for(i=0;i<=strlen(in1)-1;i++)
{
cout<<in1[i];
}
cout<<"
After step 4...";
cout<<"
Prefix is...";
infix_to_postfix(in1,prefix);
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[i];
prefix[i]=prefix[j];
prefix[j]=temp;
}
}
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
node *top;
char x;
int i,j;
char token;
j=0;
for(i=0;infix[i]!=' ';i++)
{
token=infix[i];
if(isalnum(token))
{
postfix[j++]=token;
}
else if(token=='(')
{
s.push('(');
}
else if(token==')')
{
while((x=s.pop())!='(')
{
postfix[j++]=x;
}
}
else
{
x=s.pop1();
while(precedence(token)<precedence(x)&& !s.empty())
{
x=s.pop();
postfix[j++]=x;
}
s.push(token);
}
}
while(!s.empty())
{
x=s.pop();
postfix[j++]=x;
}
postfix[j]=' ';
}
int precedence(char x)
{
if(x=='(')
{
return(0);
}
if(x=='+'||x=='-')
{
return(1);
}
if(x=='*'||x=='/'||x=='%')
{
return(2);
}
return(3);
}
void eval_prefix(char prefix[])
{
stack s;
char x;
int op1,op2,val,i;
for(i=strlen(prefix)-1;i>=0;i--)
{
x=prefix[i];
if(isalpha(x))
{
cout<<"
Enter the value of "<<x<<":";
cin>>val;
s.push(val);
}
else
{
op1=s.pop();
op2=s.pop();
val=evaluate(x,op1,op2);
s.push(val);
}
}
val=s.pop();
cout<<"
Value of expression is "<<val;
}
void eval_postfix(char postfix[])
{
stack s;
char x;
int op1,op2,val,i;
for(i=0;postfix[i]!=' ';i++)
{
x=postfix[i];
if(isalpha(x))
{
cout<<"
Enter the value of "<<x<<":";
cin>>val;
s.push(val);
}
else
{
op2=s.pop();
op1=s.pop();
val=evaluate(x,op1,op2);
s.push(val);
}
}
val=s.pop();
cout<<"
Value of expression is "<<val;
}
int evaluate(char x,int op1,int op2)
{
if(x=='+')
return(op1+op2);
if(x=='-')
return(op1-op2);
if(x=='*')
return(op1*op2);
if(x=='/')
return(op1/op2);
if(x=='%')
return(op1%op2);
}
//END OF PROGRAM