Cod sursa(job #2280753)

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

#include<vector>
#include <limits.h>
using namespace std;

#define MAXN 100000

char s[MAXN+1];

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<int> variables;

vector<token> tokens;

#define K 10

void priorities(char* exp){
	int l=strlen(exp);
	tokens.reserve(l);
	int nbPar=0; // nr. curent de paranteze deschise
	token aux;
	int nbVar=0,j,value;
	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*K;
			tokens.push_back(aux);
			continue; 
		}
		if(exp[i]=='*' || exp[i]=='/'){
			aux.info=exp[i]; aux.prio=K*(nbPar+1);
			tokens.push_back(aux);
			continue;
		}

		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);
	} 
} 

nod* buildTreeExp(int left, int right){
	if(left>right)	
		return NULL;
	int mid=left; int minpr=tokens[left].prio;
	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("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;
}