网友投稿 860 2022-11-07
UVA 12219 Common Subexpression Elimination——map
#include #include #include #include #include using namespace std;const int MAXN = 1e6;struct Node { char s[10]; int cnt, num, lch, rch; bool operator < (const Node &temp) const { if (num != temp.num) return num < temp.num; if (lch != temp.lch) return lch < temp.lch; return rch < temp.rch; }};struct Tree { Node node[MAXN]; int tot, pos; char str[MAXN]; map m; bool vis[MAXN]; void init() { scanf("%s", str + 1); tot = 0, pos = 1; m.clear(); } int build() { int root = ++tot; node[root]-t = node[root].num = node[root].lch = node[root].rch = 0; vis[root] = false; while ('a' <= str[pos] && str[pos] <= 'z') { node[root].s[++node[root]-t] = str[pos]; node[root].num = node[root].num * 30 + str[pos] - 'a' + 1; ++pos; } if (str[pos] == '(') { ++pos; node[root].lch = build(); ++pos; node[root].rch = build(); ++pos; } int x = m[node[root]]; if (x) { --tot; return x; } else return m[node[root]] = root; } void output(int root) { if (vis[root]) printf("%d", root); else { vis[root] = true; for (int i = 1; i <= node[root]-t; i++) printf("%c", node[root].s[i]); if (node[root].lch) { printf("("); output(node[root].lch); printf(","); output(node[root].rch); printf(")"); } } }}tree;int main() { int T; scanf("%d", &T); while (T--) { tree.init(); tree.build(); tree.output(1); printf("\n"); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~