読者です 読者をやめる 読者になる 読者になる

AOJ2255 6/2(1+2)

解法
区間DP。計算結果の重複を防ぐので set memo[l][r]; で計算結果を管理する。

事前に括弧付けされたものは一つの項としてまとめなければならないので、文字列[l,r) が、完全に "(expr)" の形で表せる場合を捉える必要がある。(str[l] = '(', str[r-1] = ')' である必要がある)。左括弧と右括弧の対応が正しくとれているときに括弧の中の expr を再帰する必要があるので、'(' と ')' の数を数える。

string line;
set<int> memo[200][200];
set<PII> used;

set<int> eval(int const l, int const r) {
  
  set<int>& ret = memo[l][r];
  if(l == r) return ret;
  
  if(used.count(MP(l, r))) return ret;
  used.insert(MP(l, r));
  
  // check is digits [l, r)
  bool digits = true;
  for(int i=l; i<r; i++) { digits = digits && isdigit(line[i]); }
  if(digits) { ret.insert(toInt(line.substr(l, r-l))); return ret; }
  
  int par = 0; bool check = true;
  for(int i=l; i<r-1; i++) {
    if(line[i] == '(') { par ++; }
    if(line[i] == ')') { par --; }
    if(par == 0) { check = false; }
  }
  
  // "(expr)"
  if(check) {
    if(line[r-1] == ')') {
      return ret = eval(l+1, r-1);
    }
  }
  
  par = 0;
  // parsing loop
  for(int i=l; i<r; i++) {
    if(line[i] == '(') { par ++; }
    if(line[i] == ')') { par --; }
    if(par != 0) continue;
    
    switch(line[i]) {
    case '+': case '-': case '*': case '/': {
      set<int> st_a = eval(l, i), st_b = eval(i+1, r);
      set<int>::iterator iter_a, iter_b;
      for(iter_a = st_a.begin(); iter_a!=st_a.end(); iter_a++) {
        for(iter_b = st_b.begin(); iter_b!=st_b.end(); iter_b++) {
          if(line[i] == '+') { ret.insert(*iter_a + *iter_b); }
          if(line[i] == '-') { ret.insert(*iter_a - *iter_b); }
          if(line[i] == '*') { ret.insert(*iter_a * *iter_b); }
          if(line[i] == '/') {
            if(*iter_b == 0) continue;
            ret.insert(*iter_a / *iter_b);
          }
        }
      }
      break;
    }
    default:;
    }
  } // for parsing loop
  
  return ret;
}

int main() {
  
  while(cin >> line) {
    for(int i=0; i<200; i++)
      for(int j=0; j<200; j++)
        memo[i][j].clear();
    
    used.clear();
    
    if(line == "#") break;
    cout << eval(0, line.size()).size() << endl;
  }
  
  return 0;
}