Cod sursa(job #754089)

Utilizator SpiderManSimoiu Robert SpiderMan Data 31 mai 2012 16:43:32
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 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>
#include <cctype>

#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 expr( int lev, char *&p ) {
    int x,c,d;

    if( lev == LMAX )
        if( *p == '(' )
            ++p, x = expr(0, p), ++p;
        else
            for( x = 0; isdigit(*p); ++p )
                x = x * 10 + *p - '0';
    else
        for( x = expr(lev+1, p);; ) {
            char xx = *p;
            if (!lev)
                c = xx == '+' ? 1 : xx == '-' ? -1 : 0,d=-5;
            else d = xx == '*' ? 1 : xx == '/' ? -1 : 0,c=-5;
            if (!c || !d) break;
            int a = expr (lev + 1, ++p);
            if (xx=='+') x += a;
            if (xx == '-') x -= a;
            if (xx == '*') x *= a;
            if (xx == '/') x /= a;
        }
    return x;
}

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