UVa 12219 公共表达式消除

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 
 8 const int maxn = 60000;
 9 char s[maxn * 5], *p;
10 int cnt, kase;
11 int vis[maxn];
12 
13 struct node
14 {
15     string s;   //因为运算数是1~4个小写字母，所以这里要用string
16     int left, right;
17     bool operator < (const node& rhs)  const     //有map，所以一定要重载
18     {
19         if (s != rhs.s)       return s < rhs.s;
20         if (left != rhs.left)    return left < rhs.left;
21         return right < rhs.right;
22     }
23 }tree[maxn];
24 
25 map<node, int>dict;
26 
27 int solve()
28 {
29     int id = ++cnt;  //从1开始编号
30     node& t = tree[id];  //引用，比较方便
31     t.s = "";
32     t.left = t.right = -1;
33     while (*p >= ‘a‘ && *p <= ‘z‘)   //先把根输入进去
34     {
35         t.s.push_back(*p);
36         p++;
37     }
38 
39     //递归处理左右子树
40     if (*p == ‘(‘)
41     {
42         p++;  //跳过‘(‘
43         t.left = solve(),  p++;     //跳过‘,‘
44         t.right = solve(), p++;     //跳过‘)‘
45     }
46 
47     if (dict.count(t))   //如果已经出现过
48     {
49         cnt--;
50         return dict[t];   //直接返回子树编号
51     }
52     return dict[t] = id;  //没出现过，编号并返回
53 }
54 
55 
56 void print(int u)
57 {
58     if (vis[u]==kase)     cout << u ;   //如果子树已经输出过，直接输出编号
59     else
60     {
61         vis[u] = kase;
62         cout << tree[u].s;
63         //递归输出左右子树
64         if (tree[u].left != -1)
65         {
66             cout << "(";
67             print(tree[u].left);
68             cout << ",";
69             print(tree[u].right);
70             cout << ")";
71         }
72     }
73 }
74 
75 int main()
76 {
77     //freopen("D:\\txt.txt", "r", stdin);
78     int T;
79     cin >> T;
80     for (kase = 1; kase <= T;kase++)
81     {
82         dict.clear();
83         cnt = 0;
84         cin >> s;
85         p = s;
86         print(solve());  //返回根编号，递归输出
87         cout << endl;
88     }
89     return 0;
90 }