大體題意：

給你一個(gè)字符串按照二叉樹的形式，用消除公共表達(dá)式的方法可以減少表達(dá)式樹上的的結(jié)點(diǎn)，輸出最少的結(jié)點(diǎn)的圖，詳細(xì)見原題。

思路：

寫的比較亂，感覺時(shí)間還行吧。借鑒一下吧。

先寫dfs 建樹，在寫個(gè)dfs2 從葉子結(jié)點(diǎn)向上更新父結(jié)點(diǎn) 重新標(biāo)號，使得相同類的結(jié)點(diǎn)歸為一類。

在寫個(gè)dfs3，重新從根節(jié)點(diǎn)標(biāo)號，變得有序。

最后PRint 函數(shù)  要么輸出數(shù)字 要么輸出字符串 討論一下即可。

#include <cstdio>#include <cstring>#include <algorithm>#include <unordered_map>#include <string>#include <map>#include <iostream>#define mr make_pair#define fi first#define se secondusing namespace std;const int maxn = 50000 + 7;char s[maxn*20];struct Node{    string t;    int fii,see;    Node(string t= "", int fii = -1,int see = -1):t(t),fii(fii),see(see){}    bool Operator < (const Node& rhs) const {        return fii < rhs.fii || (fii==rhs.fii && see < rhs.see) || (fii==rhs.fii && see == rhs.see && t < rhs.t);    }    bool operator == (const Node& rhs) const {        return t == rhs.t && fii == rhs.fii && see == rhs.see;    }};unordered_map<int,bool> mp;map< Node ,int >Hash;string node[maxn];int lch[maxn], rch[maxn],hash_id[maxn],tab[maxn],ord[maxn];int id, pos,cur,len;string t;void dfs(int c){    if (cur >= len) return;    t = s[cur];    while(cur + 1 < len && s[cur+1] != '(' && s[cur+1] != ')' && s[cur+1] != ','){        ++cur;        t+= s[cur];    }    node[c] = t;    cur++;    char ch = s[cur];    if (ch == ',') return;    if (ch == ')' || cur >= len ) {        ++cur;        return ;    }    if (cur < len && ch == '('){        id++;        lch[c] = id;        ++cur;        dfs(id);    }    ch = s[cur];    if (cur < len && ch == ','){        id++;        rch[c] = id;        ++cur;        dfs(id);    }    ch = s[cur];    if (cur < len && ch == ')'){        ++cur;        return;    }}void print(int c){    if (c == -1) return ;    if (mp.count(tab[c])){        printf("%d",tab[c]);        return;    }    printf("%s",node[c].c_str());    mp[tab[c]] = 1;    bool ok = !(lch[c] == -1 && rch[c] == -1);    bool ok2 = !(lch[c] == -1 || rch[c] == -1);    if (ok)printf("(");    print(lch[c]);    if (ok2)printf(",");    print(rch[c]);    if (ok)printf(")");}int fii,see;string tmp;void dfs2(int cur){    if (cur == -1) return;    dfs2(lch[cur]);    dfs2(rch[cur]);    if (lch[cur] == -1 && rch[cur] == -1){        Node u = Node(node[cur],-1,-1);        if (!Hash.count(u) ){            hash_id[cur] = id++;            Hash[u] = id-1;        }        else {            hash_id[cur] = Hash[u];        }        return;    }    if (lch[cur] == -1) fii = -1;    else fii = hash_id[lch[cur]];    if (rch[cur] == -1) see = -1;    else see = hash_id[rch[cur]];    tmp = node[cur];    Node u = Node(tmp,fii,see);    if (!Hash.count(u) ){        hash_id[cur] = id++;        Hash[u] = id-1;    }    else {        hash_id[cur] = Hash[u];    }}void dfs3(int c){    if (c == -1) return;    if (ord[hash_id[c] ] == -1){        tab[c] = id++;        ord[hash_id[c]] = id-1;    }    else {        tab[c] = ord[hash_id[c]];    }//    printf("^^ %d/n",tab[c]);    dfs3(lch[c]);    dfs3(rch[c]);}int main(){    int T;    scanf("%d%*c",&T);    while(T--){        memset(lch,-1,sizeof lch);        memset(rch,-1,sizeof rch);        memset(ord,-1,sizeof ord);        len = 0;        scanf("%s",s);        len = strlen(s);        id = pos = cur = 0;        mp.clear();        Hash.clear();        dfs(0);        id = 1;        dfs2(0);        id = 1;        dfs3(0);        print(0);        puts("");//        printf("&&& %d/n",mp[3]);    }    return 0;}/**3this(is(a,tiny),tree)a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))z(zz(zzzz(zz,z),zzzz(zz,z)),zzzz(zz(zzzz(zz,z),zzzz(zz,z)),z))1a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))**/