AOJ 1012 - Operations with Finite Sets

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

概要

1個から5個の有限集合が与えられ，さらに集合演算を表す式が与えられるのでその結果を答える． ただし，結果が空集合のときは「NULL」と答える．

集合演算には

がある．問題文には明記されていないけど，すべての二項演算子は左結合．

補集合をとるときの全体集合とは，与えられた集合の和集合とする．

制約

解法

構文解析の後，言われた通りに集合演算するだけ．

入力の最後を検出するのがめんどくさい． eofbit は「読み込んでみたら EOF だった」ときに立つので，ignore() した後に peek() することで eofbit を立てることができる．

  1 #include <iostream>
  2 #include <vector>
  3 #include <iterator>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 typedef string::const_iterator Iterator;
  8 
  9 struct evaluator
 10 {
 11   vector<int> all;
 12   vector<int> sets[5];
 13 
 14   vector<int> factor(Iterator& it, const Iterator& last) const
 15   {
 16     if (*it == '(') {
 17       ++it;
 18       const vector<int> r = expr(it, last);
 19       ++it;
 20       return r;
 21     } else {
 22       const int i = *it-'A';
 23       ++it;
 24       return sets[i];
 25     }
 26   }
 27 
 28   vector<int> term(Iterator& it, const Iterator& last) const
 29   {
 30     if (*it == 'c') {
 31       ++it;
 32       const vector<int> s = factor(it, last);
 33       vector<int> r;
 34       set_difference(all.begin(), all.end(), s.begin(), s.end(), back_inserter(r));
 35       return r;
 36     } else {
 37       return factor(it, last);
 38     }
 39   }
 40 
 41   vector<int> expr(Iterator& it, const Iterator& last) const
 42   {
 43     vector<int> r = term(it, last);
 44     while (it != last && (*it == 'u' || *it == 'i' || *it == 'd' || *it == 's')) {
 45       const char op = *it;
 46       ++it;
 47       const vector<int> l = term(it, last);
 48       vector<int> o;
 49       switch (op) {
 50         case 'u':
 51           set_union(r.begin(), r.end(), l.begin(), l.end(), back_inserter(o));
 52           break;
 53         case 'i':
 54           set_intersection(r.begin(), r.end(), l.begin(), l.end(), back_inserter(o));
 55           break;
 56         case 'd':
 57           set_difference(r.begin(), r.end(), l.begin(), l.end(), back_inserter(o));
 58           break;
 59         case 's':
 60           set_symmetric_difference(r.begin(), r.end(), l.begin(), l.end(), back_inserter(o));
 61           break;
 62       }
 63       swap(r, o);
 64     }
 65     return r;
 66   }
 67 };
 68 
 69 int main()
 70 {
 71   while (!cin.eof()) {
 72     string name;
 73     int n;
 74     evaluator e;
 75     while (cin >> name >> n && name != "R") {
 76       vector<int>& s = e.sets[name[0]-'A'];
 77       for (int i = 0; i < n; i++) {
 78         int x;
 79         cin >> x;
 80         e.all.push_back(x);
 81         s.push_back(x);
 82       }
 83       sort(s.begin(), s.end());
 84     }
 85     sort(e.all.begin(), e.all.end());
 86     e.all.erase(unique(e.all.begin(), e.all.end()), e.all.end());
 87 
 88     string s;
 89     cin >> s;
 90     Iterator it = s.begin(), last = s.end();
 91     const vector<int> r = e.expr(it, last);
 92     if (r.empty()) {
 93       cout << "NULL" << endl;
 94     } else {
 95       for (vector<int>::const_iterator it = r.begin(); it != r.end(); ++it) {
 96         if (it != r.begin()) {
 97           cout << ' ';
 98         }
 99         cout << *it;
100       }
101       cout << endl;
102     }
103 
104     cin.ignore();
105     cin.peek();
106   }
107   return 0;
108 }
aoj/1012.cc