Cod sursa(job #3312543)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 29 septembrie 2025 01:57:23
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <bits/stdc++.h>

using namespace std;

// Infix expression (with (), +, -, *, /)
// |
// v
// Shunting-yard
// |
// v
// RPN (postfix form, unambiguous, no parentheses) OR expression tree
// |
// v
// Stack-based evaluation
// |
// v
// Final integer result

inline int precedence(char op) {
  switch (op) {
    case '+':
      return 1;
    case '-':
      return 1;
    case '*':
      return 2;
    case '/':
      return 2;
    default:
      return 0;
  }
}

int main() {
#ifndef LOCAL
  freopen("evaluare.in", "r", stdin);
  freopen("evaluare.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string expr;
  cin >> expr;
  vector<string> rpxe;
  stack<char> s;
  for (std::size_t i = 0; i < expr.size(); ++i) {
    if (!isspace(expr[i])) {
      if (isdigit(expr[i])) {
        std::string number;
        for (; i < expr.size() && isdigit(expr[i]);) {
          number.push_back(expr[i++]);
        }
        rpxe.push_back(number);
        --i;
      } else {
        switch (expr[i]) {
          case '(':
            s.push(expr[i]);
            break;
          case ')':
            for (; s.size() && s.top() != '(';) {
              rpxe.push_back(string(1, s.top()));
              s.pop();
            }
            s.pop();
            break;
          default:
            for (; s.size() && precedence(s.top()) >= precedence(expr[i]);) {
              rpxe.push_back(string(1, s.top()));
              s.pop();
            }
            s.push(expr[i]);
        }
      }
    }
  }
  for (; s.size();) {
    rpxe.push_back(string(1, s.top()));
    s.pop();
  }
  stack<int> p;
  for (auto& subexpr : rpxe) {
    if (subexpr == "+" || subexpr == "-" || subexpr == "*" || subexpr == "/") {
      int b = p.top();
      p.pop();
      int a = p.top();
      p.pop();
      if (subexpr == "+") {
        p.push(a + b);
      } else if (subexpr == "-") {
        p.push(a - b);
      } else if (subexpr == "*") {
        p.push(a * b);
      } else if (subexpr == "/") {
        p.push(a / b);
      }
    } else {
      p.push(stoi(subexpr));
    }
  }
  assert(p.size() == 1);
  std::cout << p.top();
  return 0;
}