POJ 3337 Expression Evaluator

問題

変数a〜zおよび+, -からなる式が与えられる。
変数は式中で(一つの変数に対して最大1個の)--または++が前置、または後置されることがある。


変数に++が前置された場合は、式の値を求める前にその変数の値を+1し、

    1. が後置された場合は式の値を求めた後で変数の値を+1する。
    • の場合、同様の順序で変数の値を-1する。


最初変数はa=1,b=2,...,z=26である。
式を評価したときの値および、変数の値を求めよ。

制約条件

式はあいまいに解釈されない。
各変数が式に出るのは最大1回である。

方針

構文解析する。


各変数に対して++などの演算子は最大1しか出現せず、
なおかつ式は2通り以上に解釈されないという制約があるため、
greedyに演算子を解釈していってよい。

ソースコード

int n,cs;
char in[10001];
int value[26];
bool used[26];

int eval(int s,int t){
  int i=t-1;
  if(isalpha(in[i])){
    used[in[i]-'a']=1;
    
    if(i>s+1&&in[i-1]==in[i-2]){
      if(in[i-1]=='-')value[in[i]-'a']--;
      else value[in[i]-'a']++;
      
      int tmp=value[in[i]-'a'];
      if(i>s+3)return eval(s,t-4)+(in[i-3]=='+'?tmp:-tmp);
      return tmp;
    }
    else{
      int tmp=value[in[i]-'a'];
      if(i>s+1)return eval(s,t-2)+(in[i-1]=='+'?tmp:-tmp);
      return tmp;
    }
  }
  else{
    used[in[i-2]-'a']=1;
    int tmp=value[in[i-2]-'a'];
    if(in[i]=='-')value[in[i-2]-'a']--;
    else value[in[i-2]-'a']++;
    
    if(i>s+3)return eval(s,t-4)+(in[i-3]=='+'?tmp:-tmp);
    return tmp;
  }
}

int main(){
  scanf("%d ",&cs);
  while(cs--){
    gets(in);
    printf("Expression: %s\n",in);
    n=0;
    for(int i=0;in[i];i++)if(!isspace(in[i]))in[n++]=in[i];
    in[n]=0;
    rep(i,26)value[i]=i+1, used[i]=0;
    printf("value = %d\n",eval(0,n));
    rep(i,26)if(used[i])printf("%c = %d\n",'a'+i, value[i]);
  }
  return 0;
}