POJ 2269 - Friends

http://poj.org/problem?id=2269

概要

以下の規則に従って与えられた集合演算の結果を答える．

• 集合の要素は 'A' から 'Z'
• {ABC} という構文で集合を表す
• + は集合和，- は集合差，* は集合積を表す
• * は +, - よりも優先順位が高い
• すべての演算子は左結合
• () でグルーピング
• 余計な文字は式の中に含まれない

制約

• 式は255文字以下

解法

LL(1) で構文解析しつつ計算．

集合演算に関しては，STL に

• set_union
• set_difference
• set_intersection

というそのものな関数があるので，それを利用した．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 typedef string::const_iterator Iterator;
 6 
 7 string eval(Iterator& it, const Iterator& last);
 8 string eval_term(Iterator& it, const Iterator& last);
 9 string eval_factor(Iterator& it, const Iterator& last);
10 
11 string eval_factor(Iterator& it, const Iterator& last)
12 {
13   if (it == last) {
14     throw "exhausted";
15   } else if (*it == '{') {
16     ++it;
17     Iterator jt = find(it, last, '}');
18     const string r(it, jt);
19     it = jt+1;
20     return r;
21   } else if (*it == '(') {
22     ++it;
23     const string r = eval(it, last);
24     if (it == last || *it != ')') {
25       throw "unmatched paren";
26     }
27     ++it;
28     return r;
29   } else {
30     throw "unknown term";
31   }
32 }
33 
34 string eval_term(Iterator& it, const Iterator& last)
35 {
36   string r = eval_factor(it, last);
37   while (it != last && *it == '*') {
38     ++it;
39     const string l = eval_factor(it, last);
40     string t;
41     set_intersection(r.begin(), r.end(), l.begin(), l.end(), back_inserter(t));
42     r = t;
43   }
44   return r;
45 }
46 
47 string eval(Iterator& it, const Iterator& last)
48 {
49   string r = eval_term(it, last);
50   while (it != last && (*it == '+' || *it == '-')) {
51     const char op = *it;
52     ++it;
53     const string l = eval_term(it, last);
54     string t;
55     switch (op) {
56       case '+':
57         set_union(r.begin(), r.end(), l.begin(), l.end(), back_inserter(t));
58         break;
59       case '-':
60         set_difference(r.begin(), r.end(), l.begin(), l.end(), back_inserter(t));
61         break;
62       default:
63         throw "unknown operator";
64     }
65     r = t;
66   }
67   return r;
68 }
69 
70 int main()
71 {
72   string line;
73   while (cin >> line) {
74     Iterator it = line.begin(), last = line.end();
75     cout << "{" << eval(it, last) << "}" << endl;
76   }
77   return 0;
78 }