Cod sursa(job #987925)

Utilizator misu007Pogonaru Mihai misu007 Data 21 august 2013 17:41:06
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 3.26 kb
#include <cstdio>
#include <cstring>
using namespace std;

char expr[200002],exprfp[200002];
int k=0,n;

void cit()
{
    freopen("evaluare.in","r",stdin);
    freopen("evaluare.out","w",stdout);
    scanf("%s",&expr);
    n=strlen(expr);
}

int prio(char c)
{
    switch(c)
    {
        case '+':
        case '-': return 2;
        case '*':
        case '/': return 3;
        case ')': return 1;
        case '(': return 0;
        default: return 4;
    }
}

void fp()
{
    int i=0,st1=0,e;
    char st[200002];
    while(expr[i]!='\0')
    {
        switch(prio(expr[i]))
        {
            case 3: e=0;
                    if(st1>0) if(3==prio(st[st1-1])) e=1;
                    while(e)
                    {
                        exprfp[k++]=st[--st1];
                        if(st1<1) e=0;
                        if(e) if(3!=prio(st[st1-1])) e=0;
                    }
                    st[st1++]=expr[i++];
                    break;
            case 2: e=0;
                    if(st1>0) if(2<=prio(st[st1-1])) e=1;
                    while(e)
                    {
                        exprfp[k++]=st[--st1];
                        if(st1<1) e=0;
                        if(e) if(2>prio(st[st1-1])) e=0;
                    }
                    st[st1++]=expr[i++];
                    break;
            case 1: while(st[st1-1]!='(')
                    {
                        exprfp[k++]=st[--st1];
                    }
                    st1--;
                    i++;
                    break;
            case 0: st[st1++]=expr[i++];
                    break;
            default: exprfp[k++]=expr[i];
                     while(prio(expr[++i])==4&&i<n)
                     {
                         exprfp[k++]=expr[i];
                     }
                     exprfp[k++]='#';
                     break;
        }
    }
    while(st1>0)
    {
        exprfp[k++]=st[--st1];
    }
}

int conv(char c)
{
    switch(c)
    {
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default: return -1;
    }
}

void eval()
{
    int i=0,st[200000],st1=0;
    while(i<k)
    {
        switch(prio(exprfp[i]))
        {
            case 4: st[st1]=0;
                    while(exprfp[i]!='#')
                    {
                        st[st1]=st[st1]*10+conv(exprfp[i++]);
                    }
                    st1++;
                    i++;
                    break;
            default: switch(exprfp[i++])
                     {
                         case '*':st[st1-2]=st[--st1]*st[--st1];break;
                         case '/':st[st1-2]=st[st1-2]/st[--st1];--st1;break;
                         case '+':st[st1-2]=st[--st1]+st[--st1];break;
                         case '-':st[st1-2]=st[st1-2]-st[--st1];--st1;break;
                     }
                     st1++;
                     break;
        }
    }
    printf("%d\n",st[0]);
}

int main()
{
    cit();
    fp();
    eval();
    return 0;
}