AOJ1152 部陪博士，あるいは，われわれはいかにして左右非対称になったか

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1152&lang=jp）

与えられた二分木を、条件を満たすように左右の子を入れ替えて変形する。

制約条件

テストケースの個数≦100
ノードの個数≦127

方針

二分木をあらわすクラスを作って、ガリガリ実装。
左右類似度や、部分木のリストを求める計算はメモ化してみたけど、不要かも。

ソースコード

struct T{
	T *l, *r;
	int h;
	T(){l=r=NULL;h=1;}
	bool operator==(const T &o)const{
		if(h==1||o.h==1)return h==o.h;
		return *l==*(o.l)&&*r==*(o.r);
	}
	bool operator<(const T &o)const{
		if(h!=o.h)return h<o.h;
		if(h==1)return 0;
		if(!(*l==*(o.l)))return *l<*(o.l);
		return *r<*(o.r);
	}
};
T *normalize(T *t){
	T *res=new T();
	if(t->h==1)return res;
	T *l=normalize(t->l), *r=normalize(t->r);
	if(*l<*r)res->r=l, res->l=r;
	else res->l=l, res->r=r;
	res->h=max(l->h,r->h)+1;
	return res;
}
map<T,double> dp;
map<T,set<T> > dp2;
set<T> subsets(T *t){
	if(dp2.count(*t))return dp2[*t];
	if(t->h==1){
		set<T> res;
		res.insert(*t);
		return dp2[*t]=res;
	}
	set<T> res,l=subsets(t->l),r=subsets(t->r);
	res.insert(*t);
	res.insert(all(l));
	res.insert(all(r));
	return dp2[*t]=res;
}
double calc(T *t){
	if(dp.count(*t))return dp[*t];
	if(t->h==1)return dp[*t]=0;
	set<T> sl=subsets(normalize(t->l)), sr=subsets(normalize(t->r)), s=sl;
	s.insert(all(sr));
	int cnt=0;
	fr(i,s)if(sl.count(*i)&&sr.count(*i))cnt++;
	return dp[*t]=cnt*1.0/s.size();
}
string out(T* t){
	if(t->l==NULL)return "x";
	return "("+out(t->l)+" "+out(t->r)+")";
}
int cmp(T *a,T *b){
	double x=calc(normalize(a)), y=calc(normalize(b));
	if(a->h==1&&b->h==1)return 0;
	if(abs(x-y)>EPS)return x<y?-1:1;
	T *a1,*a2,*b1,*b2;
	if(cmp(a->l,a->r)<0)a1=a->l, a2=a->r;
	else a1=a->r, a2=a->l;
	if(cmp(b->l,b->r)<0)b1=b->l, b2=b->r;
	else b1=b->r, b2=b->l;
	int res=cmp(a1,b1);
	if(res)return res;
	return cmp(a2,b2);
}
T* form(T *t,bool left,bool root){
	T *res=new T();
	if(t->h==1)return res;
	if((cmp(t->l,t->r)<0)^!left)res->l=form(t->l,1,0), res->r=form(t->r,0,0);
	else res->l=form(t->r,1,0), res->r=form(t->l,0,0);
	res->h=max(t->l->h,t->r->h)+1;
	return res;
}
string in;
T* rec(int l,int r){
	if(r-1==l)return new T();
	int i,d=0;
	for(i=r-1;i>=l;i--){
		if(in[i]==')')d++;
		if(in[i]=='(')d--;
		if(d==0)break;
	}
	if(i==l)return rec(l+1,r-1);
	T *res=new T();
	res->l=rec(l,i-1);
	res->r=rec(i,r);
	res->h=max(res->l->h,res->r->h)+1;
	return res;
}

int main(){
	while(getline(cin,in),in!="0"){
		T *t=rec(0,in.size());
		cout<<out(form(t,1,1))<<endl;
	}
	return 0;
}