AOJ2255 6/2(1+2)
解法
区間DP。計算結果の重複を防ぐので set
事前に括弧付けされたものは一つの項としてまとめなければならないので、文字列[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; }