Cod sursa(job #754101)

Utilizator SpiderManSimoiu Robert SpiderMan Data 31 mai 2012 16:59:10
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
/*
   Evaluarea unei fesii - dupa o idee de Sima Cotizo (job ID 144801)

   Definim recursiv o fesie 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 fesii de nivel k+1, iar
   o(k) sunt operatori cu nivel de prioritate k

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

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

#include <cstdio>
#include <cstring>
#include <cctype>

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

int f(int L,char*&p){int x,c,d;if(L==2)if(*p=='(')++p,x=f(0,p),++p;else for(x=0;isdigit(*p);++p)x=x*10+*p-'0';else for(x=f(L+1,p);;){char X=*p;if(L)d=X=='*'?1:X=='/'?2:0,c=3;else c=X=='+'?1:X=='-'?2:0,d=3;if(!c||!d)break;int a=f(L+1,++p);if(c==1)x+=a;if(c==2)x-=a;if(d==1)x*=a;if(d==2)x/=a;}return x;}

int e(char * &s,int l=0,int v=0) {
    if(l==2) {
        if(*s=='(') {
            ++s;
            int r=e(s);
            ++s;
            return r;
        } else if(*s>='0'&&*s<='9') {
            int r=v*10+(*s)-'0';
            return e(++s,2,r);
        } else return v;
    } else if(l==1) {
        int r=e(s,2);
        while(1) {
            if(*s=='*')r*=e(++s,2);
            else if(*s=='/')r/=e(++s,2);
            else return r;
        }
    } else {
        int v=e(s,1);
        while(1) {
            if(*s=='+')v+=e(++s,1);
            else if(*s=='-')v-=e(++s,1);
            else return v;
        }
    }
}
int main() {
    fgets( S, NX, fopen( "evaluare.in", "r" ) );
    fprintf( fopen( "evaluare.out", "w" ), "%d\n", f(0, p) );
    return 0;
}