Cod sursa(job #2732892)

Utilizator avtobusAvtobus avtobus Data 29 martie 2021 15:20:16
Problema Evaluarea unei expresii Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
// const int INF = 0x3f3f3f3f;

ifstream fin {"evaluare.in"};
ofstream fout {"evaluare.out"};

struct Result {
  int num;
  size_t pos;
};

Result eval(const string &s, size_t i) {
  // cout << string(25, '-') << i << string(25, '-') << endl;
  stack<char> op1, // + or -
              op2; // * or /
  stack<int> num;
  int d = 0;
  while(i < s.size()) {
    if (s[i] == ')') {
      i++;
      break;
    } else if ('0' <= s[i] && s[i] <= '9') {
      d = 0;
      while('0' <= s[i] && s[i] <= '9') {
        d = d*10 + s[i] - '0';
        i++;
      }
      num.push(d);
      // cout << "d: " << d << ". num.size: " << num.size() << ". op1.size: " << op1.size() << ". op2.size: " << op2.size() << endl;
      while(!op2.empty()) {
        char c = op2.top(); op2.pop();
        int y = num.top(); num.pop();
        int x = num.top(); num.pop();
        // cout << x << c << y << endl;
        if (c == '*') { num.push(x*y); }
        else if (c == '/') { num.push(x/y); }
      }
    } else if (s[i] == '+' || s[i] == '-') {
      op1.push(s[i]);
      i++;
    } else if (s[i] == '*' || s[i] == '/') {
      op2.push(s[i]);
      i++;
    } else if (s[i] == '(') {
      i++;
      auto result = eval(s, i);
      d = result.num;
      i = result.pos;
      num.push(d);
      // cout << "d: " << d << ". num.size: " << num.size() << ". op1.size: " << op1.size() << ". op2.size: " << op2.size() << endl;
      while(!op2.empty()) {
        char c = op2.top(); op2.pop();
        int y = num.top(); num.pop();
        int x = num.top(); num.pop();
        // cout << x << c << y << endl;
        if (c == '*') { num.push(x*y); }
        else if (c == '/') { num.push(x/y); }
      }
    }
  }
  while(!op1.empty()) {
    char c = op1.top(); op1.pop();
    int y = num.top(); num.pop();
    int x = num.top(); num.pop();
    // cout << x << c << y << endl;
    if (c == '+') { num.push(x+y); }
    else if (c == '-') { num.push(x-y); }
  }
  // cout << "num.size " << num.size() << endl;
  // cout << string(22, '=') << num.top() << "=====" << i << string(22, '=') << endl;
  return Result{num.top(), i};
}

int main(void) {
  // freopen("evaluare.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  string str;
  fin >> str;

  auto res = eval(str, 0);
  fout << res.num << '\n';

  return 0;
}