Cod sursa(job #3298082)

Utilizator Raul_ManzicuMinzicu Florian Raul Raul_Manzicu Data 26 mai 2025 20:36:01
Problema Evaluarea unei expresii Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 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;

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

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

nod *arb(const vector<int>& p, const vector<string>& e)
{
    nod *n = new nod;
    int mini = INT_MAX;
    int pos = 0;
    for(int i = 0 ; i < p.size() ; i++)
        if(p[i] < mini)
        {
            mini = p[i];
            pos = i;
        }
    n->vf = e[pos];
    if(p.size() == 1)
        return n;
    n->fs = arb(vector<int>(p.begin(), p.begin() + pos), vector<string>(e.begin(), e.begin() + pos));
    n->fd = arb(vector<int>(p.begin() + pos + 1, p.end()), vector<string>(e.begin() + pos + 1, e.end()));
    
    return n;
}

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

int main()
{
    string expresie;
    fin >> expresie;
    vector<string> e;
    vector<int> p;
    int c = 0;
    char t;
    for(int i = 0 ; i < expresie.size() ; i++)
    {
        if(expresie[i] == '(')
        {
            c += 100;
            continue;
        }
        if(expresie[i] == ')')
        {
            c -= 100;
            continue;
        }
    
        if(isdigit(expresie[i]))
        {
            string numar(1, expresie[i]);
            int j = i + 1;
            while(j < expresie.size() && isdigit(expresie[j]))
            {
                numar += expresie[j];
                j++;
            }
            i = j - 1;
            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(p, e);
    SDR(root);
    stack<int> rez;
    for(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);
            if(it == "-")
                rez.push(a - b);
            if(it == "*")
                rez.push(a * b);
            if(it == "/")
                rez.push(a / b);
        }
    }
    fout << rez.top();
}