Cod sursa(job #2280835)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 11 noiembrie 2018 11:21:42
Problema Evaluarea unei expresii Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.08 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include<vector>
#include <limits.h>
#include<map>
#include<algorithm>

using namespace std;

#define MAXN 100000

char s[MAXN+1];

map<pair<int,int>,int> minime;

typedef struct nod{ 
	int info; // operator sau numele variabilei
	struct nod *left, * right;
}nod;

typedef struct token{ // operator sau variabila
	int info; // operator sau numele variabilei
	int prio; // prioritatea tokenului
}token; // vom avea un vector de tokeni

vector<token> tokens;

#define K 2

void priorities(char* exp){
	int l=strlen(exp);
	tokens.reserve(l);
	int nbPar=0; // nr. curent de paranteze deschise
	token aux;
	int nbTokens=0,j,value;
	int minim,prio;
	for(int i=0;i<l;i++){
		if(exp[i]=='('){	nbPar++; continue;}
		if(exp[i]==')'){	nbPar--; continue;} 

		if(exp[i]=='+' || exp[i]=='-'){
			aux.info=exp[i]; aux.prio=1+(nbPar<<1);
			tokens.push_back(aux);
		}
		else{
			if(exp[i]=='*' || exp[i]=='/'){
				aux.info=exp[i]; aux.prio=(nbPar+1)<<1;
				tokens.push_back(aux);
			}
			else{
				value=exp[i]-'0';
				for(j=i+1;j<l;j++){
					if(exp[j]>'9' || exp[j]<'0')
						break;
					value*=10;
					value+=(exp[j]-'0');
				}
				i=j-1;
				aux.info=value; aux.prio=INT_MAX; 
				tokens.push_back(aux);
			}
		}
		
		/*
		minime.insert(make_pair(make_pair(nbTokens,nbTokens),nbTokens));
		minim=nbTokens; prio=aux.prio;
		for(int k=nbTokens-1;k>=0;k--){
			if(tokens[k].prio<prio){
				minim=k; prio=tokens[k].prio;
			}
			minime.insert(make_pair(make_pair(k,nbTokens),minim));
		}
		nbTokens++;
		*/
	} 
} 

nod* buildTreeExp(int left, int right){
	if(left>right)	
		return NULL;
	/*
	map<pair<int,int>,int>::iterator it;
	it=minime.find(make_pair(left,right));
	int mid=it->second; 
	*/
	
	int minpr=tokens[left].prio;
	int mid=left;
	for(int i=left+1;i<=right;i++){ 
		if(tokens[i].prio<=minpr){
			mid=i; minpr=tokens[i].prio;
		}
	}
	

	nod* root=new nod;
	root->info=tokens[mid].info;
	root->left=buildTreeExp(left,mid-1);
	root->right=buildTreeExp(mid+1,right);
	return root;
}

/*
void printsymbol(int info){
	if(info=='(' || info==')' || info=='+')
		printf("%c",info);
	else{
		if(info=='-' || info=='*' || info=='/')
			printf("%c",info);
		else
			printf("%d",info);
	}
}

void inorder(nod* root){
	if(root->left==NULL) {
		printsymbol(root->info);
		return;
	}
	printf("(");
	inorder(root->left);
	printsymbol(root->info);
	inorder(root->right);
	printf(")");
}
*/

int evalTreeExp(nod* root){
	if(root->left==NULL)	
		return root->info;
	int op1=evalTreeExp(root->left);
	int op2=evalTreeExp(root->right);
	switch(root->info){
		case '+':	return op1+op2;
		case '-':	return op1-op2;
		case '*':	return op1*op2;
		case '/':	return op1/op2;
	}
}

int main(){
	
	freopen("evaluare.in","rt",stdin);
	//freopen("test10.in","rt",stdin);
	freopen("evaluare.out","wt",stdout);
	
	scanf("%s\n",s);

	priorities(s); 
	nod* root=buildTreeExp(0,tokens.size()-1);
	//inorder(root); 
	int rez=evalTreeExp(root); 
	printf("%d\n",rez); 

	return 0;
}