Problem 1001 : Binary Tree Intersection And Union

Binary Tree Intersection And Union
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1001

• 問題概要

二分木のユニオンとインターセクトをとって、あたえられた形式で出力せよ。

• 解法

構文解析。
ただし、2個木をつくるのではなく、1個きを作り、2個目は上書きする。上書きされたところは記憶する。

ユニオンならすべての要素を、インターセクトなら上書きされた要素を出力する。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class Node{
public:
  int r, l, cnt;
  Node(){
    r = l = -1;
    cnt = 0;
  }
};
int ID;
Node n[300];

string strUNI(int id){
  string s = "(";
  if(n[id].l != -1){
    s += strUNI(n[id].l);
  }
  s += ",";
  if(n[id].r != -1){
    s += strUNI(n[id].r);
  }
  s += ")";
  return s;
}
string strIN(int id){
  string s = "(";
  if(n[id].l != -1 && n[n[id].l].cnt == 2){
    s += strIN(n[id].l);
  }
  s += ",";
  if(n[id].r != -1 && n[n[id].r].cnt == 2){
    s += strIN(n[id].r);
  }
  s += ")";
  return s;
}

void parse(string &s, int &pos, int &now){
  pos++;
  n[now].cnt++;
  if( s[pos] != ',' ){
    if(n[now].l == -1)n[now].l = ++ID;
    parse(s, pos, n[now].l); 
  }
  
  pos++;
  
  if( s[pos] != ')'){
    if(n[now].r == -1)n[now].r = ++ID;
    parse(s, pos, n[now].r);
  }
  pos++;
}

main(){
  char c;
  string first, second;

  while(cin >> c >> first >> second){
    rep(i, 300)n[i] = Node();
    int now = 0, pos = 0;
    ID = 0;
    parse(first, pos, now);
    pos = 0;
    now = 0;
    ID++;
    parse(second, pos, now);
    if(c == 'u')cout << strUNI(0) << endl;
    else cout << strIN(0)<<endl;
  }
}