読者です 読者をやめる 読者になる 読者になる

AOJ1001 Binary Tree Intersection And Union

概要
二分木が入力されるので Intersect または Union して出力せよ。

解法

以下がBNF

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

一つの親ノードと2つの子ノードの3つのノードについての処理を考える。つまりカンマの位置を特定することが必要なのでその方法を考える。
先頭の'('を読み飛ばしてから、'('が来たらカウントを1増やし、')'が来たらカウントを1減らす操作をする。カウントが0になったときにカンマの位置が発見できるので前後の文字列が分割可能。

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

次に2つの二分木のIntersectとUnionについて考える。2つの木を重ねあわせたとき「片方が終端に達していても、もう片方が非終端である場合」がある。ここで初めて Intersection または Union の処理考えるればよい。何故なら2つの木のどちらかが終端に達した時点で空文字列を返せばIntersectであり、余った文字列を返せばUnionとなるからである。

#include <bits/stdc++.h>
 
using namespace std;
 
// rep
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define rep(i,n) REP(i,0,n)
 
void division(string const &raw, string &left, string &right) {
   
  int const N = raw.size();
  int retain = 0;
  REP(pos, 1, N) {
    if(raw[pos] == '(') retain++;
    else if(raw[pos] == ')') retain--;
    else if(retain == 0) {
      //assert(raw[pos] == ',');
      left  = raw.substr(1, pos-1);
      right = raw.substr(pos+1, N-pos-2);
      break;
    }
  }
   
}
 
string solve(char op, string const &s, string const &t) {
  if(s.empty() || t.empty()) {
    if(op == 'i') return min(s, t);
    else return max(s, t);
  }
   
  string sL, sR, tL, tR;
  division(s, sL, sR);
  division(t, tL, tR);
   
  return '(' + solve(op, sL, tL) + ',' + solve(op, sR, tR) + ')';
}
 
int main() {
   
  char op; string s, t;
  while(cin >> op >> s >> t) {
    cout << solve(op, s, t) << endl;
  }
   
  return 0;
}