UVa 11234 Expressions

　　先构建一个表达式树，构建方式：从右向左读字符串，如果该字符是大写字母，则构建右子树，接着构建左子树，用递归进行实现。接着层次遍历该树，把得到的结果逆序输出。

　　代码如下：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <queue>
 5 #include <cctype>
 6 using namespace std;
 7 
 8 const int maxn = 10000+10;
 9 
10 struct Node
11 {
12     char value;
13     Node *left, *right;
14 };
15 
16 Node * newnode()
17 {
18     Node * u = (Node *)malloc(sizeof(Node));
19     if(u != NULL)
20     {
21         u->value = '\0';
22         u->left = u->right = NULL;
23     }
24     return u;
25 }
26 
27 int len, cur;
28 char s[maxn];
29 
30 void build(Node * p)
31 {
32     if(cur < 0)   return;
33     p->value = s[cur--];
34     if(isupper(p->value))
35     {
36         if(p->right == NULL)   p->right = newnode();
37         build(p->right);
38         if(p->left == NULL)   p->left = newnode();
39         build(p->left);
40     }
41 }
42     
43 void remove_tree(Node * u)
44 {
45     if(u)   return;
46     remove_tree(u->left);
47     remove_tree(u->right);
48     free(u);
49 }
50 
51 Node * root;
52 
53 char ans[maxn];
54 void traversal(Node * root)
55 {
56     queue<Node *> q;
57     q.push(root);
58     int n = 0;
59     while(!q.empty())
60     {
61         Node * u = q.front();
62         ans[n++] = u->value;
63         q.pop();
64         if(u->left)   q.push(u->left);
65         if(u->right)   q.push(u->right);
66     }
67 }
68 
69 int main()
70 {
71 #ifdef LOCAL    
72     freopen("in", "r", stdin);
73 #endif
74     int T;
75     scanf("%d", &T);
76     while(T--)
77     {
78         scanf("%s", s);
79         len = strlen(s);
80         cur = len - 1;
81         root = newnode();
82         build(root);
83         traversal(root);
84         remove_tree(root);
85         for(int i = len-1; i >= 0; i--)
86             printf("%c", ans[i]);
87         printf("\n");
88     }
89     return 0;
90 }

　　代码中试着用了queue，不小心忘写using namespace std了，编译出错那个纠结啊...