Inorder Traversals

Background:

Trees form a major part of computer science, even though computer scientists draw the silly things upside down. Computer scientists also tend to be lazy which can lead to sloppy notation for their trees.

In this problem, you'll be given a binary tree and will print out the in order traversal (left, root, right) of that tree.

A tree is denoted by the form:

(root left right)
where root, left, and right are the root, left and right subtrees of the node in question. A null tree would be represented as (). This can lead to quite lengthy trees if you try to specify every child. Therefore, we allow the following relaxations:
  1. If one of the children of a node is empty, that child may be omitted entirely.
  2. If a root has no children, the () may be omitted entirely.
Of course, some computer scientists are not quite as lazy as others and may choose to put the () in at all times to make a fully balanced binary tree. Therefore, the following are all representations of the same tree, which has 4 at its root, with children nodes of 5 and 6.

Of course, while computer scientists may be lazy, they hate ambiguity. The relaxation rules can be done only so long as the tree is not ambiguous. If a root has only one child specified, then assume that child is the left child. ie, to make a tree with 4 at the root, and 5 as the right child, the tree would have to specified as one of

Input:

The input will consist of a series of test cases, each arbitrarily long. A test case will contain at least a non-null root node. Furthermore, each tree will always have the outer (). Therefore, the test case obviously ends when () are matched. There is an arbitrary amount of spaces in the tree specifications and tree may be on more than one line. Each node has a one character value.

Output:

For each test case, print one line consisting of the in order traversal of the tree. Separate each value by a space.

Sample Input:

(4 () 5)
(4 5)
(4 5
6)
(4 5 (6 () ()))

Sample Output:

4 5
5 4
5 4 6
5 4 6