解题的第一步显然是构建表达式树，因为题目保证运算符均为二元的，所以该表达式树是一颗二叉树，本题要求建树的时间复杂度为O(n)。故使用pos变量作为指针在字符串上移动，根据’('符号进行递归建树。
在对于重复子树的判断上，建议使用unordered_map，unordered_map本质上是一个哈希表，在没有顺序要求的情况下，仅进行简单的查找操作最高可达到O(1)的时间复杂度，这取决于哈希的优秀性。
用编码的方式给每个子树赋予一个唯一的特征，再进行哈希。
最后递归打印即可。
key=key*(long long)1e10+node[cur].lson*(long long)1e5+node[cur].rson;代码如下：
#include<bits/stdc++.h> using namespace std; struct Node{ string data; int lson,rson; Node(string d="",int l=0,int r=0):data(d),lson(l),rson(r){}; }node[50005]; string s; int vis[50005]; int cnt; int build(int&pos,unordered_map<long long,int>& m) { int start=pos; int cur=cnt++; long long key=0; while(pos<s.length()&&isalpha(s[pos])){ key=key*27+s[pos]-'a'+1; pos++; } node[cur]=Node(s.substr(start,pos-start)); if(pos<s.length()&&s[pos]=='('){ node[cur].lson=build(++pos,m); node[cur].rson=build(++pos,m); pos++; } key=key*(long long)1e10+node[cur].lson*(long long)1e5+node[cur].rson; if(!m.count(key)){ m[key]=cur; } else cnt--; return m[key]; } void print_ans(int root,int sign) { if(vis[root]==sign){ printf("%d",root); return ; } vis[root]=sign; printf("%s",(node[root].data).c_str()); if(node[root].lson==0)return ; printf("("); print_ans(node[root].lson,sign); printf(","); print_ans(node[root].rson,sign); printf(")"); return ; } int main(void) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int t; cin>>t; while(t--) { cin>>s; int pos=0; cnt=1; unordered_map<long long,int> m; build(pos,m); print_ans(1,t); printf("\n"); } // fclose(stdout); // fclose(stdin); }附上unordered_map和map在各种操作上的时间复杂度的对比。
