Cod sursa(job #3251837)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 27 octombrie 2024 11:48:49
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;

// E -> T + E | T - E | T
// T -> F * T | F / T | F
// F -> n | (E)

pair<int, size_t> evaluate(const string &expr, size_t index);
pair<int, size_t> term(const string &expr, size_t index);
pair<int, size_t> factor(const string &expr, size_t index);

pair<int, size_t> evaluate(const string &expr, size_t index) {
  auto [partial_result, pos] = term(expr, index);
  index = pos;
  while (index < expr.size() && (expr[index] == '+' || expr[index] == '-')) {
    auto [result, pos] = term(expr, index + 1);
    if (expr[index] == '+')
      partial_result += result;
    else
      partial_result -= result;
    index = pos;
  }

  return {partial_result, index};
}

pair<int, size_t> term(const string &expr, size_t index) {
  auto [partial_result, pos] = factor(expr, index);
  index = pos;
  while (index < expr.size() && (expr[index] == '*' || expr[index] == '/')) {
    auto [result, pos] = factor(expr, index + 1);
    if (expr[index] == '*')
      partial_result *= result;
    else
      partial_result /= result;
    index = pos;
  }

  return {partial_result, index};
}

pair<int, size_t> factor(const string &expr, size_t index) {
  if (expr[index] == '(') {
    auto [result, pos] = evaluate(expr, index + 1);
    assert(expr[pos] == ')');
    return {result, pos + 1};
  }

  assert(isdigit(expr[index]));
  int number = 0;
  while (index < expr.size() && isdigit(expr[index]))
    number = (number * 10 + expr[index++] - '0');

  return {number, index};
}

void solve() {
  string expr;
  cin >> expr;
  auto [result, pos] = evaluate(expr, 0);
  assert(pos == expr.size());
  cout << result << endl;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("evaluare.in", "r", stdin);
  freopen("evaluare.out", "w", stdout);
#endif
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}