Tree Transformation Puzzle
Let's get started with a puzzle!
First, you are given an arithmetic expression, which solely consists of integers, operator symbols
Figure C-1: A tree representation of
In the tree of the figure, each box is a leaf node labeled with an integer, and each circle is a non-leaf node labeled with an operator symbol
For any trees representing arithmetic expressions given for this puzzle, the root nodes have three child nodes, and all the other non-leaf nodes have one parent and two child nodes. Therefore, every non-leaf node is directly connected to exactly three nodes.
Let us think of transformation of the tree structure corresponding to the given arithmetic expression by applying either of the following operations on the entire tree or any of its subtrees arbitrarily many times.
Unless explicitly stated above, these operations change neither the parent-child relationship between two nodes nor the left-to-right order among child nodes sharing the same parent.
The new tree resulted from such operations represents a possibly different arithmetic expression having a possibly different value. The goal of this puzzle is to find the maximum possible value of such an expression through the operations described above applied arbitrarily many times.
For example, by swapping the two child nodes of the leftmost non-leaf node in Figure C-1, which has an operator symbol
Figure C-2: The result of swapping the two leftmost leaf nodes
And then by swapping the leftmost and the rightmost child nodes of the root in Figure C-2, you will have the tree in Figure C-3.
The value of the original arithmetic expression
Figure C-3: The result of swapping the leftmost and the rightmost nodes of the root
In addition, by making the leftmost child node of the root in Figure C-3 the new root, and the original root the rightmost child node of the new root, you will have the tree in Figure C-4.
The expression represented by this tree is
Figure C-4: The result of making the leftmost non-leaf node the new root
The input consists of multiple datasets, each being a line containing a root-expression defined in the following.
Each dataset has at lease five characters (i.e. three digits and two signs). The total number of the characters in all the datasets in the input is at most 500,000. The depths of nested parentheses are no greater than 100.
The end of the input is indicated by a line containing a minus one (−1).
For each dataset, output one line containing the answer of the puzzle.
2+3+4 2-3-4 ((5-1)-1)-7-9 (3+2)-(4-1)-(5+6) -1
Output for the Sample Input
9 -1 7 19