The Ward-Carver of the North Gate

Over the north gate of bitwick, the ward-carver recuts inscriptions before they are set into stone. A ward only holds if every operation in it is bracketed exactly once. Apprentices bring her inscriptions written flat, with the brackets left out, and she must work out the grouping and cut it herself. Sometimes what an apprentice brings is not an inscription at all, and then the stone is left blank.

expr is a string containing no whitespace. Return a string: the fully bracketed recut of expr, or the empty string "" if expr is not a well-formed inscription.

An inscription is one of:

• a numeral: one or more of the digits 0-9 (leading zeros are allowed, and are kept as written)
• ( followed by an inscription followed by )
• an operator applied to inscriptions.

The operators, loosest-binding first:

1. = — binary, non-associative: at most one = may stand outside brackets in any one inscription, so a=b=c is not well-formed while (a=b)=c is 2. + and - — binary, left-associative 3. * and / — binary, left-associative 4. ^ — binary, right-associative 5. - — prefix, and may be stacked 6. ! — postfix, and may be stacked

Prefix - binds looser than ^, so -a^b groups as -(a^b). The operand to the right of ^ is read at the prefix level, so a^-b is well-formed and groups as a^(-b); the operand to the left of ^ is read at the postfix level, so a prefix - standing there always applies to the whole power.

The recut:

• a numeral recuts to itself
• a binary application recuts to ( + recut left operand + the operator character + recut right operand + )
• a prefix - application recuts to (- + recut operand + )
• a postfix ! application recuts to ( + recut operand + !)

The result contains no spaces and no brackets other than those, so brackets in expr that only restate a grouping already forced by the rules do not appear in the result.

Anything that is not an inscription — including an inscription followed by any leftover characters, and including the empty string — is not well-formed.