Cod sursa(job #3277034)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 15 februarie 2025 11:30:18
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.82 kb
#include <bits/stdc++.h>

using namespace std;

const int L_MAX = 1e5 + 5;
const int MAX_PRIORITY = 2; /// = nr prioritati, chiar daca prima prioritate este 0 (avem 2 prioritati, "+-" si "*/")
unsigned int pos; /// pozitia unde am ajuns, variabila globala folosita de functiile recursive
string expr;

vector<vector<char> > operators = {
    {'+', '-'},
    {'*', '/'},
    {'^'} /// din pacate nu putem implementa puterea in acest cod deoarece este asociativa la dreapta
          /// adica x ^ y ^ z = x ^ (y ^ z) in ordinea de operare
          /// si noi lucram cu asociativitate la stanga in functia Eval. Totusi, s-ar putea face modificari
};

unordered_map<char, int> priority = {
    {'+', 0},
    {'-', 0},
    {'*', 1},
    {'/', 1},
    {'^', 2},
};

unordered_map<char, function<int(int, int)> > operations = {
    {'+', [](const int& a, const int& b){ return a + b; } },
    {'-', [](const int& a, const int& b){ return a - b; } },
    {'*', [](const int& a, const int& b){ return a * b; } },
    {'/', [](const int& a, const int& b){ return a / b; } },
    {'^', [](const int& a, const int& b){ return pow(a, b); } }
};

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

int EvalFactor();

/// Functie recursiva pt evaluare, in functie de nivelul curent de proritate
int Eval(int priorityLevel)
{
    if(priorityLevel == MAX_PRIORITY) /// Am ajuns la ultimul nivel
        return EvalFactor();

    int result = Eval(priorityLevel + 1); /// evaluam primul operand

    while(pos < expr.size()
          && find(operators[priorityLevel].begin(), operators[priorityLevel].end(), expr[pos]) != operators[priorityLevel].end()) /// daca urmatorul operator are prioritatea potrivita, sau exista
    {
        char op = expr[pos];

        //if(priority[op] != priorityLevel) /// daca operatorul nu face parte din acest nivel de prioritate ne oprim, dar verificam deja in while
        //    break;

        pos++; /// sarim peste operator

        int nextOperand = Eval(priorityLevel + 1);

        result = operations[op](result, nextOperand);
    }

    return result;
}

/// Functie pentru a evalua numere si expresii intre paranteza
int EvalFactor()
{
    int result = 0;
    if(expr[pos] == '(')
    {
        pos++; /// Sarim peste '('
        result = Eval(0);
        pos++; /// Sarim peste ')'
    }
    else
    {
        while(isdigit(expr[pos])) /// construim numarul
        {
            result = result * 10 + (expr[pos] - '0');
            pos++;
        }
    }
    return result;
}

int main()
{
    SetInput("evaluare");

    cin >> expr;
    pos = 0;
    cout << Eval(0) << '\n';

    return 0;
}