Cod sursa(job #353779)

Utilizator undogSavu Victor Gabriel undog Data 6 octombrie 2009 08:14:40
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <cstring>

struct node{
	node *left,*right;
	bool isNumber;
	int val;
};

char msg[100000];
int n;

inline int getPriority(char x){
	if(x=='+')
		return 1;
	if(x=='-')
		return 2;
	if(x=='*')
		return 3;
	if(x=='/')
		return 4;
	return 5;
}

int getNumber(int l,int r){
	int i,n=0;
	for(i=l;i<r;i++)
		n=n*10+msg[i]-48;
	return n;
}

node* rang(int l,int r){
	int i,p=5,pos;
	if(msg[l]=='('){
		pos=0;
		for(i=l;i<r;i++){
			if(msg[i]=='(')
				pos++;
			else if(msg[i]==')')
				pos--;
			if(!pos)
				break;
		}
		if(i>=r-1)
			return rang(l+1,r-1);
	}
	node* tmp;
	tmp=new node;
	tmp->left=tmp->right=NULL;
	tmp->isNumber=false;
	tmp->val=0;
	for(i=l;i<r;i++)
		if(msg[i]=='('){
			int ct=0;
			do{
				if(msg[i]=='(')
					ct++;
				else if(msg[i]==')')
					ct--;
				i++;
			}while(ct);
			i--;
		}
		else if(p>getPriority(msg[i])){
			pos=i;
			p=getPriority(msg[i]);
			if(p==1)
				break;
		}
		
	if(p<5){
		tmp->left=rang(l,pos);
		tmp->right=rang(pos+1,r);
		tmp->val=msg[pos];
	}
	else{
		tmp->isNumber=true;
		tmp->val=getNumber(l,r);
	}
	
	return tmp;
}

inline node* init(){
	return rang(0,n);
}

int parse(node* x){
	if(x->isNumber)
		return x->val;
	switch(x->val){
		case '+': return parse(x->left)+parse(x->right);
		case '-': return parse(x->left)-parse(x->right);
		case '*': return parse(x->left)*parse(x->right);
		case '/': return parse(x->left)/parse(x->right);
	}
}

int main(){
	freopen("evaluare.in","rt",stdin);
	freopen("evaluare.out","wt",stdout);
	
	scanf("%s",msg);
	n=strlen(msg);
	node* root=init();
	printf("%d",parse(root));
	return 0;
}