Cod sursa(job #67657)

Utilizator stef2nStefan Istrate stef2n Data 25 iunie 2007 13:07:26
Problema Eval Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasele 11-12 Marime 2.69 kb
// MEMORIE !!!!!!!!!!!!!!!!!!!!!!!!!!!!
// NUMERE MARI !!!!!!!!!!!!!!!!!!!!!!!!
// SEMN !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


#include <cstdio>
#include <cstring>

#define LUNGMAX 100005
#define NMAX 30

int N,val[NMAX],L,poz;
char expr[LUNGMAX];
int pair[LUNGMAX],st[LUNGMAX],niv,plus[LUNGMAX];

void read_data()
  {
   scanf("%d\n",&N);
   for(int i=0;i<N;i++)
      scanf("%d\n",&val[i]);
   fgets(expr,LUNGMAX,stdin);
  }

void init()
  {
   poz=L-1;
   for(int i=L-1;i>=0;--i)
      if(expr[i]!='+' && expr[i]!='-')
        expr[poz--]=expr[i];
      else
        if(i>0 && (expr[i-1]=='+' || expr[i-1]=='-'))
          if(expr[i]=='-')
            if(expr[i-1]=='+')
              expr[i-1]='-';
            else
              expr[i-1]='+';
          else{}
        else
          expr[poz--]=expr[i];
   niv=0;
   for(int i=poz+1;i<L;i++)
      if(expr[i]=='(' || expr[i]=='[')
        st[niv++]=i;
      else
        if(expr[i]==')' || expr[i]==']')
          {
           pair[i]=st[niv-1];
           pair[st[niv-1]]=i;
           --niv;
          }
   niv=1;
   st[0]=-1;
   for(int i=L-1;i>poz;--i)
      if(expr[i]=='+' || expr[i]=='-')
        {
         if((i>poz+1 && expr[i-1]=='*') || i==poz+1) //unar
           plus[i]=st[niv-1];
         else //binar
           {
            plus[i]=i;
            st[niv-1]=i;
           }
        }
      else
        {
         plus[i]=st[niv-1];
         if(expr[i]==')' || expr[i]==']')
           st[niv++]=-1;
         else
           if(expr[i]=='(' || expr[i]=='[')
             --niv;
        }
  }

int solve(int li, int ls)
  {
   if(li==ls)
     return val[expr[li]-'a'];
   if(expr[li]=='(' || expr[li]=='[')
     if(pair[li]==ls)
       return solve(li+1,ls-1);
     else
       if(plus[pair[li]+1]==-1 || plus[pair[li]+1]>ls)
         return solve(li+1,pair[li]-1)*solve(pair[li]+2,ls);
       else
         if(expr[plus[pair[li]+1]]=='+')
           return solve(li,plus[pair[li]+1]-1)+solve(plus[pair[li]+1]+1,ls);
         else
           return solve(li,plus[pair[li]+1]-1)-solve(plus[pair[li]+1]+1,ls);
   if(plus[li]!=-1 && plus[li]<=ls)
     if(expr[plus[li]]=='+')
       return solve(li,plus[li]-1)+solve(plus[li]+1,ls);
     else
       return solve(li,plus[li]-1)-solve(plus[li]+1,ls);
   else
     if(expr[li]>='a' && expr[li]<='z')
       return val[expr[li]-'a']*solve(li+2,ls);
     else
       if(expr[li]=='+')
         return solve(li+1,ls);
       else
         return -solve(li+1,ls);
  }


int main()
{
freopen("eval.in","r",stdin);
freopen("eval.out","w",stdout);

read_data();
L=strlen(expr)-1;
init();
printf("%d\n",solve(poz+1,L-1));

return 0;
}