Conversion of Expression and Evaluation

//Implementation of Stack

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

class stack
{
struct node
{
int data;
node *next;
};//struct
node *top;

public:
stack()
{
top=NULL;
}
void push(char);
char pop();
int empty();
void display();
int Top()
{
return top->data;
}
};//class

int stack::empty()
{
if(top==NULL)
return 1;
else
return 0;
}//check empty condition

void stack::push(char val)
{
node *temp;
node *newnode=new node;
newnode->next=NULL;
newnode->data=val;

if(top==NULL)
top=newnode;
else
{
newnode->next=top;
top=newnode;
}
}//push opration

char stack::pop()
{
node *temp;
if(empty())
cout<<"\nstack is empty ";
else
{
temp=top;
top=top->next;
return temp->data;
}
}//pop opration

void stack::display()
{
node *temp=top;

while(temp!=NULL)
{
cout<<"\t"<<temp->data;
temp=temp->next;
}
}//display
int priority(char op)
{
static int flag=3;
if(op=='(')
return 0;
else if(op=='+' || op=='-')
return 1;
else if(op=='*' || op=='/')
return 2;
else if(op=='^')
return flag++;
else return -1;

}//priority

void infixtopostfix(char infix[20])
{
char token,post[20],x;
int j=0;
stack s2;

for(int i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
post[j++]=token;
else
if(token=='(')
s2.push(token);
else if(token==')')
while((x=s2.pop())!='(')
post[j++]=x;
else
{
while(!s2.empty() && priority(s2.Top())>=priority(token))
{
post[j++]=s2.pop();
}//while
s2.push(token);
}//else
}//for

while(!s2.empty())
post[j++]=s2.pop();

post[j]='\0';
cout<<post;
}//function of Infix To Postfix


void infixtoprefix(char infix[20])
{
char token,pre[20],x;
int j=0;
stack s2;

for(int i=(strlen(infix)-1);i>=0;i--)
{
token=infix[i];
if(isalnum(token))
pre[j++]=token;
else
if(token==')')
s2.push(token);
else if(token=='(')
while((x=s2.pop())!=')')
pre[j++]=x;
else
{
while(!s2.empty() && priority(s2.Top())>priority(token))
{
pre[j++]=s2.pop();
}//while
s2.push(token);
}//else
}//for

while(!s2.empty())
pre[j++]=s2.pop();

pre[j]='\0';
for(int i=strlen(pre)-1;i>=0;i--)
cout<<pre[i];
}//function of Infix To Prefix

float operation(char token,float op1,float op2)
{
float p;
if(token=='*')
p=op1*op2;
else if(token=='/')
p=op1/op2;
else if(token=='+')
p=op1+op2;
else if(token=='-')
p=op1-op2;
else if(token=='^')
p=pow(op1,op2);

return p;
}//operation

void evapost(char post[20])
{
stack s3;
int val;
float result,op2,op1;
char token;
for(int i=0;post[i]!='\0';i++)
{
token=post[i];
if(isalpha(token))
{
cout<<"\nEnter value of variable "<<token<<" : ";
cin>>val;
s3.push(val);
}//if
else
if(isdigit(token))
s3.push(token-48);

else
{
op2=s3.pop();
op1=s3.pop();
result=operation(token,op1,op2);
s3.push(result);
}//else
}//for
result=s3.pop();
cout<<"\nResult= "<<result;
}//evapostfix expression

void evapre(char pre[20])
{
stack s3;
int val;
float result,op2,op1;
char token;
for(int i=strlen(pre)-1;i>=0;i--)
{
token=pre[i];
if(isalpha(token))
{
cout<<"\nEnter value of variable "<<token<<" : ";
cin>>val;
s3.push(val);
}//if
else
if(isdigit(token))
s3.push(token-48);

else
{
op1=s3.pop();
op2=s3.pop();
result=operation(token,op1,op2);
s3.push(result);
}//else
}//for
result=s3.pop();
cout<<"\nResult= "<<result;
}//evaprefix expression

int main()
{
char str1[20],str2[20],str3[20],str4[20];
int choice;
char ans='y';
do
{
cout<<"\n1.infix to postfix\n2.infix to prefix\n3.postfix evaluation\n4.prefix evaluation.";
cout<<"\nEnter your choice : ";
cin>>choice;
switch(choice)
{
case 1: cout<<"Enter infix expression  ";
 cin>>str1;
 infixtopostfix(str1);
 break;

case 2: cout<<"Enter infix expression  ";
 cin>>str2;
 infixtoprefix(str2);
 break;
case 3: cout<<"Enter postfix expression  ";
 cin>>str3;
 evapost(str3);
 break;
case 4: cout<<"Enter prefix expression  ";
 cin>>str4;
 evapre(str4);
 break;
}//switch
cout<<"\nDo you want to continue (y/n): ";
cin>>ans;

}while(ans=='y' || ans=='Y');

return 0;
}//main

/////////////////OUTPUT///////////////////
/*
1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 1
Enter infix expression  (((a+b)*(c-e))/(f+g))
ab+ce-*fg+/
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 2
Enter infix expression  a+b/c*d-(e+f+(g-h)^i)/j+k
+-+a*//*bcd/++ef^-ghijk
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 3
Enter postfix expression  623+-382/+*2^3+

Result= 52
Do you want to continue (y/n): y

1.infix to postfix
2.infix to prefix
3.postfix evaluation
4.prefix evaluation.
Enter your choice : 4
Enter prefix expression  ^*+232-64

Result= 100
Do you want to continue (y/n): n
*/

Refrence :-

1. http://www.thecrazyprogrammer.com/2014/02/c-program-and-algorithm-for-conversion-of-an-expression-from-infix-to-postfix.html

2. http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

In this program their are Various type of opration.we can perform :

1.Infix to Postfix Opration

2.Infix to Prefix
3.Postfix Evaluation
4.Prefix Evaluation.