紫书354页的题，将表达式树进行公共表达式消除，化为等价的图。因为需要判断某一个是否出现过，所以需要快速比较，采用哈希表的形式，将a~b与1~27一一对应，不采用0，因为0与0000是相同的，对于每一个树，都预先给予其一个编号，然后将其所表示的字符串化为27进制的数，然后递归建造其左右子树，如果发现其是出现过的字符串表达式，则取消其编号，返回编号，即dict[u]。建完树之后进行输出。具体细节见代码：
#include<cstdio>
#include<string>
#include<map>
using namespace std; const int maxn = ;
int T, kase, cnt;
char expr[maxn*], *p;
int done[maxn]; /// 该结点是否已输出 struct Node
{
string s;
int hash, left, right;
bool operator < (const Node& rhs) const
{
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 = -;
u.s = "";///初始化字符串
u.hash = ;
while(isalpha(*p)){
u.hash = u.hash * + *p - 'a' + ;///用27进制数来表示字符串，并取消0，1~27与a~b一一对应
u.s.push_back(*p);///节点所代表的字符串
p++;///指针后移，检查下一个字符
}
if (*p == '('){
p++;
u.left = parse();
p++;///因为递归返回时指针所指的应是')'，所以要后移到下一个
u.right = parse();
p++;
}
if (dict.count(u) != ){///如果出现过，则取消预设的编号，返回其编号
id--;
cnt--;
return dict[u];
}
return dict[u] = id;
} void print(int v)
{
if(done[v] == kase)
printf("%d", v + );
else{
done[v] = kase; /// 常见小技巧，可以避免memset(done, 0, sizeof(done))
printf("%s", node[v].s.c_str());///c_str将string转换为C语言中的字符数组的形式
if(node[v].left != -){
putchar('(');
print(node[v].left);
putchar(',');
print(node[v].right);
putchar(')');
}
}
} int main()
{
scanf("%d", &T);
for(kase = ; kase <= T; kase++){
dict.clear();
cnt = ;
scanf("%s", expr);
p = expr;
print(parse());
putchar('\n');
}
return ;
}