Language: C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

#define LEFT false
#define RIGHT true

class Tree{
public:
  Tree *l,*r;
  double similar;
  Tree():l(NULL),r(NULL),similar(0){};
  //function for arrangement symmetry
  bool cmp(bool flag){
    if ( l->similar <r->similar)return LEFT;
    else if (l->similar >r->similar)return RIGHT;
    if ( l->l == NULL && r->l == NULL)return flag;
    else if ( l->l == NULL)return LEFT;
    else if ( r->l == NULL)return RIGHT;

    if (min(l->l->similar,l->r->similar)<min(r->l->similar,r->r->similar))return LEFT;
    else if ( min(l->l->similar,l->r->similar)>min(r->l->similar,r->r->similar))return RIGHT;

    if ( max(l->l->similar,l->r->similar)<max(r->l->similar,r->r->similar))return LEFT;
    else if ( max(l->l->similar,l->r->similar)>max(r->l->similar,r->r->similar))return RIGHT;
    
    return flag;
  }  
  void sym_arrangement(bool flag){
    if ( l == NULL)return;
    if ( cmp(flag) != flag)swap(l,r);    
    l->sym_arrangement(LEFT);
    r->sym_arrangement(RIGHT);
  }

  //function for decide similar
  void aggregate_children(vector<Tree> &a,vector<bool> &used){
    if ( l == NULL)return;
    a.push_back(*l);
    a.push_back(*r);
    
    rep(i,2)used.push_back(false);
    l->aggregate_children(a,used);
    r->aggregate_children(a,used);
  }
  
  bool is_same_structure(Tree a,Tree b){
    if ( (a.l!=NULL&&b.l==NULL)||((a.l==NULL)&&b.l!=NULL))return false;
    if ( a.l==NULL)return true;
    if ( is_same_structure(*(a.l),*(b.l))==false||is_same_structure(*(a.r),*(b.r))==false)return false;
    return true;
  }

  double decide_similar(){
    //if ( (*this) == NULL)return similar=0;
    vector<Tree> all[2];
    vector<Tree> disj[2];
    vector<bool> used[2];
    vector<bool> used_disj[2];
    if ( l != NULL){
      l->aggregate_children(all[0],used[0]);
      l->decide_similar();
      r->aggregate_children(all[1],used[1]);
      r->decide_similar();
    }else return similar=0;

    rep(k,2){
      rep(i,all[k].size()){
	if ( used[k][i] == true)continue;
	used[k][i]=true;
	used_disj[k].push_back(false);
	disj[k].push_back(all[k][i]);
	REP(j,i+1,all[k].size()){
	  if ( is_same_structure(all[k][i],all[k][j]))used[k][j]=true;
	}
      }
    }
    
    
    rep(i,disj[0].size()){
      rep(j,disj[1].size()){
	if ( is_same_structure(disj[0][i],disj[1][j])){used_disj[0][i]=true;break;}
      }
    }
    
    double same =count(used_disj[0].begin(),used_disj[0].end(),true);
    double total=count(used_disj[0].begin(),used_disj[0].end(),false)+used_disj[1].size();
    same+=1;
    total+=1;
    return similar=same/total;
  }
  


  //arrangement left
  //number of node of left  > number of node of >right
  int dfs(){
    if ( l == NULL)return 1;
    int l_num=l->dfs(),r_num=r->dfs();
    if ( l_num < r_num)swap(l,r);
    return l_num+r_num+1;
  }
};

void parse(string &a,int &p,Tree &cur){
  if(  a[p] == '('){
    p++;
    cur.l=new Tree();
    parse(a,p,*(cur.l));
  }else if ( a[p] == 'x'){
    p++;
    return;
  }
  assert(a[p] ==' ');
  p++;
  cur.r=new Tree();
  parse(a,p,*(cur.r));
  p++;
}

void output(Tree & cur){
  if ( cur.l == NULL){
    putchar('x');
    return;
  }
  
  putchar('(');
  output(*(cur.l));
  putchar(' ');
  output(*(cur.r));
  putchar(')');
}

main(){
  string in;
  while(getline(cin,in) && in[0] != '0'){
    Tree root;
    int p=0;
    parse(in,p,root);
    // output(root);puts("");
    root.dfs();
    //    output(root);puts("");
    root.decide_similar();
    //output(root);puts("");
    root.sym_arrangement(LEFT);
    output(root);puts("");
    //puts("end");
  }
}

Compiler output:
a.cc: In function 'void parse(std::string&, int&, Tree&)':
a.cc:117:3: error: 'assert' was not declared in this scope
  117 |   assert(a[p] ==' ');
      |   ^~~~~~
a.cc:4:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    3 | #include<algorithm>
  +++ |+#include <cassert>
    4 | using namespace std;
a.cc: At global scope:
a.cc:137:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  137 | main(){
      | ^~~~