Cod sursa(job #3305773)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 4 august 2025 21:22:44
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>
#define NMAX 500
#define ll long long
#define ull unsigned long long

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

string expr;

struct Nod {
    string val;
    Nod *st, *dr;

    Nod(string v) : val(v), st(NULL), dr(NULL) {}
};

int pr(char op) {
    if (op == '*' || op == '/') {
        return 2;
    }
    if (op == '+' || op == '-') {
        return 1;
    }
    return 0;
}

Nod *nod_intern(stack<Nod*> &nums, stack<char> &op) {
    Nod *dr = nums.top();
    nums.pop();

    Nod *st = nums.top();
    nums.pop();

    char op_cr = op.top();
    op.pop();
    Nod *rad = new Nod(string(1, op_cr));
    rad -> st = st;
    rad -> dr = dr;
    return rad;
}

Nod *build_expr(string expr) {
    stack<Nod*> nums;
    stack<char> op;

    int n = expr.size();
    for (int i = 0; i < n; i++) {
        char ch = expr[i];
        if (isdigit(ch)) {
            int j = i;
            while (j < n && isdigit(expr[j])) {
                j++;
            }
            nums.push(new Nod(expr.substr(i, j - i)));
            i = j - 1;
        }
        else if (ch == '(') {
            op.push(ch);
        }
        else if (ch == ')') {
            while (!op.empty() && op.top() != '(') {
                nums.push(nod_intern(nums, op));
            }
            op.pop();
        }
        else {
            while (!op.empty() && pr(op.top()) >= pr(ch)) {
                nums.push(nod_intern(nums, op));
            }
            op.push(ch);
        }
    }

    while (!op.empty()) {
        nums.push(nod_intern(nums, op));
    }
    return nums.top();
}

int eval(Nod *nod) {
    if (!nod -> st && !nod -> dr) {
        return stoi(nod -> val);
    }

    int val_st = eval(nod -> st);
    int val_dr = eval(nod -> dr);

    if (nod -> val == "+") {
        return val_st + val_dr;
    }
    if (nod -> val == "-") {
        return val_st - val_dr;
    }
    if (nod -> val == "*") {
        return val_st * val_dr;
    }
    if (nod -> val == "/") {
        return val_st / val_dr;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    getline(fin, expr);

    Nod *rad = build_expr(expr);
    fout << eval(rad);
    return 0;
}