What associativity was it again Non-associative operators (for example the subtraction-operator) often are either left- or right associative, such that one has to write less parentheses. Consider for example the following:

$$
a-b-c
$$

Probably everybody read that as \$(a-b)-c\$, by default (usually) subtraction is left-associative.

Now let us consider some operation \$\diamond: X \times X \to X\$, the only thing we know about it is that it is not associative. In this case the following is ambiguous:

$$
a \diamond b \diamond c
$$

It could either mean \$(a \diamond b) \diamond c\$ or it could mean \$a \diamond (b \diamond c)\$.

Challenge

Given some possibly parenthesised expression that is ambiguous, your task is to parenthesise it such that there is no ambiguity. You can chooose freely whether the operator should be left- or right associative.

Since there is only one operation the operator is only implied, so for the above example you'll get abc as input. For left-associative you'll output (ab)c and for right-associative you'll output a(bc).

Input / Output


Input will be a string of at least 3 characters


the string is guaranteed to be ambiguous (ie. there are missing parentheses)
you're guaranteed that no single character is isolated (ie. (a)bc or a(bcd)e is invalid input)
the string is guaranteed to only contain alphanumeric ASCII (ie. [0-9], [A-Z] and [a-z]) and parentheses (you may choose (), [] or {})

Output will be a minimally1 parenthesized string that makes the string unambiguous


as with the input you may choose between (), [], {} for the parentheses
output may not contain whitespace/new-lines, except for leading and trailing ones (finite amount)



Test cases

These use () for parentheses, there is a section for each associativity you may choose (ie. left or right):

Left associative

abc -&gt; (ab)c
ab123z -&gt; ((((ab)1)2)3)z
ab(cde)fo(0O) -&gt; ((((ab)((cd)e))f)o)(0O)
(aBC)(dE) -&gt; ((aB)C)(dE)
code(Golf) -&gt; (((co)d)e)(((Go)l)f)
(code)Golf -&gt; ((((((co)d)e)G)o)l)f


Right associative

abc -&gt; a(bc)
ab123z -&gt; a(b(1(2(3z))))
ab(cde)fo(0O) -&gt; a(b((c(de))(f(o(0O)))))
(aBC)(dE) -&gt; (a(BC))(dE)
code(Golf) -&gt; c(o(d(e(G(o(lf))))))
(code)Golf -&gt; (c(o(de)))(G(o(lf)))




1: Meaning removing any pair of parentheses will make it ambiguous. For example a(b(c)) or (a(bc)) are both not minimally parenthesised as they can be written as a(bc) which is not ambiguous.
Retina 0.8.2, 61 bytes

+1`(\(((\()|(?&lt;-3&gt;\))|[^()])+(?(3)$)\)|[^()]){2}(?=[^)])
($&amp;)


Try it online! Link includes test cases. Explanation: I'd really like to use a recursive regex (([^()]|\((?1)\)){2})(?=[^)]) here, but .NET only has balancing groups, so it's a bit verbose.

+1`


Repeatedly replace the first match each time. This ensures left-associativity.

(           Either
 \(          Match outer `(`
 (           Either
  (\()        Capture a `(` into $3
 |           Or
  (?&lt;-3&gt;\))   A `)` if it matched an earlier `(`
 |           Or
  [^()]       Something else
 )+          Match as much of the above as possible
 (?(3)$)     But don't leave `(`s unmatched
 \)          Match outer `)`
|           Or
 [^()]       Match something else
){2}        Match the above twice
(?=[^)])    Followed by a non-`)`


Either, a ( followed by a string containing balanced ()s,  followed by a ), or a non-(), twice, followed by a non-). This represents an ambiguous match.

($&amp;)


Wrap the match in disambiguating parentheses.