UVa 112 - Tree Summing（树的各路径求和,递归）

 1 #include <bits/stdc++.h>
 2 #define MAX 100010
 3 
 4 using namespace std;
 5 
 6 char Input()
 7 {
 8     char str;
 9     scanf("%c",&str);
10     while(str == ‘ ‘ || str == ‘\n‘)
11         scanf("%c",&str);
12     return str;
13 }
14 
15 int work(int v,int *leaf)
16 {
17     int temp, value;
18     scanf("%d",&value);
19     temp = Input();
20     int max_num=0,left=0,right=0;
21     if(temp == ‘(‘)
22     {
23         if(work(v-value,&left))  max_num=1;
24         temp = Input();
25         if(work(v-value,&right)) max_num=1;
26         temp = Input();
27         if(left&&right) max_num = (v == value);
28     }
29     else *leaf = 1;
30     return max_num;
31 }
32 int main()
33 {
34     int n,temp;
35     while(~scanf("%d",&n))
36     {
37         Input();
38         if(work(n,&temp))
39             printf("yes\n");
40         else
41             printf("no\n");
42     }
43     return 0;
44 }

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 //递归扫描输入的整棵树
 5 bool ScanTree(int nSum, int nDest, bool *pNull) {
 6     static int nChild;
 7     //略去当前一级前导的左括号
 8     cin >> (char&)nChild;
 9     //br用于递归子节点的计算结果，bNull表示左右子是否为空
10     bool br = false, bNull1 = false, bNull2 = false;
11     //如果读入值失败，则该节点必为空
12     if (!(*pNull = ((cin >> nChild) == 0))) {
13         //总和加上读入的值，遍例子节点
14         nSum += nChild;
15         //判断两个子节点是否能返回正确的结果
16         br = ScanTree(nSum, nDest, &bNull1) | ScanTree(nSum, nDest, &bNull2);
17         //如果两个子节点都为空，则本节点为叶，检验是否达到目标值
18         if (bNull1 && bNull2) {
19             br = (nSum == nDest);
20         }
21     }
22     //清除节点为空时cin的错误状态
23     cin.clear();
24     //略去当前一级末尾的右括号
25     cin >> (char&)nChild;
26     return br;
27 }
28 //主函数
29 int main(void) {
30     bool bNull;
31     //输入目标值
32     for (int nDest; cin >> nDest;) {
33         //根据结果输出yes或no
34         cout << (ScanTree(0, nDest, &bNull) ? "yes" : "no") << endl;
35     }
36     return 0;
37 }

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAXN 10000
 4 
 5 int stack[MAXN];
 6 int topc, top, t;
 7 
 8 bool judge() {
 9     int sum = 0;
10     for (int i=1; i<=top; i++)
11         sum += stack[i];
12     if (sum == t)
13         return true;
14     return false;
15 }
16 
17 int main() {
18 
19     //freopen("f:\\out.txt", "w", stdout);
20     while (scanf("%d", &t) != EOF) {
21         int tmp = 0, flag = 0, isNeg = 0;
22         char pre[4];
23         topc = top = 0;
24         memset(pre, 0, sizeof (pre));
25 
26         while (1) {
27             // 接收字符的代码，忽略掉空格和换行
28             char ch = getchar();
29             while (‘\n‘==ch || ‘ ‘==ch)
30                 ch = getchar();
31 
32             // 记录该字符前三个字符，便于判断是否为叶子
33             pre[3] = pre[2];
34             pre[2] = pre[1];
35             pre[1] = pre[0];
36             pre[0] = ch;
37 
38             // 如果遇到左括弧就进栈
39             if (‘(‘ == ch) {
40                 topc++;
41                 if (tmp) {
42                     if (isNeg) {
43                         tmp *= -1;
44                         isNeg = 0;
45                     }
46                     stack[++top] = tmp;
47                     tmp = 0;
48                 }
49                 continue;
50             }
51 
52             // 如果遇到右括弧就出栈
53             if (‘)‘ == ch) {
54                 // 如果为叶子便计算
55                 if (‘(‘==pre[1] && ‘)‘==pre[2] && ‘(‘==pre[3]) {
56                     if (!flag)
57                         flag = judge();
58                 }
59                 else if (pre[1] != ‘(‘){
60                     top--;
61                 }
62                 topc--;
63                 // 如果左括弧都被匹配完说明二叉树输入完毕
64                 if (!topc)
65                     break;
66                 continue;
67             }
68             if (‘-‘ == ch)
69                 isNeg = 1;
70             else
71                 tmp = tmp*10 + (ch-‘0‘);
72         }
73 
74         if (flag)
75             printf("yes\n");
76         else
77             printf("no\n");
78     }
79 
80     return 0;
81 }