首页 > 代码库 > UVa12219 Common Subexpression Elimination (表达式树)

UVa12219 Common Subexpression Elimination (表达式树)

2024-08-14 12:16:46   208人阅读

链接：http://vjudge.net/problem/UVA-12219

分析：用一个map把子树映射成编号1,2,...。这样一来，一棵子树就可以用三元组（s,left,right）表示（s表示根结点字符串，left，right表示左右子结点编号）。这样，每次判断一棵子树是否出现过只需要在map中查找，总时间复杂度为O（nlogn）。

 

 1 #include <cstdio> 2 #include <string> 3 #include <map> 4 using namespace std; 5  6 const int maxn = 5e4 + 5; 7  8 int kase, cnt, done[maxn]; 9 char expr[maxn * 6], *p;10 11 struct Node {12     string s;13     int hash, left, right;14     bool operator < (const Node& rhs) const {15         if (hash != rhs.hash) return hash < rhs.hash;16         if (left != rhs.left) return left < rhs.left;17         return right < rhs.right;18     }19 } node[maxn];20 21 map<Node, int> dict;22 23 int parse() {24     int id = ++cnt;25     Node& u = node[id];26     u.left = u.right = -1;27     u.s = "";28     u.hash = 0;29     while (isalpha(*p)) {30         u.hash = u.hash * 27 + *p - ‘a‘ + 1;31         u.s.push_back(*p);32         p++;33     }34     if (*p == ‘(‘) {35         p++; u.left = parse(); p++; u.right = parse(); p++;36     }37     if (dict.count(u) != 0) {38         cnt--;39         return dict[u];40     }41     return dict[u] = id;42 }43 44 void print(int u) {45     if (done[u] == kase) printf("%d", u);46     else {47         done[u] = kase;48         printf("%s", node[u].s.c_str());49         if (node[u].left != -1) {50             putchar(‘(‘);51             print(node[u].left);52             putchar(‘,‘);53             print(node[u].right);54             putchar(‘)‘);55         }56     }57 }58 59 int main() {60     int T;61     scanf("%d", &T);62     for (kase = 1; kase <= T; kase++) {63         cnt = 0; dict.clear();64         scanf("%s", &expr);65         p = expr;66         print(parse());67         putchar(‘\n‘);68     }69     return 0;70 }

 

UVa12219 Common Subexpression Elimination (表达式树)


联系
我们