Pagini recente » Cod sursa (job #1318245) | Cod sursa (job #2092269) | Cod sursa (job #2120879) | Cod sursa (job #2962862) | Cod sursa (job #1831447)
#include <iostream>
#include <fstream>
#include <map>
using namespace std;
ifstream in ("evaluare.in");
ofstream out ("evaluare.out");
int n= 0;
int const NMAX = 100002;
char line[NMAX];
int ex[NMAX];
struct tree {
int val;
tree *left;
tree *right;
};
tree *root;
map<int,char> op;
void citire(){
//in>>line;
in>>line;
int pointer = 0;
int i = 0;
int nr = 0;
bool ok = 0;
while(line[i]!=0){
if('0' <= line[i] && line[i] <= '9'){
nr = nr * 10 + line[i] - '0';
ok = 1;
}
else{
if(ok == 1){
ex[pointer] = nr;
op[nr]='@';
pointer++;
} if(line[i]=='+'){
ex[pointer] = 1000000002;
pointer++;
} if(line[i]=='-'){
ex[pointer] = 1000000003;
pointer++;
} if(line[i]=='*'){
ex[pointer] = 1000000004;
pointer++;
} if(line[i]=='/'){
ex[pointer] = 1000000005;
pointer++;
} if(line[i]=='('){
ex[pointer] = 1000000006;
pointer++;
} if(line[i]==')'){
ex[pointer] = 1000000007;
pointer++;
}
ok = 0;
nr = 0;
}
i++;
}
if(ok == 1){
ex[pointer] = nr;
op[nr]='@';
pointer++;
}
n = pointer;
op[1000000002] = '+';
op[1000000003] = '-';
op[1000000004] = '*';
op[1000000005] = '/';
op[1000000006] = '(';
op[1000000007] = ')';
}
int prevop[2][NMAX];
int lastvisited[2][NMAX];
void precompute(){
///le fac -1 pe toate
int parantezlev =0 ;
for(int i =0 ;i < n ;i++){
for(int j =0 ;j < 2;j++)
lastvisited[j][i] = -1;
}
for(int i =0 ;i < n ;i++){
if(op[ex[i]] == '('){
for(int k = 0 ; k < 2 ; k++){
prevop[k][i] = lastvisited[k][parantezlev];
}
parantezlev++;
} if(op[ex[i]] == ')'){
parantezlev--;
for(int k = 0 ; k < 2 ; k++){
prevop[k][i] = lastvisited[k][parantezlev];
}
} else{
for(int k = 0 ; k < 2 ; k++){
prevop[k][i] = lastvisited[k][parantezlev];
}
if(!(op[ex[i]] == '@') && op[ex[i]]!='(' && op[ex[i]]!=')')
lastvisited[(ex[i]-1000000002)/2][parantezlev] = i;
}
}
}
tree *buildtree(int from ,int to){
//cout<<from<<" "<<to<<" "<<prevop[0][to]<<" "<< prevop[1][to]<<" "<<'\n';
tree *result = nullptr;
if(prevop[0][to] < from && prevop[1][to] < from && from != to) {
result = buildtree(from + 1, to - 1);
} else if(from == to){
result = new tree();
result->val = ex[from];
result->left = nullptr;
result->right = nullptr;
} else {
if(prevop[0][to] >= from){
result = new tree();
result->val = ex[prevop[0][to]];
result->left = buildtree(from , prevop[0][to] - 1 );
result->right = buildtree(prevop[0][to] + 1, to);
} else if(prevop[1][to] >= from){
result = new tree();
result->val = ex[prevop[1][to]];
result->left = buildtree(from , prevop[1][to] - 1 );
result->right = buildtree(prevop[1][to] + 1, to);
}
}
return result;
}
int eval(tree *node){
if(op[node->val] == '+') {
return eval(node->left) + eval(node->right);
} else if(op[node->val] == '-') {
return eval(node->left) - eval(node->right);
} else if(op[node->val] == '*'){
return eval(node->left) * eval(node->right);
} else if(op[node->val] == '/'){
return eval(node->left) / eval(node->right);
} else {
return node->val;
}
}
int main(){
citire();
precompute();
root = buildtree(0, n - 1);
out<<eval(root);
return 0;
}