这道题看了刘汝佳的代码真的是天秀， 很值得学习。
具体看代码
#include<cstdio>
#include<iostream>
#include<cctype>
#include<map>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 51234;
struct node
{string s;int l, r;node(string s = "", int l = 0, int r = 0) : s(s), l(l), r(r) {}bool operator < (const node& rhs) const //map用设置优先级 {if(s != rhs.s) return s < rhs.s;if(l != rhs.l) return l < rhs.l;return r < rhs.r;}
}s[MAXN];
map<node, int> g;
int done[MAXN], kase, cnt, k;
string str;int solve()
{string cur;while(isalpha(str[k])) cur += str[k++]; //string很方便， 当作一个数直接加就ok了 int id = ++cnt; //不知道要不要的时候先预留一个id， 然后不要cnt--， 很轻松就删除了。 node& t = s[id] = node(cur, 0, 0); //变量名不想打那么长所以引用来偷懒if(str[k] == '(') //根据括号来拓展 {k++;t.l = solve(); k++;t.r = solve(); k++;}if(g[t]) { cnt--; return g[t]; } //去掉重复 return g[t] = id;
}void print(int u)
{if(done[u] == kase) //省去了清零， 秀！ {printf("%d", u);return;}done[u] = kase;cout << s[u].s; //学习这种输出方式，先输出根节点， 然后递归。 if(s[u].l != 0) {putchar('(');print(s[u].l);putchar(',');print(s[u].r);putchar(')');}
}int main()
{int T;scanf("%d", &T);for(kase = 1; kase <= T; kase++){g.clear();cin >> str;k = cnt = 0;print(solve()); //两个函数一起写 puts("");}return 0;
}