AOJ1001 Binary Tree Intersection And Union

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

解法

以下がBNF。

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

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

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

次に２つの二分木の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;
}