Cod sursa(job #1006296)

Utilizator misu007Pogonaru Mihai misu007 Data 6 octombrie 2013 20:19:33
Problema Evaluarea unei expresii Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[100001];

struct nod
{
    char x;
    int y,e;
    nod *s,*d;
};

void init(nod *&p)
{
    p=new nod;
    p->s=NULL;
    p->d=NULL;
}

int numar(int x,int y)
{
    s[y]='\0';
    int z=atoi(s+x);
    return z;
}

nod *fp(int x,int y)
{
    int i,poz=-1,e=0,nr=0;
    nod *p;
    init(p);
    for(i=x;i<y&&!e;++i)
    {
        if(s[i]=='(') ++nr;
        else
        {
            if(s[i]==')') --nr;
            else
            {
                if(!nr)
                {
                    if(s[i]=='*'||s[i]=='/') poz=i;
                    else if(s[i]=='-'||s[i]=='+') e=1;
                }
            }
        }
    }
    if(e)
    {
        --i;
        p->e=1;
        p->x=s[i];
        p->s=fp(x,i);
        p->d=fp(i+1,y);
    }
    else
    {
        if(poz==-1)
        {
            if(s[x]=='(') p=fp(x+1,y-1);
            else
            {
                p->e=0;
                p->y=numar(x,y);
            }
        }
        else
        {
            p->e=1;
            p->x=s[poz];
            p->s=fp(x,poz);
            p->d=fp(poz+1,y);
        }
    }
    return p;
}

int ev(nod *p)
{

    if(p->e)
    {
        switch(p->x)
        {
            case '-': return ev(p->s)-ev(p->d);
            case '+': return ev(p->s)+ev(p->d);
            case '*': return ev(p->s)*ev(p->d);
            case '/': return ev(p->s)/ev(p->d);
        }
    }
    else return p->y;
}

void scrie(nod *p)
{
    if(p)
    {
        scrie(p->s);scrie(p->d);
        if(p->e)printf("%c ",p->x);
        else printf("%d ",p->y);
    }
}

int main()
{
    freopen("evaluare.in","r",stdin);
    freopen("evaluare.out","w",stdout);
    nod *p;
    scanf("%s",s);
    p=fp(0,strlen(s));
    //scrie(p);
    printf("%d\n",ev(p));
    return 0;
}