Cod sursa(job #3298132)

Utilizator Raul_ManzicuMinzicu Florian Raul Raul_Manzicu Data 27 mai 2025 10:50:25
Problema Evaluarea unei expresii Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <stack>
#include <cctype>
#include <climits>

using namespace std;

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

vector<string> polo;
vector<string> e;
vector<int> p;

unordered_map<char, int> um = {
    {'+', 1},
    {'-', 1},
    {'*', 10},
    {'/', 10}
};

struct nod {
    string vf;
    nod* fs = nullptr;
    nod* fd = nullptr;
};

nod* arb(int s, int d) {
    if (s > d) return nullptr;

    int mini = INT_MAX;
    int pos = -1;

    for (int i = s; i <= d; ++i) {
        if (p[i] <= mini) {
            mini = p[i];
            pos = i;
        }
    }

    nod* n = new nod;
    n->vf = e[pos];

    if (s == d) return n;

    n->fs = arb(s, pos - 1);
    n->fd = arb(pos + 1, d);

    return n;
}

void SDR(nod* root) {
    if (!root) return;
    SDR(root->fs);
    SDR(root->fd);
    polo.push_back(root->vf);
}

int main() {
    string expresie;
    fin >> expresie;

    int c = 0;
    for (size_t i = 0; i < expresie.size(); ++i) {
        if (expresie[i] == '(') {
            c += 100;
        } else if (expresie[i] == ')') {
            c -= 100;
        } else if (isdigit(expresie[i])) {
            string numar;
            while (i < expresie.size() && isdigit(expresie[i])) {
                numar += expresie[i];
                ++i;
            }
            --i;
            e.push_back(numar);
            p.push_back(100000);
        } else {
            e.push_back(string(1, expresie[i]));
            p.push_back(um[expresie[i]] + c);
        }
    }

    nod* root = arb(0, (int)p.size() - 1);
    SDR(root);

    stack<int> rez;
    for (const auto& it : polo) {
        if (it != "+" && it != "-" && it != "*" && it != "/") {
            rez.push(stoi(it));
        } else {
            int b = rez.top(); rez.pop();
            int a = rez.top(); rez.pop();
            if (it == "+") rez.push(a + b);
            else if (it == "-") rez.push(a - b);
            else if (it == "*") rez.push(a * b);
            else if (it == "/") rez.push(a / b);
        }
    }

    fout << rez.top() << '\n';

    return 0;
}