Cod sursa(job #968027)

Utilizator geniucosOncescu Costin geniucos Data 29 iunie 2013 18:48:39
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int nr,i,j,n,S[100009],st[100009],dr[100009];
char sir[100009];
int val(int x,int y)
{
    int pz1,p,i,sum=0,vv,semn=1;
    vector < pair < int , int > > X;
    vector < pair < int , int > >::iterator it;
    vector < char > smn;
    while(y==dr[x]&&sir[x]=='(')
    {
        x++;
        y--;
    }
    if(y==dr[x]&&sir[x]>='0'&&sir[x]<='9')
    {
        for(i=x;i<=y;i++)
            sum=sum*10+sir[i]-48;
        return sum;
    }
    for(i=x;i<=y&&dr[i]<=y;i=dr[i]+2)
    {
        X.push_back(make_pair(i,dr[i]));
        if(dr[i]+1<=y) smn.push_back(sir[dr[i]+1]);
    }
    pz1=0;
    while(pz1<X.size())
    {
        p=val(X[pz1].first,X[pz1].second);
        for(i=pz1+1;i<X.size()&&(smn[i-1]=='*'||smn[i-1]=='/');i++)
        {
            vv=val(X[i].first,X[i].second);
            if(smn[i-1]=='*') p*=vv;
            else p/=vv;
        }
        sum+=p*semn;
        if(smn[i-1]=='+') semn=1;
        else semn=-1;
        pz1=i;
    }
    return sum;
}
int main()
{
freopen("evaluare.in","r",stdin);
freopen("evaluare.out","w",stdout);
gets(sir+1);
if(sir[1]=='-') while(1);
n=strlen(sir+1);
for(i=1;i<=n;i++)
    if(sir[i]=='('||sir[i]==')')
    {
        if(sir[i]=='(')
        {
            nr++;
            S[nr]=i;
        }
        else
        if(sir[i]==')')
        {
            dr[S[nr]]=i;
            st[i]=S[nr];
            nr--;
        }
    }
for(i=n;i>=1;i--)
    if(sir[i]>='0'&&sir[i]<='9')
    {
        j=i;
        while(sir[j]>='0'&&sir[j]<='9')
        {
            dr[j]=i;
            j--;
        }
        j++;
        i=j;
    }
printf("%d\n",val(1,n));
return 0;
}