admin管理员组文章数量:1596259
草草刷了一下暴力,开始转战图论了。 这是第一道例题,讲解了一种实用而神奇的树状结构:表达式树 。虽然打比赛从来没见过,但是我练这个本来也不只是为了比赛 , 重要的是ACM本身带给我的乐趣 。
该题的一个很巧妙的做法是将每一个结点用一个三元组来表示,然后映射到map中以去重 。 其中三元组中有一个string , 我们可以用hash来处理这个string 。
因为string最大长度为4, 所以我们可以这样处理 : int hash = 0; hash = hash * 27 + s[i] - '0' + 1;
将hash每次乘以27 是因为字符串只有小写字母,这样做可以完美的去重 ,保证了哈希表不会重复 。
细节参见代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 60000;
int T,n,m,kase,cnt,done[maxn];
char s[maxn*5],*p;
struct node {
string s;
int hash,l,r;
bool operator < (const node& u) const {
if(hash != u.hash) return hash < u.hash;
if(l != u.l) return l < u.l;
return r < u.r;
}
}nodes[maxn];
map<node,int> dict;
int parse() {
int id = cnt++;
node& u = nodes[id];
u.l = u.r = -1 ;
u.s = "";
u.hash = 0;
while(isalpha(*p)) {
u.hash = u.hash * 27 + *p - 'a' + 1;
u.s.push_back(*p);
++p;
}
if(*p == '(') {
p++; u.l = parse(); p++; u.r = 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+1);
else {
done[v] = kase;
printf("%s",nodes[v].s.c_str());
if(nodes[v].l != -1) {
printf("(");
print(nodes[v].l); //递归求得结点值并打印 。
printf(",");
print(nodes[v].r);
printf(")");
}
}
}
int main() {
scanf("%d",&T);
for(kase = 1; kase <= T; ++kase) {
dict.clear();
cnt = 0;
scanf("%s",s);
p = s;
print(parse());
printf("\n");
}
return 0;
}
本文标签: 表达式commonEliminationSubexpression
版权声明:本文标题:12219 - Common Subexpression Elimination(表达式树) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728257074a1151144.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论