AOJ1001 Binary Tree Intersection And Union


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

AOJ1001 Binary Tree Intersection And Union

サイト

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001

解説

タイトルの通り入力の木は二分木である。

入力のBNFを書いてみると実装がしやすい。以下がBNFである。

< binary > := ( < binary > , < binary > ) | ε

εは空文字列を意味し、木構造の葉(終端)である。

このBNFによって記述された2つの二分木をIntersectまたはUnionする。先ずは上のBNFの構文解析をして、1つの二分木のみの解析を考えてみよう。

カンマの位置を特定することが必要なのでその方法を考える。先頭の'('を読み飛ばしてから、'('が来たらカウントを1増やし、')'が来たらカウントを1減らす操作をする。カウントが0になったときにカンマの位置が発見できるので前後のが分割可能。分割のコードは以下。

void divStr(const string& s, string& s1, string& s2) {
  int n = s.size();
  int retain = 0;
  for(int pos=1; ; pos++) {
    if(s[pos] == '(') retain++;
    if(s[pos] == ')') retain--;
    else if(retain == 0) {
      s1 = s.substr(1, pos-1);
      s2 = s.substr(pos+1, n-pos-2);
      return;
    }
  }
}

分割が完了したら、(A,B)のAとB両方で再帰が起こる。BNFの通り、再帰の終了条件を空文字列とすれば二分木の構文解析が終了する。

次に、2つの二分木のIntersectとUnionについて考えよう。2つの木を重ねあわせたとき「片方が終端に達していても、もう片方が非終端である場合」がある。出力すべき文字列の形式で言い換えると、「片方が空文字列であっても、もう片方がまだ文字列をもつ場合がある」と言える。つまり2つの木のどちらかが終端に達した時点で空文字列を返せばIntersectであり、余った文字列を返せばUnionとなる。

string make(string op, string s, string t) {
  if(s == "" || t == "") {
    if(op == "i") return "";
    else return s == "" ? t : s;
  }
  
  string sL, sR, tL, tR;
  divStr(s, sL, sR);
  divStr(t, tL, tR);
  
  return '(' + make(op, sL, tL) + ',' + make(op, sR, tR) + ')';
}