POJ 1145 - Tree Summing

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

概要

S 式のような形で二分木が与えられ，各ノードは整数を持っている． ルートからリーフまでの整数の和が，与えられた整数 T になるようなパスが存在するかどうか答える．

ただし空の木は，どんな整数 T に対しても no であるとする．

制約

特になし

解法

パースして DFS．「整数」なので負の数も入力に含まれうることに注意…

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct tree {
 7   int v;
 8   const tree *left, *right;
 9   tree(int v_, const tree *l, const tree *r) : v(v_), left(l), right(r) {}
10   ~tree() { delete left; delete right; }
11 
12   bool has(int n) const
13   {
14     if (left == 0 && right == 0) {
15       return n == v;
16     } else {
17       return (left && left->has(n - v)) || (right && right->has(n - v));
18     }
19   }
20 };
21 
22 typedef string::const_iterator Iterator;
23 const tree* parse(Iterator& it, const Iterator& last)
24 {
25   if (it == last) {
26     throw "eof";
27   }
28   if (*it != '(') {
29     throw "parse error";
30   }
31 
32   ++it;
33   if (*it == ')') {
34     ++it;
35     return 0;
36   } else {
37     int v = 0;
38     bool neg = false;
39     if (*it == '-') {
40       neg = true;
41       ++it;
42     }
43     while (*it != '(') {
44       v = 10*v + (*it - '0');
45       ++it;
46     }
47     if (neg) {
48       v = -v;
49     }
50     const tree *left = parse(it, last);
51     const tree *right = parse(it, last);
52     if (*it != ')') {
53       throw "parse error";
54     }
55     ++it;
56     return new tree(v, left, right);
57   }
58 }
59 
60 int main()
61 {
62   int n;
63   while (cin >> n) {
64     string buf;
65     cin >> buf;
66     int kakko = count(buf.begin(), buf.end(), '(');
67     kakko -= count(buf.begin(), buf.end(), ')');
68     while (kakko > 0) {
69       string s;
70       cin >> s;
71       kakko += count(s.begin(), s.end(), '(');
72       kakko -= count(s.begin(), s.end(), ')');
73       buf += s;
74     }
75     Iterator it = buf.begin(), last = buf.end();
76     const tree *t = parse(it, last);
77     if (t) {
78       cout << (t->has(n) ? "yes" : "no") << endl;
79     } else {
80       cout << "no" << endl;
81     }
82     delete t;
83   }
84   return 0;
85 }