#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

enum Stronger{NOCALC,LEFT,EQUAL,RIGHT};//非対称性の強さ.交換するときは4から引いた値になる
struct Tree{
	Tree *left,*right;
	set<string> structure;//これ以下に出来る全ての構造
	long double LR_similarity;//左右類似度
	Stronger stronger; //非対称性の強さ
	Tree(){left=0;right=0;stronger=NOCALC;LR_similarity=0;}
	~Tree(){
		if(left)delete left;
		if(right)delete right;
	}
};

//文字列から木を生成する
Tree* fromString(const string &in){
	Tree *node=new Tree();
	if(in=="x")return node;
	int depth=0,mid;
	for(int i=1;i<(int)in.size()-1;i++){
		if(in[i]=='(')depth++;else if(in[i]==')')depth--;
		if(depth==0&&in[i]==' '){
			mid=i;break;
		}
	}
	node->left=fromString(in.substr(1,mid-1));
	node->right=fromString(in.substr(mid+1,in.size()-mid-2));

	return node;
}

//木からそれを表わす文字列を生成する.整形する場合同じ形だったら一意なものになるようにする.
string toString(Tree *node,bool normalize=false){
	string res="";
	if((!node->left)&&(!node->right))return "x";
	string l=toString(node->left,normalize),r=toString(node->right,normalize);
	if(normalize&&l.size()<r.size())swap(l,r);
	res="("+l+" "+r+")";
	return res;
}

//木からそれ以下に含まれる全ての構造を取得する．
void getStructure(Tree *node){
	if(!node->structure.empty())return;
	if(node->left){
		getStructure(node->left);
		FOR(it,node->left->structure){
			node->structure.insert(*it);
		}
	}
	if(node->right){
		getStructure(node->right);
		FOR(it,node->right->structure){
			node->structure.insert(*it);
		}
	}

	node->structure.insert(toString(node,true));
}
//ノード及び小ノードの左右類似度を計算する．
void calcLR_similarity(Tree *node){
	if(!node->left){
		node->LR_similarity=0;return;
	}else{
		calcLR_similarity(node->left);
		calcLR_similarity(node->right);
		set<string> all;
		set<string> common;
		FOR(it,node->left->structure)all.insert(*it);
		FOR(it,node->right->structure)all.insert(*it);
		FOR(it,node->left->structure){
			if(node->right->structure.find(*it)!=node->right->structure.end()){
				common.insert(*it);
			}
		}
		node->LR_similarity=static_cast<long double>(common.size())/static_cast<long double>(all.size());
	}
}
//強い方と弱い方を取得する
void getStrongerAndWeaker(Tree *node,Tree **weaker,Tree **stronger){
	if(node->stronger==LEFT){
		*stronger=node->left;
		*weaker=node->right;
	}else{
		*stronger=node->right;
		*weaker=node->left;
	}
}
//非対称性の強さの比較
Stronger compare(Tree *left,Tree *right){
	if(abs(left->LR_similarity-right->LR_similarity)>1e-9){
		if(left->LR_similarity<right->LR_similarity){
			return LEFT;
		}else{
			return RIGHT;
		}
	}

	if((!left->left)&&(!right->right))return EQUAL;

	Tree *rStronger=0,*rWeaker=0,*lStronger=0,*lWeaker=0;
	getStrongerAndWeaker(left,&lWeaker,&lStronger);
	getStrongerAndWeaker(right,&rWeaker,&rStronger);
	if(compare(lStronger,rStronger)!=EQUAL){
		return compare(lStronger,rStronger);
	}

	if(compare(lWeaker,rWeaker)!=EQUAL){
		return compare(lWeaker,rWeaker);
	}
	return EQUAL;
}
//非対称性の強さを比較する．
void calcStronger(Tree *node){
	if(!node->left)return;
	if(node->left)calcStronger(node->left);
	if(node->right)calcStronger(node->right);
	node->stronger=compare(node->left,node->right);
}

//非対称性が強くなるようにする
void solve(Tree *node,int root=0){//root=0ならルート．1なら右 -1なら左
	if(!node->left)return;
	if(node->stronger==RIGHT&&root<=0){
		swap(node->left,node->right);
		node->stronger=static_cast<Stronger>(4-static_cast<int>(node->stronger));
	}
	if(node->stronger==LEFT&&root==1){
		swap(node->left,node->right);
		node->stronger=static_cast<Stronger>(4-static_cast<int>(node->stronger));
	}
	solve(node->left,-1);
	solve(node->right,1);
}


//入力処理
bool input(Tree **root){
	string in;
	getline(cin,in);
	if(in=="0")return false;
	*root=fromString(in);
	return true;
}

int main() {
	Tree *root;
	while(input(&root)){
		getStructure(root);
		calcLR_similarity(root);

		calcStronger(root);
		solve(root);

		cout<<toString(root)<<endl;
		if(root)delete root;//メモリの解放
	}
	return 0;
}

Measured memory_bytes: 1348