【uva 12219】Common Subexpression Elimination（图论--树+自定义比较器+映射+递归）

阅读原文时间：2023年07月10日阅读：1

题意：如题，用表达式树来表示一个表达式，且消除公共的部分，即用编号表示。编号 K 定义为表达式第 K 个出现的字符串。

解法：先构造表达式树，给每棵子树用(string,left_son,right_son)-->(哈希值,…,…)编号。由于最多出现4个小写字母，所以可以用27进制数表示，同时也要利用好映射map的count(),和对应的dict[]的编号。

再递归输出表达式，利用编号的定义，看输出编号或字符串。

注意——这里的自定义比较器用的是“显式定义”，若是2个键值排序，还可以用专门把2个类型捆绑到一起的pair，它默认先比较第一关键字 .first，再是第二关键字 .second——

定义排序：typedef pair pii[]; 再加优先队列或 cmp函数
赋值： pii[]=make_pair(x,y);

P.S.我是参考着紫书做着Rujia Liu的代码打着，但如名，我这konjac蒟蒻改成了一个我自己能够记得的代码~所以，这题主要是提高代码能力，hh~

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 const int N=50010;
8
9 char ss[7*N];
10 struct node
11 {
12 char s[6];
13 int hash,lc,rc,l;
14 bool operator < (const node& x) const 15 { 16 if (hash!=x.hash) return hash dict;
22 bool v[N];
23 int len,p;
24
25 int build()
26 {
27 int id=++len,t=p;
28 node& u=a[id];
29 u.hash=0,u.lc=u.rc=-1,u.l=0;
30 while (ss[p]>='a'&&ss[p]<='z')
31 {
32 u.hash=27*u.hash+ss[p]-'a'+1;
33 u.s[p-t+1]=ss[p];
34 p++;
35 }
36 u.l=p-t;
37 if (ss[p]=='(')
38 {
39 p++,u.lc=build();
40 p++,u.rc=build();
41 p++;
42 }
43 if (dict.count(u)) {len--;return dict[u];}
44 dict[u]=id;
45 return dict[u];
46 }
47
48 void print(int x)
49 {
50 if (v[x]) {printf("%d",x);return;}
51 v[x]=1;
52 for (int i=1;i<=a[x].l;i++) printf("%c",a[x].s[i]);
53 if (a[x].lc!=-1)
54 {
55 printf("(");
56 print(a[x].lc);
57 printf(",");
58 print(a[x].rc);
59 printf(")");
60 }
61 }
62
63 int main()
64 {
65 int T;
66 scanf("%d",&T);
67 while (T--)
68 {
69 len=0,p=1;
70 dict.clear();
71 scanf("%s",ss+1);
72 memset(v,0,sizeof(v));
73 print(build());
74 printf("\n");
75 }
76 return 0;
77 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章