Expression evaluator HELP

[nano72]

Hi Guys ,

I am looking for a function that will evaluate the following expressions (eg..
13214.00
(a * b)/c
a+b

Has anyone code out there that will do any expression like the above ?

I have looked at some on the web but they seem too complex and not working ..

Please help.
Thanks

[little joey]

There are two main approaches:

- substitution: find an operation with the highest priority in the current expression, evaluate it, and replace the operation by the result; repeat until the expression consists of just one value.

- recursive descent: define the grammar and device a parser (you may want to google 'recursive descent parser' to find more information).

The second approach is my favourite. If you have a copy of Stroustroup, you'll find one in there (I always consult Stroustroup when implementing an RDP, because I keep forgetting the details).

[nano72]

hi ,

I am using the following code to do the evaluation

a*b/2
(a+b)/2

but having difficult in getting my desired results ..

Any ideas all help is much appreciated ..


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<deque>
#include<string>
#include<cassert>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;

#define MAXV 101
#define INF 2000000000

#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define ABS(a) ((a)>0 ? (a) : -(a))


enum {UNDEF=0,OPERATOR,OPERAND,NUMBER,ID,OPENPAR,CLOSEPAR};

struct Data
{
string val;
int type;
Data(string v="",int t=UNDEF)
{
val=v; type=t;
}
};

struct TreeNode
{
Data data;
bool parenthesis;
TreeNode *l,*r;
TreeNode(Data d=Data())
{
data=d;
parenthesis=false;
l=r=NULL;
}
};

typedef vector<Data>::iterator diter;


vector<char> ops;
stack<char> opstack;
vector<Data> postfix;
vector<string> ids;
vector<long double> idvals;

TreeNode *root;


void init();
void set_ops_ids();

int priority(char op);
void push_on_opstack(char );
char pop_from_opstack();
void make_postfix(char *);
void print_func(Data &);

TreeNode * make_postfix_tree(diter ,diter );
void traverse(TreeNode *);
void delete_tree(TreeNode *);
long double evaluate_tree(TreeNode *);
long double getvalue(Data d);


void process(char *str);


int main()
{
char input[2000];

set_ops_ids();

while(gets(input))
{
init();
process(input);
//make_postfix(input);
//root=make_postfix_tree(postfix.begin(),postfix.end());
//traverse(root);
//printf("%.2lf\n",evaluate_tree(root));
}

return 0;
}

void process(char *str)
{
string temp;
int index=-1;
long double val;

if(str[1]=='=')
{
temp=str[0];
index=find(ids.begin(),ids.end(),temp)-ids.begin();
str=&str[2];
}

make_postfix(str);
root=make_postfix_tree(postfix.begin(),postfix.end());
//traverse(root);
val=evaluate_tree(root);

if(index==-1)
printf("%.2llf\n",val);
else
idvals[index]=val;
}


/************** MAKING POST FIX NOTATION *************/

void make_postfix(char *expr)
{
int i;
string temp;
char opr;

i=0;
for(i=0;i<strlen(expr);i++)
{
if(expr==' ' || expr=='\t')
continue;

else if(isdigit(expr) || isalpha(expr))
{
temp="";
while(isdigit(expr) || isalpha(expr))
{
temp+=expr;
++i;
}
postfix.push_back(Data(temp,OPERAND));
--i;
}

else if(expr=='(')
{
push_on_opstack(expr);
temp="(";
postfix.push_back(Data(temp,OPENPAR));

}

else if(find(ops.begin(),ops.end(),expr)!=ops.end())
{
if(!opstack.empty())
{
opr=pop_from_opstack();
while(priority(opr)>=priority(expr[i]))
{
temp=opr;
postfix.push_back(Data(temp,OPERATOR));
opr=pop_from_opstack();
}
if(opr!=-1)
push_on_opstack(opr);
push_on_opstack(expr[i]);
}
else
push_on_opstack(expr[i]);
}

else if(expr[i]==')')
{
opr=pop_from_opstack();
while(opr!='(')
{
temp=opr;
postfix.push_back(Data(temp,OPERATOR));
opr=pop_from_opstack();
}

temp=")";
postfix.push_back(Data(temp,CLOSEPAR));
}
}

while(!opstack.empty())
{
opr=pop_from_opstack();
temp=opr;
postfix.push_back(Data(temp,OPERATOR));
}
}

int priority(char op)
{
if((op=='%')||(op=='/')||(op=='*'))
return 2;
if((op=='+')||(op=='-'))
return 1;
return 0;
}

void push_on_opstack(char c)
{
opstack.push(c);
}

char pop_from_opstack()
{
if(opstack.empty())
return -1;

char t=opstack.top();
opstack.pop();
return t;
}

char top_of_opstack()
{
if(opstack.empty())
return -1;

return opstack.top();
}

void print_func(Data &d)
{
if(d.type==OPERATOR && d.val[0]==-1)
{
cout<<" PROBLEM HERE";
return;
}
cout<<"."<<d.val;
}

/*************** END OF MAKING POSTFIX NOTATION ****************/

/***************** INITIALIZATION PART *************************/

void init()
{
postfix.clear();

while(!opstack.empty())
opstack.pop();

// fill(idvals.begin(),idvals.end(),0.0);

delete_tree(root);
root=new TreeNode;
}

void set_ops_ids()
{
int i;
string temp;

ops.push_back('*'); ops.push_back('/'); ops.push_back('%'); ops.push_back('+'); ops.push_back('-');

for(i=0;i<26;i++)
{
temp=('a'+i);
ids.push_back(temp);
}

idvals.resize(26);
fill(idvals.begin(),idvals.end(),0);
}
/******************** END OF INITIALIZATION *****************/


/********************* MAKING EVALUATION TREE ***************/

TreeNode * make_postfix_tree(diter start,diter end) // it will create a tree starting from start and ending just before end
{
diter it,p;
TreeNode *ptr;
stack<TreeNode *> nodestack;

for(it=start;it<end;it++)
{
if(it->type==OPENPAR)
{
int balance=1;

p=it;
do{
++p;
if(p->type==OPENPAR)
++balance;
else if(p->type==CLOSEPAR)
--balance;
}while(p->type!=CLOSEPAR || balance!=0);

ptr=make_postfix_tree(it+1,p);
ptr->parenthesis=true;

it=p;
nodestack.push(ptr);

continue;
}

ptr=new TreeNode(*it);
ptr->parenthesis=false;

if(it->type==OPERATOR)
{
if(!nodestack.empty())
{
ptr->r=nodestack.top();
nodestack.pop();
}
if(!nodestack.empty())
{
ptr->l=nodestack.top();
nodestack.pop();
}
}
nodestack.push(ptr);
}

ptr=nodestack.top(); nodestack.pop();
return ptr;
}

long double evaluate_tree(TreeNode *ptr)
{
if(ptr)
{
long double a,b;

if(ptr->data.type==OPERATOR)
{
a=evaluate_tree(ptr->l);
b=evaluate_tree(ptr->r);

if(ptr->data.val=="+")
return a+b;
if(ptr->data.val=="-")
return a-b;
if(ptr->data.val=="*")
return a*b;
if(ptr->data.val=="/")
return a/b;
if(ptr->data.val=="%")
return fmod(a,b);
}

else if(ptr->data.type==OPERAND)
return getvalue(ptr->data);
}

return 0.0;
}

void traverse(TreeNode *ptr)
{
if(ptr)
{
if(ptr->parenthesis)
cout<<"(";

traverse(ptr->l);
cout<<ptr->data.val;
traverse(ptr->r);

if(ptr->parenthesis)
cout<<")";
}
}

long double getvalue(Data d)
{
int index=find(ids.begin(),ids.end(),d.val)-ids.begin(),i;
long double val;

if(index!=ids.size())
return idvals[index];

for(val=0.0,i=0;i<d.val[i];i++)
val=10*val+d.val[i]-'0';

return val;
}

void delete_tree(TreeNode *ptr)
{
if(ptr)
{
delete_tree(ptr->l);
delete_tree(ptr->r);
delete ptr;
}
}

/********************* END OF MAKING EVALUATION TREE *************