るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

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;
  }
}