Cod sursa(job #3331962)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 2 ianuarie 2026 01:07:23
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
/*
   Evaluarea unei expresii - dupa o idee de Sima Cotizo (job ID 144801)

   Definim recursiv o expresie de nivel k (k>=0) astfel:
   E(k) = E1(k+1) o(k) E2(k+1) o(k) ... o(k) En(k+1)
   unde Ei(k+1) sunt expresii de nivel k+1, iar
   o(k) sunt operatori cu nivel de prioritate k

   Ultimul nivel din expresii (fie acesta L) este alcatuit
   din variabile sau expresii de nivel 0 incluse intr-o pereche de paranteze
   E(L) = x (x variabila sau numar) sau E(L) = ( E(0) )

   Vom evalua astfel expresiile pe niveluri de prioritate, folosind in
   fiecare nivel operatorii din clasa de prioritate respectiva
*/

#include <cstdio>
#include <cstring>

#define LMAX 2 // nivelul maxim de prioritate
char op[4][4] = { "+-", "*/", "^", "" }; // operatorii pe niveluri de prioritate

#define NX 100010
char S[NX], *p = S;

int eval(int a, int b, char o)
{
    switch(o)
    {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    }
}

/*
   Urmatoarea functie evalueaza expresia care incepe pe pozitie indicata de p
   considerand ca aceasta este de nivel lev

   Daca am ajuns pe ultimul nivel, studiem cele doua cazuri pentru E(L) :
    * poate urma o expresie de nivel 0 intre paranteze: (E(0))
    * poate urma o constanta (pentru alte probleme si o variabila)

   In primul caz, trecem peste '(', evaluam E(0) si trecem peste ')'.
   In cel de-al doilea caz, citim numarul, cifra cu cifra

   Daca nu suntem pe ultimul nivel, vom evalua expresia
   E1(lev+1) op(lev) E2(lev+1) op(lev)...

   Initial, x va fi E1(lev+1), apoi, la al i-ulea operator op(lev) intalnit
    x = E1(lev+1) op(lev) ... op(lev) Ei(lev+1)
    y = x op(lev) E_i+1_(lev+1)

   Cand trimitem parametrii functiei eval, pointerul p este incrementat
   inainte de apelul recursiv
*/

int expr(int lev)
{
    int x, y;
    if(lev == LMAX)
        if(*p == '(')
            ++p, x = expr(0), ++p;
        else
            for(x = 0; *p >= '0' && *p <= '9'; ++p)
                x = x * 10 + *p - '0';
    else
        for(x = expr(lev + 1); strchr(op[lev], *p); x = y)
            y = eval(x, expr(lev + 1), *p++);
    return x;
}

int main()
{
    fgets(S, NX, fopen("evaluare.in", "r"));
    fprintf(fopen("evaluare.out", "w"), "%d\n", expr(0));
    return 0;
}