UOA1001: Binary Tree Intersection And Union

何故か知らないけど最近解いてる人が多いので、便乗してみました。二分木の和と積を求める問題。

人によってコード長の差が激しいのを見て、できるだけ簡単な実装を考えてから書いてみました。十分縮まったので満足です。

与えられた木を別個に作らず、1つ目の木に2つ目の木を上書きするのがポイント。あるノードを訪れるたびにそのノードのカウンタを増やしていくと、そのノードが和・積に含まれるかどうかはカウンタを見るだけで判断できる。

#include <iostream>

using namespace std;

const int nil=-1;
const int N=256;

struct node{
  int c,l,r;
  node(){c=0;l=r=nil;}
} v[N];

int cnt;

void parse(string& s,int &n,int r){
  v[r].c++; n++;
  if(s[n]!=','){
    if(v[r].l==nil) v[r].l=++cnt;
    parse(s,n,v[r].l);
  }
  n++;
  if(s[n]!=')'){
    if(v[r].r==nil) v[r].r=++cnt;
    parse(s,n,v[r].r);
  }
  n++;
}

string str(int r,int n){
  if(v[r].c<n) return "";
  return "("+(v[r].l!=nil?str(v[r].l,n):"")+","+(v[r].r!=nil?str(v[r].r,n):"")+")";
}

main(){
  char op;
  string a,b;
  while(cin >> op >> a >> b){
    for(int i=0;i<N;++i) v[i]=node();
    cnt=0;
    int n;
    parse(a,n=0,0); parse(b,n=0,0);
    cout << str(0,op=='i' ? 2 : 1) << endl;
  }
}

そういえば、UOAのSubmit数がついに10,000に達したようで。おめでとうございます。