Saturday, November 17, 2012

Integer Expression Evaluator using Infix-to-Postfix conversion and evaluation of Postfix expression


#include<iostream>
#include<string.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

class stack
{
private:
int top;
char A[100];//operator stack array
int B[100];//operand stack array
public:
char pop_oprt();
void undopop_oprt();
void push_oprt(char);
int get_top();
void displayoprt();
void init();
void push_opnd(int);
int pop_opnd();
};
void stack::init()
{
top=-1;
}
char stack::pop_oprt()
{
if(top==-1)
{
return 0;
}
else
{
char t = A[top];
top--;
return t;
}
}
void stack::push_oprt(char val)
{
top++;
A[top]=val;
}
void stack::undopop_oprt()
{
top++;
}
int stack::pop_opnd()
{
int t = B[top];
top--;
return t;
}
void stack::push_opnd(int val)
{
top++;
B[top]=val;
}
int stack::get_top()
{
return top;
}
void stack::displayoprt()
{
for(int i=top;i>=0;i--)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
int prcd(char a)
{
if(a=='(')
{
return 0;
}
else if(a=='+')
{
return 1;
}
else if(a=='-')
{
return 1;
}
else if(a=='/')
{
return 2;
}
else if(a=='*')
{
return 2;
}
}
int evaluator(char post[100][10],int cnt)
{
stack opnd;
opnd.init();
int i=0;
while(i<cnt)
{
if(isdigit(post[i][0]))
{
opnd.push_opnd(atoi(post[i]));
//opnd.displayoprt();
}
else
{
int val2 = opnd.pop_opnd();
int val1 = opnd.pop_opnd();
if(post[i][0]=='*')
{
opnd.push_opnd(val1*val2);
}
else if(post[i][0]=='+')
{
opnd.push_opnd(val1+val2);
}
else if(post[i][0]=='-')
{
opnd.push_opnd(val1-val2);
}
else if(post[i][0]=='/')
{
opnd.push_opnd(val1/val2);
}
}
i++;
}
return opnd.pop_opnd();
}
int main()
{
//char A[100] = "4/2*2+2/2*4";
char A[100] = "(11+2)*(3+4)";
stack oprt;
oprt.init();
char post[100][10];
int cnt=00;
for(int i=0;i<strlen(A);)
{
//oprt.displayoprt();
//getchar();
int curr_num=0;
if(isdigit(A[i]))
{
while(isdigit(A[i]))
{
curr_num = curr_num*10 + A[i]-48;
i++;
}
itoa(curr_num,post[cnt],10);
cnt++;
}
else if(A[i]=='(')
{
oprt.push_oprt(A[i]);
i++;
}
else if(A[i]==')')
{
while(oprt.pop_oprt()!='(' && oprt.get_top()>-1)
{
oprt.undopop_oprt();
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
}
i++;
}
else
{
//oprt.diplayoprt();
if(oprt.get_top()==-1)
{
oprt.push_oprt(A[i]);
//cout<<oprt.pop_oprt()<<endl;
}
else if(prcd(A[i])>prcd(oprt.pop_oprt()))
{
oprt.undopop_oprt();
oprt.push_oprt(A[i]);
}
else
{
oprt.undopop_oprt();
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
oprt.push_oprt(A[i]);
}
i++;
}
}
while(oprt.get_top()>=0)
{
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
}
cout<<"post-fix"<<endl;
for(int i=0;i<cnt;i++)
{
cout<<post[i]<<endl;
}
cout<<"Final value"<<endl;
cout<<evaluator(post,cnt)<<endl;
}
Output: 91

No comments:

Post a Comment