AOJ 2255 - 6/2(1+2)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255

概要

数と括弧と四則演算からなる式が与えられる． 括弧の中は先に計算しなければならないが，四則演算に関してはどの演算から計算しても構わないとしたとき，式の計算結果が何通りあるか答える．

ただし割り算のときは絶対値の小さいほうに丸め，計算の途中にゼロ割が発生するような場合はカウントしない．

制約

• 演算子は10個以下
• 入力は常に式として正しい
• 式の長さは200文字以下
  • 演算子が10個以下なので実際には100文字もない
• 計算の途中および結果の値は 10^9 以下

解法

演算子のところで区切りつつ，全通り計算を試して結果を set に入れて set のサイズを出力する． 括弧の対応さえとれればいいので，LL(1) なかんじにパーサを書く必要は無い．

式 str を受けとって set を返す eval を

• str が数値のみなら，その数値だけからなる set を返す (base case)
• str が括弧で括られた式のみなら，括弧をはずして eval
• str が演算子を含んでいたら，各演算子について左右の式をそれぞれ結合して eval して，その結果のそれぞれの要素に関して演算を行って set に入れて返す

みたいに実装した． 実行効率はよくないけど AOJ で 00:00:15 なのでまぁ十分では．

  1 #include <iostream>
  2 #include <vector>
  3 #include <sstream>
  4 #include <set>
  5 #include <functional>
  6 #include <cassert>
  7 using namespace std;
  8 
  9 typedef string::const_iterator Iterator;
 10 
 11 Iterator matching_paren(Iterator it, const Iterator& last)
 12 {
 13   for (int d = 1; it != last; ++it) {
 14     if (*it == ')') {
 15       --d;
 16       if (d == 0) {
 17         return it;
 18       }
 19     } else if (*it == '(') {
 20       ++d;
 21     }
 22   }
 23   throw "paren mismatch";
 24 }
 25 
 26 set<int> eval(const string& str)
 27 {
 28   vector<string> terms;
 29   vector<char> ops;
 30   string term;
 31   for (string::const_iterator it(str.begin()), end = str.end(); it != end; ++it) {
 32     if ('0' <= *it && *it <= '9') {
 33       term += *it;
 34     } else if (*it == '(') {
 35       if (!term.empty()) {
 36         terms.push_back(term);
 37       }
 38       term = "";
 39       Iterator l = matching_paren(it+1, end);
 40       term = string(it, l+1);
 41       it = l;
 42     } else {
 43       if (!term.empty()) {
 44         terms.push_back(term);
 45       }
 46       term = "";
 47       assert(*it == '+' || *it == '-' || *it == '*' || *it == '/');
 48       ops.push_back(*it);
 49     }
 50   }
 51   terms.push_back(term);
 52   assert(ops.size()+1 == terms.size());
 53 
 54   if (ops.empty()) {
 55     if (terms[0][0] == '(') {
 56       return eval(terms[0].substr(1, terms[0].size()-2));
 57     } else {
 58       set<int> s;
 59       istringstream iss(terms[0]);
 60       int x;
 61       iss >> x;
 62       s.insert(x);
 63       return s;
 64     }
 65   } else {
 66     set<int> s;
 67     for (vector<char>::size_type i = 0; i < ops.size(); i++) {
 68       string lhs;
 69       for (vector<string>::size_type j = 0; j <= i; j++) {
 70         if (j != 0) {
 71           lhs += ops[j-1];
 72         }
 73         lhs += terms[j];
 74       }
 75       const set<int> l = eval(lhs);
 76       string rhs;
 77       for (vector<string>::size_type j = i+1; j < terms.size(); j++) {
 78         if (j != i+1) {
 79           rhs += ops[j-1];
 80         }
 81         rhs += terms[j];
 82       }
 83       const set<int> r = eval(rhs);
 84       for (set<int>::const_iterator jt(l.begin()); jt != l.end(); ++jt) {
 85         for (set<int>::const_iterator kt(r.begin()); kt != r.end(); ++kt) {
 86           switch (ops[i]) {
 87             case '+': s.insert(*jt + *kt);  break;
 88             case '-': s.insert(*jt - *kt);  break;
 89             case '*': s.insert(*jt * *kt);  break;
 90             case '/': if (*kt != 0) { s.insert(*jt / *kt); }  break;
 91           }
 92         }
 93       }
 94     }
 95     return s;
 96   }
 97 }
 98 
 99 int main()
100 {
101   for (string s; cin >> s && s != "#";) {
102     cout << eval(s).size() << endl;
103   }
104   return 0;
105 }