Expression Evaluator and Parsing

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
soumit
New poster
Posts: 4
Joined: Wed Feb 25, 2004 4:42 pm
Location: Bangladesh
Contact:
Contact soumit

Expression Evaluator and Parsing

Post by soumit »

Hi,
I need some help on parsing techniques. Ive been trying to solve 10932 Calculator and frequently getting WA. I used the algorithm stated in the following link. I use the Postfix notation.

LINK:

Algorithm # http://www.codepedia.com/1/Art_Expressions_p1
Their Implementation # http://www.codepedia.com/1/Art_Expressions_p2

Now this implementation has a little bit problem in dealing with the parentheses. Which I fixed in my code ( its given at the end of the post )

But im getting WA ... definately thrs something wrong with my algo or may b my code which i cant really detect.

So can anyone plz show me where my error is or may provide me with a correct algorithm or code for parsing and expression evaluation.

With Regards
Soumit Salman

My Code

Code: Select all

#pragma warning(disable:4786)

#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[i]==' ' || expr[i]=='\t')
			continue;
		
		else if(isdigit(expr[i]) || isalpha(expr[i]))
		{
			temp="";
			while(isdigit(expr[i]) || isalpha(expr[i]))
			{
				temp+=expr[i];
				++i;
			}
			postfix.push_back(Data(temp,OPERAND));
			--i;
		}
		
		else if(expr[i]=='(')
		{
			push_on_opstack(expr[i]);
			temp="(";
			postfix.push_back(Data(temp,OPENPAR));

		}

		else if(find(ops.begin(),ops.end(),expr[i])!=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 ***************/
Top
Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:
Contact Zuberul

Post by Zuberul »

i havnt tested ur code just had a look at it.
i dont think u need a post fix form.
because if u r building tree u can evaluate on the process.
if u havnt solved it yet i can help.
Top
nano72
New poster
Posts: 10
Joined: Tue Sep 05, 2006 5:25 pm

Post by nano72 »

Hi ,

Does this code work now ?

Please advise
Top
Post Reply

Return to “Algorithms”