//by Rujia Liu/*字符串的对比是缓慢的。鉴于这道题最多只有四个小写字母，也就是最多26*4种情况，我们完全可以用整数来代替字符串。一种比较简单的做法是把字符串看成一个四位的27进制数，并抛弃0，因为0和0000相等。*/#include<cstdio>#include<cctype>#include<string>#include<map>using namespace std;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& rhs) const {  //定义一个全序，用于map     if(hash != rhs.hash) return hash < rhs.hash;    if(left != rhs.left) return left < rhs.left;    return right < rhs.right;  }} node[maxn];map<Node,int> dict;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 == ‘(‘) { // (L,R)    p++; u.left = parse(); p++; u.right = parse(); p++;  }  if (dict.count(u) != 0) {    //先建好一个结点，然后看这个结点是不是已经有了，如果有了这个结点就不必建了     cnt--;           return dict[u];  }  return dict[u] = id;}void print(int v) {  //打印结果，kase用于标记   if(done[v] == kase)    printf("%d", v + 1);  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(‘)‘);    }  }  }int main() {  scanf("%d", &T);  for(kase = 1; kase <= T; kase++) {    dict.clear();    cnt = 0;    scanf("%s", expr);    p = expr;    print(parse());    putchar(‘\n‘);      }  return 0;}