Cod sursa(job #550367)

Utilizator SadmannCornigeanu Calin Sadmann Data 9 martie 2011 13:56:34
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
//Parcurgem expresia tinand cont de nivelurile subexpresiilor
//si de nivelurile de prioritate a operatorilor


#include<stdio.h>
#include<string.h>
#define NMAX 1<<17
#define LMAX 2
FILE *in,*out;
char op[4][4] = { "+-", "*/", "^", "" };
char S[NMAX],*p;

/*
   In fiecare nod al arborelui, vom retine o valoare (in cazul frunzeolor)
   sau un operator (in cazul nodurilor interne), si doi pointeri catre
   fii stang, respectiv drept ai nodului

   Constructorul seteaza toti membrii cu valoarea nula
   *A este un pointer catre radacina arborelui
*/

typedef struct node
{
    int val;
    char op;
    node *l,*r;
    node(int a=0,char b=0,node *c=0,node *d=0):
            val(a),op(b),l(c),r(d) {}
};
node *A;

/*
   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
*/

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

}

int eval( node *n ) {
	switch( n->op ) {
		case '+': return eval( n->l ) + eval( n->r );
		case '-': return eval( n->l ) - eval( n->r );
		case '*': return eval( n->l ) * eval( n->r );
		case '/': return eval( n->l ) / eval( n->r );
		default: return n->val;
	}
}


int main()
{
    in=fopen("fp.in","rt");
    out=fopen("fp.out","wt");
    fscanf(in,"%s",S);
    S[strlen(S)]='\n';
    p=S;

    A=expr(0);
    fclose(in);
    fprintf(out,"%d\n",eval(A));

    return 0;
}