题目链接
使用 \((hash,left,right)\) 表示一个子树,存入 \(map\) 中,就可以判断一个子树是否出现过
剩下的就是字符串处理的部分,利用字符串指针递归处理,很巧妙
\(s.c_str()\) 返回指向字符串 \(s\) 的指针
\(vis[i] == kase\) 可以避免 \(memset(vis, 0, sizeof(vis))\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 60000;
int T, kase, cnt;
char expr[maxn * 5], *p;
int done[maxn];
struct Node{
string s;
int hash, left, right;
bool operator < (const Node& x) const{
if(hash != x.hash) return hash < x.hash;
if(left != x.left) return left < x.left;
return right < x.right;
}
}node[maxn];
map<Node, int> mp;
int parse(){
int id = ++cnt;
Node& u = node[id];
u.left = u.right = -1;
u.s = "";
u.hash = 0;
while(isalpha(*p)){
u.hash = u.hash * 27 + *p - 'a' + 1;
u.s.push_back(*p);
p++;
}
if(*p == '('){
p++; u.left = parse(); p++; u.right = parse(); p++;
}
if(mp.count(u) != 0){
cnt--;
return mp[u];
}
return mp[u] = id;
}
void print(int v){
if(done[v] == kase){
printf("%d", v);
} else{
done[v] = kase;
printf("%s", node[v].s.c_str());
if(node[v].left != -1){
putchar('(');
print(node[v].left);
putchar(',');
print(node[v].right);
putchar(')');
}
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
scanf("%d", &T);
for(kase = 1 ; kase <= T ; ++kase){
scanf("%s", expr);
p = expr;
cnt = 0;
mp.clear();
print(parse());
putchar('\n');
}
return 0;
}