Cod sursa(job #349047)

Utilizator freak93Adrian Budau freak93 Data 17 septembrie 2009 20:26:39
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include<cstring>
#include<cstdio>
#include<stack>

using namespace std;

const char iname[]="evaluare.in";
const char oname[]="evaluare.out";
const int maxn=200005;
const int add=1000000003;
const int sub=1000000004;
const int mul=1000000005;
const int divi=1000000006;
const int left=1000000001;
const int right=1000000002;

char s[maxn];

int n,i,j,a[maxn],k,lp,inv,x;

stack<int> S;

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);

    fgets(s,sizeof(s),stdin);
    n=strlen(s);
    i=0;
    for(;i<n;)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            x=0;
            while(s[i]>='0'&&s[i]<='9')
                x=(x<<1)+(x<<3)+s[i]-'0',++i;
            a[++k]=x;
            if(inv)
                a[k]=-a[k],inv=0;
            lp=1;
            continue;
        }

        if(s[i]=='+')
        {
            while(!S.empty()&&S.top()>right)
                a[++k]=S.top(),S.pop();
            S.push(add);
            ++i;
            lp=0;
            continue;
        }

        if(s[i]=='*')
        {
            while(!S.empty()&&S.top()>sub)
                a[++k]=S.top(),S.pop();
            S.push(mul);
            ++i;
            lp=0;
            continue;
        }
        if(s[i]=='/')
        {
            while(!S.empty()&&S.top()>sub)
                a[++k]=S.top(),S.pop();
            S.push(divi);
            ++i;
            lp=0;
            continue;
        }
        if(s[i]=='-')
        {
            if(lp==0)
            {
                inv^=1;
                ++i;
                continue;
            }
            while(!S.empty()&&S.top()>right)
                a[++k]=S.top(),S.pop();
            S.push(sub);
            lp=0;
            ++i;
            continue;
        }
        if(s[i]=='(')
        {
            S.push(left);
            ++i;
            lp=0;
            continue;
        }
        if(s[i]==')')
        {
            while(S.top()!=left)
                a[++k]=S.top(),S.pop();
            S.pop();
            lp=1;
            ++i;
            continue;
        }
        ++i;
    }

    while(!S.empty())
        a[++k]=S.top(),S.pop();


    for(i=1;i<=k;++i)
        if(a[i]<add)
            S.push(a[i]);
        else
        {
            x=S.top();S.pop();
            if(a[i]==add)
                S.top()+=x;
            else
                if(a[i]==sub)
                    S.top()-=x;
                else
                    if(a[i]==mul)
                        S.top()*=x;
                    else
                        S.top()/=x;
        }

    printf("%d\n",S.top());

    fclose(stdin);
    fclose(stdout);

    return 0;
}