Cod sursa(job #2816340)

Utilizator DariuuusmMalai Darius Dariuuusm Data 11 decembrie 2021 11:47:18
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

char s[100001];        /// expresia
int ls;             /// lungime
stack <char> op;    /// operatori
stack <int> nr;     /// operanzi

/// prioritatea operatiilor
int prioritate(char c)
{
    if(c == '+' || c == '-')
        return 1;
    if(c == '/' || c == '*')
        return 2;
    if(c == '(' || c == ')')
        return 3;
}

/// formeaza un nr dintr-un sir incepand de la pozitia poz
int formareNr(int poz)
{
    int aux = 0;
    for(int i = poz; i < ls; i++)
    {
        if('0' <= s[i] && s[i] <= '9')
            aux = aux * 10 + (s[i] - '0');
        else
            break;
    }
    return aux;
}

/// evalueaza o expresie cu 2 termeni
int eval()
{
    int x2 = nr.top(); nr.pop();
    int x1 = nr.top(); nr.pop();
    char oper = op.top(); op.pop();
    if(oper == '+')
        return x1 + x2;
    if(oper == '-')
        return x1 - x2;
    if(oper == '*')
        return x1 * x2;
    if(oper == '/')
        return x1 / x2;
}

int dijkstra(char *s)
{
    for(int i = 0; i < ls; i++)
    {
        if(op.empty() && !('0' <= s[i] && s[i] <= '9'))
            op.push(s[i]);
        else
        if('0' <= s[i] && s[i] <= '9')
        {
            int aux = formareNr(i);
            nr.push(aux);
            while(aux > 9)
            {
                aux /= 10;
                i++;
            }
        }
        else
        if(s[i] == ')')
        {
            if(op.top() == '(')
               op.pop();
            else
                while(op.top() != '(')
                    nr.push(eval());
        }
        else
        if(prioritate(s[i]) >= prioritate(op.top()))
            op.push(s[i]);
        else
        if(s[i] == '(')
           op.push(s[i]);
        else
        {
            while(!op.empty() && prioritate(s[i]) < prioritate(op.top()))
                nr.push(eval());
            op.push(s[i]);
        }
    }
    while(!op.empty())
        nr.push(eval());

    return nr.top();
}

int main()
{
    cin.getline(s, 100001);
    ls = strlen(s);
    cout << dijkstra(s);
    return 0;
}