Cod sursa(job #1831447)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 18 decembrie 2016 08:31:19
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.59 kb
#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;
}