题目链接： 点这里

题意： 可以参考紫书P354 - P355。

解题方法：第一步是构造表达式树，构造时可以利用一个map来记录出现的子树，并为之编号。例如，用(a,0,0)可以表示一个叶子a，用(b,3,6)表示根的名字是b，子树的编号分别是3,6的树。这样既可方便地得到最简表达式。本题总的时间复杂度为O(N*logN)。具体细节在代码中也有详细描述。

代码如下:

//
//Created by BLUEBUFF 2016/1/29
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 60010;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // NTT
//const double PI = acos(-1);
//head
int T, ks, cnt;
int vis[maxn];
char expr[maxn * 5], *p;
struct node{
    string s;
    int val, left, right;
    node(){}
    node(string s, int val, int left, int right) : s(s), val(val), left(left), right(right){}
    bool operator <(const node &rhs) const{ //重载小于运算符
        if(val != rhs.val) return val < rhs.val;
        if(left != rhs.left) return left < rhs.left;
        return right < rhs.right;
    }
}tree[maxn];
map <node, int> mp; //映射子树的编号
int work(){
    int id = cnt++; //编号从0开始
    node &u = tree[id];
    u.left = u.right = -1, u.s = "", u.val = 0;
    while(isalpha(*p)){
        u.val = u.val * 27 + *p - 'a' + 1;
        u.s.push_back(*p);
        p++;
    }
    if(*p == '('){
        p++; //先跳过'('
        u.left = work(), p++; //返回左子树编号，并跳过','
        u.right = work(), p++; //返回右子树编号，并跳过')'
    }
    if(mp.count(u)){
        cnt--;//子树出现过，个数减少1
        return mp[u];//返回这颗子树的编号
    }
    return mp[u] = id;
}
void print(int v){
    if(vis[v] == ks){
        printf("%d", v + 1);
    }
    else{
        vis[v] = ks;//不需要对vis数组初始化，只需要用这一轮特有的ks标记即可
        printf("%s", tree[v].s.c_str());
        if(tree[v].left != -1){
            putchar('(');
            print(tree[v].left);
            putchar(',');
            print(tree[v].right);
            putchar(')');
        }
    }
}
int main(){
    scanf("%d", &T);
    for(ks = 1; ks <= T; ks++){
        mp.clear();
        cnt = 0;
        scanf("%s", expr);
        p = expr;
        print(work());
        putchar('\n');
    }
    return 0;
}