Patch Bay Root-First Translator

A boutique modular synthesizer lets a sound designer describe how numbered oscillator channels are blended using three panel operations written in ordinary infix notation: + (mix two channels), - (phase-cancel one channel against another), and * (ring-modulate two channels), combined with parentheses for grouping. Each single digit 0-9 in the formula names one raw channel (a leaf of the underlying operation tree).

The synth's onboard sequencer cannot evaluate the formula directly the way a human reads it. Instead it must be told the root operation first — the very last combination that produces the final signal — before it can recurse into how each side of that operation was built. In other words, you must report the formula's operation tree in root-first (preorder / prefix) order: print the operation (or channel) at the root, then the entire left subtree in the same root-first order, then the entire right subtree in the same root-first order.

The tree is built the same way a calculator would parse the formula: * binds tighter than +/-, operators of equal precedence group left to right (so 9-8-7 is (9-8)-7, not 9-(8-7)), and parentheses override precedence exactly as written.

Input format

A single line containing the patch formula: a non-empty string made only of the characters 0-9, +, -, *, (, and ).

Output format

Print the operation tree's root-first (preorder) traversal as tokens separated by single spaces: each token is either an operator (+, -, *) or a single digit. End with a newline.

Constraints

• 1 <= length of the formula <= 300.
• The formula is guaranteed to be syntactically valid: parentheses are balanced, every operator has an operand on each side, there are no empty sub-expressions, and there is no unary +/-.
• Every operand is exactly one digit (0-9); there are no multi-digit numbers.
• There is no division operator and no whitespace in the formula.

1+2*3

+ 1 * 2 3

(1+2)*3

* + 1 2 3