Cod sursa(job #2732013)

Utilizator radubigColtos Radu radubig Data 28 martie 2021 17:02:43
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>
#define lim 100000

using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");

int coef = 0;
char a[lim+5];
stack<pair<int, char>> ops; //first -> priority, second -> operator
vector<pair<int, int>> polonez; //first -> tip, second -> info
                                ///0-> nr, 1->op

int prioritate(char c)
{
    switch(c)
    {
        case '*' : case '/' : return 2;
        case '+' : case '-' : return 1;
        default : return 0; //this should not happen
    }
}

int operatie(int nr1, int nr2, char c)
{
    switch(c)
    {
        case '+': return nr1+nr2; break;
        case '-': return nr1-nr2; break;
        case '*': return nr1*nr2; break;
        case '/': return nr1/nr2; break;
        default: return 0; //RIP
    }
}

void parse(char* a)
{
    int n = strlen(a);
    int nr = 0, ok = 0;
    for(int i=0; i<n; i++)
    {
        if(a[i]>='0' && a[i]<='9')
        {
            ok = 1;
            nr = nr * 10 + a[i] - '0';
        }
        else if(a[i]=='(') coef += 10;
        else if(a[i]==')') coef -= 10;
        else
        {
            if(ok) polonez.push_back(make_pair(0, nr));
            ok = 0;
            nr = 0;
            int pr = prioritate(a[i]) + coef;
            while(!ops.empty() && ops.top().first >= pr)
            {
                polonez.push_back(make_pair(1, ops.top().second));
                ops.pop();
            }
            ops.push(make_pair(pr, a[i]));
        }
    }
    //golirea numarului
    if(ok) polonez.push_back(make_pair(0, nr));
    while(!ops.empty()) //golirea stivei
    {
        polonez.push_back(make_pair(1, ops.top().second));
        ops.pop();
    }
}

void compute()
{
    stack<int> numere;
    for(auto& i : polonez) //pentru fiecare element din sirul polonez
    {
        if(i.first == 0)
            numere.push(i.second);
        else
        {
            //ordinea operanzilor este inversa
            int nr2 = numere.top();
            numere.pop();
            int nr1 = numere.top();
            numere.pop();
            numere.push(operatie(nr1, nr2, i.second));
        }
    }

    //rezultat:
    out<<numere.top();
}

int main()
{
    in>>a;
    parse(a);
    compute();
    return 0;
}