Cod sursa(job #456555)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 15 mai 2010 22:58:26
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define inf "evaluare.in"
#define outf "evaluare.out"
#define LMax 100100
#define INF 0x3f3f3f3f
using namespace std;

int k,n;
int p[LMax],pfp[LMax];
char efp[LMax][20];
char e[LMax][20];
char sir[LMax];
char fp[LMax][20];
int t;
int st[LMax];

struct Nod
{
char op[20];
Nod *as,*ad;
};

Nod *v;

void read()
{
scanf("%s",sir+1);
for(int i=1; i<=strlen(sir+1); i++ )
    if( (int)(sir[i])>=(int)('0') && (int)(sir[i])<=(int)('9') )
        {
        k++;
        e[k][0] = sir[i];
        int j=i+1;
        while( (int)(sir[j])>=(int)('0') && (int)(sir[j])<=(int)('9') )  e[k][ strlen(e[k]) ] = sir[j] , j++ ;
        j--;
        i = j;
        }
    else
        {
        k++;
        e[k][0] = sir[i];
        }
}

Nod* arb(int li,int ls)
{
int poz,min;
min = pfp[ls];
poz=ls;
for(int i=ls-1; i>=li; i-- )
    if( pfp[i]<min )
        {
        min=pfp[i];
        poz=i;
        }
Nod *c=new Nod;
strcpy( c->op, efp[poz] );
if( li==ls ) c->as = c->ad = 0;
else
    {
    c->as = arb(li,poz-1);
    c->ad = arb(poz+1,ls);
    }
return c;
}

void SDV(Nod *s)
{
if( s )
    {
    SDV( s->as );
    SDV( s->ad );
    strcpy( fp[++t], s->op );
    }
}

void solve()
{
int j=0;
for(int i=1; i<=k; i++)
    switch( e[i][0] )
        {
        case ')' : j-=10 ; break;
        case '(' : j+=10 ; break;
        case '+' : p[i]=1+j; break;
        case '-' : p[i]=1+j; break;
        case '*' : p[i]=10+j; break;
        case '/' : p[i]=10+j; break;
        default : p[i]=INF;
        }
for(int i=1; i<=k; i++)
    if( e[i][0]!='(' && e[i][0]!=')' )
        {
        n++;
        strcpy( efp[n], e[i] );
        pfp[n] = p[i];
        }
v = arb(1,n);
SDV(v);
t=0;
for(int i=1; i<=n; i++)
    if( fp[i][0]=='+' || fp[i][0]=='-' || fp[i][0]=='*' || fp[i][0]=='/' )
        {
        int rez=0;
        switch( fp[i][0] )
            {
            case '+' : rez = st[t]+st[t-1]; break;
            case '-' : rez = st[t-1]-st[t]; break;
            case '*' : rez = st[t]*st[t-1]; break;
            case '/' : rez = st[t-1]/st[t]; break;
            }
        t--;
        st[t]=rez;
        }
    else t++, st[t] = atol( fp[i] );
//for(; t; t-- ) printf("%d ",st[t]);
printf("%d",st[t]);
//for(int i=1; i<=n; i++) printf("%s ",fp[i]);
}

int main()
{
freopen(inf,"r",stdin);
freopen(outf,"w",stdout);
read();
solve();
return 0;
}