use std::hash::Hash;
use std::collections::hash_set::Iter;
use std::rc::Rc;
use std::ops::DivAssign;
use std::ops::MulAssign;
use std::ops::SubAssign;
use std::collections::BinaryHeap;
use std::str::FromStr;
use std::collections::HashSet;
use std::collections::BTreeMap;
use std::fmt::Display;
use std::ops::Neg;
use std::ops::Div;
use std::ops::Mul;
use std::ops::Add;
use std::ops::{AddAssign, Sub};
use std::cmp::max;
use std::collections::VecDeque;
use std::cmp::min;
use std::collections::{HashMap, BTreeSet};
use std::cmp::Ordering;
use std::fmt::Debug;

fn read_line() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).expect("No Line");
    buffer.trim().to_owned()
}
fn read_lines<T: std::str::FromStr>(count: usize) -> Vec<T> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(buffer.trim().parse().ok().expect("Can't Parse"));
        buffer.clear();
    }
    vec
}
fn read_tabulate<R, T: Fn(&str)->R> (count: usize, transformer: T) -> Vec<R> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(transformer(buffer.trim()));
        buffer.clear();
    }
    vec
}
fn read_value<T: std::str::FromStr>() -> T {
    read_line().trim().parse().ok().unwrap()
}
fn read_values<T: std::str::FromStr>() -> Vec<T> {
    read_line().trim().split_whitespace().map(|x| x.parse().ok().expect("Can't Parse")).collect::<Vec<T>>()
}
macro_rules! freeze {
    ($($id:ident), *) => {
        $(let $id = $id;)*
    };
}
macro_rules! read_map {
    ($ident: ident: [$block: block; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$block: block; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
}
macro_rules! read {
    (mut $ident: ident: String) => {
        let mut $ident = read_value::<String>();
    };
    ($ident: ident: String) => {
        let $ident = read_value::<String>();
    };
    (mut $ident: ident: [$ty:ty]) => {
        let mut $ident = read_values::<$ty>();
    };
    ($ident: ident: [$ty:ty]) => {
        let $ident = read_values::<$ty>();
    };
    (mut $ident: ident: [[$ty:ty]; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| read_values::<$ty>()).collect::<Vec<_>>();
    };
    ($ident: ident: [[$ty:ty]; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| read_values::<$ty>()).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$ty:ty; $size:expr]) => {
        let mut $ident = read_lines::<$ty>($size);
    };
    ($ident: ident: [$ty:ty; $size:expr]) => {
        let $ident = read_lines::<$ty>($size);
    };
    ($ident: ident: [$block: block; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$block: block; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    ($($token: tt)*) => {
        let mut iter = read_values::<String>().into_iter();
        read_from_iter!(iter; $($token)*);
    };
}
macro_rules! read_from_iter {
    ($iter:expr; mut $ident:ident:$ty:ty, $($rest:tt)*) => {
        let mut $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
        read_from_iter!($iter; $($rest)*);
    };
    ($iter:expr; $ident:ident:$ty:ty, $($rest:tt)*) => {
        let $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
        read_from_iter!($iter; $($rest)*);
    };
    ($iter:expr; mut $ident:ident:$ty:ty) => {
        let mut $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
    };
    ($iter:expr; $ident:ident:$ty:ty) => {
        let $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
    };
    ($iter: expr; ) => {};
}
struct KeyValue<K, V> {
    key: K,
    value: V
}
impl <K: PartialOrd, V> PartialEq for KeyValue<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.key.eq(&other.key)
    }
}
impl <K: PartialOrd, V> Eq for KeyValue<K, V> {}
impl <K: PartialOrd, V> PartialOrd for KeyValue<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.key.partial_cmp(&other.key)
    }
}
impl <K: PartialOrd, V> Ord for KeyValue<K, V> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key.partial_cmp(&other.key).ok_or("Can't Compare").unwrap()
    }
}
#[derive(Eq, PartialEq)]
struct Rev<T: Ord>(T);
impl <T: std::cmp::Ord> PartialOrd for Rev<T> {
    fn partial_cmp(&self, rhs: &Rev<T>) -> std::option::Option<std::cmp::Ordering> { 
        rhs.0.partial_cmp(&self.0)
    }
}
impl <T: Ord> Ord for Rev<T> {
    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering { 
        rhs.0.cmp(&self.0)
    }
}

#[derive(Debug)]
enum BinaryTree {
    Nil,
    Node{left: Box<BinaryTree>, right: Box<BinaryTree>}
}
impl FromStr for BinaryTree {
    type Err = ();
    fn from_str(s: &str) -> std::result::Result<Self, <Self as std::str::FromStr>::Err> {
        let mut stack = Vec::new();
        for c in s.chars() {
            match c {
                'x' => stack.push(BinaryTree::Nil),
                ')' => {
                    let first = stack.pop().unwrap();
                    let second = stack.pop().unwrap();
                    stack.push(BinaryTree::Node{left: Box::new(second), right: Box::new(first)});
                }
                '(' | ' ' => (),
                _ => return Err(())
            }
        }
        if stack.len() == 1 {
            let result = stack.pop().unwrap();
            Ok(result)
        }else {
            Err(())
        }
    }
}
enum BiTree<T> {
    Leaf{value: T},
    Node{value: T, left: Rc<BiTree<T>>, right: Rc<BiTree<T>>}
}
impl <T> BiTree<T> {
    fn get_value(&self) -> &T {
        match self {
            &BiTree::Leaf{ref value} => value,
            &BiTree::Node{ref value, left: _, right: _} => value
        }
    }
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
struct Rational {
    num: i32, den: i32
}
fn gcd(a: i32, b: i32) -> i32 {
    match b {
        0 => a,
        _ => gcd(b, a % b)
    }
}
impl Rational {
    fn new(n: i32, d: i32) -> Rational {
        let g = gcd(n.abs(), d.abs());
        let s = n.signum() * d.signum();
        Rational{num: n.abs() * s / g, den: d.abs() / g}
    }
}
impl Sub for Rational {
    type Output = Rational;
    fn sub(self, rhs: Rational) -> <Self as std::ops::Sub<Rational>>::Output {
        Rational::new(self.num * rhs.den - rhs.num * self.den, self.den * rhs.den)
    }
}
impl PartialOrd for Rational {
    fn partial_cmp(&self, rhs: &Rational) -> std::option::Option<std::cmp::Ordering> {
        (*self - *rhs).num.partial_cmp(&0)
    }
}
impl Ord for Rational {
    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
        (*self - *rhs).num.cmp(&0)
    }
}
struct TreeInfo {
    id: usize,
    asynmmetrity: Rational,
}
fn swap(tree: &Rc<BiTree<TreeInfo>>, all_trees: &mut HashMap<(usize, usize), usize>, sub_trees: &mut Vec<HashSet<usize>>, node_cache: &mut Vec<Rc<BiTree<TreeInfo>>>) -> Rc<BiTree<TreeInfo>> {
    match &**tree {
        &BiTree::Leaf{value: _} => tree.clone(),
        &BiTree::Node{ref value, ref left, ref right} => {
            if let Some(&pos) = all_trees.get(&(right.get_value().id, left.get_value().id)) {
                node_cache[pos].clone()
            }else {
                let id = node_cache.len();
                all_trees.insert((right.get_value().id, left.get_value().id), id);
                let new = Rc::new(BiTree::Node{value: TreeInfo{id: id, asynmmetrity: value.asynmmetrity}, left: swap(right, all_trees, sub_trees, node_cache), right: swap(left, all_trees, sub_trees, node_cache)});
                node_cache.push(new.clone());
                let original = sub_trees[value.id].clone();
                sub_trees.push(original);
                new
            }
        }

    }
}
fn construct(tree: &BinaryTree, all_trees: &mut HashMap<(usize, usize), usize>, sub_trees: &mut Vec<HashSet<usize>>, node_cache: &mut Vec<Rc<BiTree<TreeInfo>>>) -> Rc<BiTree<TreeInfo>> {
    match tree {
        &BinaryTree::Nil => node_cache[0].clone(),
        &BinaryTree::Node{ref left, ref right} => {
            let left_node = construct(&left, all_trees, sub_trees, node_cache);
            let right_node = construct(&right, all_trees, sub_trees, node_cache);
            let min_id = min(left_node.get_value().id, right_node.get_value().id);
            let max_id = max(left_node.get_value().id, right_node.get_value().id);
            if let Some(&id) = all_trees.get(&(min_id, max_id)) {
                node_cache[id].clone()
            }else {
                let id = node_cache.len();
                let mut union = sub_trees[min_id].union(&sub_trees[max_id]).cloned().collect::<HashSet<_>>();
                let intersection = sub_trees[min_id].intersection(&sub_trees[max_id]).count();
                let info = TreeInfo{id: id, asynmmetrity: Rational::new(intersection as i32, union.len() as i32)};
                union.insert(id);
                all_trees.insert((min_id, max_id), id);
                sub_trees.push(union);
                let res = Rc::new(BiTree::Node{value: info, left: left_node, right: right_node});
                node_cache.push(res.clone());
                res
            }
        }
    }
}

fn compare(a: &BiTree<TreeInfo>, b: &BiTree<TreeInfo>, cache: &mut HashMap<(usize, usize), Ordering>) -> Ordering {
    if a.get_value().id == b.get_value().id {
        Ordering::Equal
    }else if a.get_value().asynmmetrity != b.get_value().asynmmetrity {
        a.get_value().asynmmetrity.cmp(&b.get_value().asynmmetrity).reverse()
    }else if let Some(&o) = cache.get(&(a.get_value().id, b.get_value().id)) {
        o
    }else if let Some(&o) = cache.get(&(b.get_value().id, a.get_value().id)) {
        o.reverse()
    }else {
        match (a, b) {
            (&BiTree::Node{value: _, left: ref a_left, right: ref a_right}, &BiTree::Node{value: _, left: ref b_left, right: ref b_right}) => {
                let (a_greater, a_lesser) = match compare(&a_left, &a_right, cache) {
                    Ordering::Greater => (a_left, a_right),
                    _ => (a_right, a_left)
                };
                let (b_greater, b_lesser) = match compare(&b_left, &b_right, cache) {
                    Ordering::Greater => (b_left, b_right),
                    _ => (b_right, b_left),
                };
                let res = compare(&a_greater, &b_greater, cache).then_by(||compare(&a_lesser, &b_lesser, cache));
                cache.insert((a.get_value().id, b.get_value().id), res);
                res
                }
            _ => panic!()
        }
    }
}
trait RichOrdering {
    fn then_by<F: FnOnce() -> Ordering>(&self, func: F) -> Ordering;
}
impl RichOrdering for Ordering {
    fn then_by<F>(&self, func: F) -> std::cmp::Ordering where F: std::ops::FnOnce() -> Ordering {
        match self {
            &Ordering::Equal => func(),
            _ => *self
        }
    }
}
fn reconstruct(tree: &BiTree<TreeInfo>, cmp_cache: &mut HashMap<(usize, usize), Ordering>, is_left: bool) -> BinaryTree {
    match tree {
        &BiTree::Leaf{value: _} => BinaryTree::Nil,
        &BiTree::Node{value: _, ref left, ref right} => {
            let (l, r) = match compare(&left, &right, cmp_cache) {
                Ordering::Less if is_left => (right, left),
                Ordering::Greater if !is_left => (right, left),
                _ => (left, right)
            };
            BinaryTree::Node{left: Box::new(reconstruct(&l, cmp_cache, true)), right: Box::new(reconstruct(&r, cmp_cache, false))}
        }
    }
}
fn formatted(tree: &BinaryTree) -> BinaryTree {
    let mut all_trees = HashMap::new();
    let mut sub_trees = vec![HashSet::new()]; sub_trees[0].insert(0);
    let mut node_cache = vec![Rc::new(BiTree::Leaf{value: TreeInfo{id: 0, asynmmetrity: Rational::new(0, 1)}})];
    let mut cmp_cache = HashMap::new();
    let root = construct(tree, &mut all_trees, &mut sub_trees, &mut node_cache);
    reconstruct(&root, &mut cmp_cache, true)
}
impl <T> Display for BiTree<T> {
    fn fmt<'a>(&self, fmt: &mut std::fmt::Formatter<'a>) -> std::result::Result<(), std::fmt::Error> {
        match self {
            &BiTree::Leaf{value: _} => write!(fmt, "x"),
            &BiTree::Node{value: _, ref left, ref right} => write!(fmt, "({} {})", left, right)
        }
    }
}
impl Display for BinaryTree {
    fn fmt<'a>(&self, fmt: &mut std::fmt::Formatter<'a>) -> std::result::Result<(), std::fmt::Error> {
        match self {
            &BinaryTree::Nil => write!(fmt, "x"),
            &BinaryTree::Node{ref left, ref right} => write!(fmt, "({} {})", left, right)
        }
    }
}
fn main() {
    loop {
        read!(input: String);
        if input == "0" {break;}
        let tree = input.parse::<BinaryTree>().unwrap();
        let format_tree = formatted(&tree); 
        println!("{}", format_tree);
    }
}


Measured memory_bytes: 5080