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

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

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

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

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

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

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

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<map>

 5 #include<iostream>

 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<x.hash;

17       if (lc!=x.lc) return lc<x.lc;

18       return rc<x.rc;

19     }

20 }a[N];

21 map<node,int> 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 }

巴特西

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

最新文章

热门文章