原題鏈接：點(diǎn)擊此處

覺得這題好難呀！方法在紫書上，十一節(jié)公共表達(dá)式消除那小節(jié)（沒帶書回來，具體頁數(shù)不清楚啦~）

?

這題樹中的結(jié)點(diǎn)對應(yīng)的子樹都是二叉樹，不存在只有一個兒子的情況。輸入的字符串中也只有兩種情況，結(jié)點(diǎn)名字后面緊跟一個左括號的，和不跟括號的。

?

因此很容易判斷一個結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)：只要在原字符串中看他后面有沒有緊跟著左括號就行了。如果有，立刻遞歸建樹作為左子樹。因?yàn)橛凶笞訕渚鸵欢ㄓ杏易訕?#xff0c;所以左子樹建完后就可以從字符串中左子樹結(jié)束的位置開始建右子樹了。因此不需要從左到右掃描尋找逗號來分割左右子樹。

另外字符串的對比是緩慢的。鑒于這道題最多只有四個小寫字母，也就是最多26*4種情況，我們完全可以用整數(shù)來代替字符串。一種比較簡單的做法是把字符串看成一個四位的27進(jìn)制數(shù)，并拋棄0，因?yàn)?和0000相等。

代碼如下：

#include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<iostream> #include<map> #include<stdio.h> using namespace std;void decode(int a) {vector<char> result;while(a) { result.push_back(a%27+'a'-1); a/=27; } //%27+1for(int i = result.size() - 1; i >= 0; i --) {cout<<result[i];} }struct Tree {int rcode, lch, rch; //code of root. treeid of left and right sub-tree. Tree(){}Tree(int a, int b, int c):rcode(a), lch(b), rch(c) { }bool operator < (const Tree& rhs) const {if(rcode == rhs.rcode){if(lch == rhs.lch) return rch < rhs.rch;return lch < rhs.lch;}return rcode < rhs.rcode;} };//Global Variables. Reset upon Each Case! const int maxn = 50000+5; int T, treecnt, vis[maxn], ans[maxn], cnt; char str[5*(maxn+10000)], *p; Tree trees[maxn]; map<Tree, int> tree_map; /////int getTreeID(Tree& t) {if(tree_map.count(t)) return tree_map[t];else{Tree& v = trees[treecnt];v = t;return tree_map[t] = treecnt++;} }int parse() {int lch = -1, rch = -1;int name = 0;while(isalpha(*p)) {name = name*27 + (*p-'a'+1);p ++;}if(*p == '(') {p++;lch = parse();p ++;rch = parse();p ++;}Tree tmp = Tree(name, lch, rch);return getTreeID(tmp); }void print_ans(int id) {if(ans[id] != -1) cout<<ans[id];else {ans[id] = ++cnt;decode(trees[id].rcode);if(trees[id].lch != -1){cout<<"(";print_ans(trees[id].lch);cout<<",";print_ans(trees[id].rch);cout<<")";}} }int main() {memset(vis, -1, sizeof(vis));cin>>T;while(T--){treecnt = cnt = 0;tree_map.clear();scanf("%s", str);p = str;memset(ans, -1, sizeof(ans));print_ans(parse());printf("\n");}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/gdvxfgv/p/5721887.html

總結(jié)

以上是生活随笔為你收集整理的UVA 12219-Common Subexpression Elimination的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。