UVA 12219 Common Subexpression Elimination （dfs瞎搞）

大体题意：

给你一个字符串按照二叉树的形式，用消除公共表达式的方法可以减少表达式树上的的结点，输出最少的结点的图，详细见原题。

思路：

写的比较乱，感觉时间还行吧。借鉴一下吧。

先写dfs 建树，在写个dfs2 从叶子结点向上更新父结点 重新标号，使得相同类的结点归为一类。

在写个dfs3，重新从根节点标号，变得有序。

最后PRint 函数  要么输出数字 要么输出字符串 讨论一下即可。

#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))**/