AOJ 1001 Binary Tree Intersection And Union
[問題文]
AIZU ONLINE JUDGE
[解法]
構文解析
慣れていないのでかなり時間がかかった。
こんなやつの解析
<exp>::= "(" , <exp> , <exp> , ")" | ""
結構楽しい。
struct E{ int l,r,id; int over; E(){ l = r = -1 ,id = 0; over = 0;} }; int now; int p = 0; E memo[400]; void parse(string s,int &id){ memo[id].over++; p++; if(s[p] != ','){// "(" if(memo[id].l == -1) memo[id].l = ++now; parse(s,memo[id].l); } p++; // "," if(s[p] != ')'){ // ")" if(memo[id].r == -1) memo[id].r = ++now; parse(s,memo[id].r); } p++; } string unite(int n){ string ret = "("; if(memo[n].l != -1) ret += unite(memo[n].l); ret += ","; if(memo[n].r != -1) ret += unite(memo[n].r); ret += ")"; return ret; } string intersect(int n){ string ret = "("; if(memo[n].over != 2) return ""; if(memo[n].l != -1) ret += intersect(memo[n].l); ret += ","; if(memo[n].r != -1) ret += intersect(memo[n].r); ret += ")"; return ret; } int main(){ char ope;string a,b; while(cin>>ope>>a>>b){ now = 0; rep(i,400) memo[i] = E(); p = 0; int id = 0; parse(a,id); now++; p = 0; id = 0; parse(b,id); if(ope == 'i') cout<<intersect(0)<<endl; else cout<<unite(0)<<endl; } }