Pagini recente » Cod sursa (job #442371) | Cod sursa (job #2533738) | Cod sursa (job #1368090) | Cod sursa (job #631944) | Cod sursa (job #2280753)
#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;
}