What associativity was it again

Question

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 minimally¹ 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 -> (ab)c
ab123z -> ((((ab)1)2)3)z
ab(cde)fo(0O) -> ((((ab)((cd)e))f)o)(0O)
(aBC)(dE) -> ((aB)C)(dE)
code(Golf) -> (((co)d)e)(((Go)l)f)
(code)Golf -> ((((((co)d)e)G)o)l)f

Right associative

abc -> a(bc)
ab123z -> a(b(1(2(3z))))
ab(cde)fo(0O) -> a(b((c(de))(f(o(0O)))))
(aBC)(dE) -> (a(BC))(dE)
code(Golf) -> c(o(d(e(G(o(lf))))))
(code)Golf -> (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.}

Answer 1

Retina 0.8.2, 61 bytes

+1`(\(((\()|(?<-3>\))|[^()])+(?(3)$)\)|[^()]){2}(?=[^)])
($&)

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
  (?<-3>\))   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.

($&)

Wrap the match in disambiguating parentheses.

Answer 2

JavaScript (ES6), 128 bytes

f=([a,...s],c=q=p="",$=")")=>s[1]?a<$?s.map(t=>c||(t<$?++p:t>$||p--||(c=f(q),q=""))?q+=t:0)&&q?a+c+$+a+f(q)+$:c:a+"("+f(s)+$:a+s

Recognizes () as parentheses, and outputs a right-associative expression. Test cases additionally include nested parentheses.

Try it online!

Explanation

Recursively disambiguates sub-expressions within parentheses given in the input. To track nesting depth, it increments the variable p upon encountering a left paren (following the initial opening paren). A right paren decrements the counter, and if p = 0 prior to decrementing, the function recurs on the accumulated sub-expression. A quick visual:

(ab(cd(ef)gh)ij)
0  1  2  1  0  = 0, so call function

When handling parentheses in inputs, i.e. the first character is a (, it partitions the input into the enclosed sub-expression and everything following the matching paren, e.g. (cd)ef splits into cd, which is fed back into the function, and ef, both of which are subsequently wrapped in parentheses. If an enclosed sub-expression has no trailing characters, the result of recurring on it isn't wrapped in parentheses. (cd)ef -> (cd)(ef) but (cd) -> cd

Ungolfed:

f = (
    [a, ...s],                                       // destructure string, e.g. "abc" => "a", ["b", "c"]
    c = q = p = "",
    $ = ")"
) =>
    s[1] ?                                           // if input length > 2 ...
        a < $                                        //     if first char is ( ...
            ? s.map(t =>
                c                                    //         stores disambiguated sub-expression
                || (                                 //         if sub-expression not yet found...
                        t < $                        //             if char is ( ...
                            ? ++p
                        : t > $
                            || p--                   //             if char is ) and p = 0, e.g. outer closing paren found...
                            || (c = f(q), q = "")    //                 reset q to accumulate characters following the closing paren
                )                                    //         this expression returns a truthy value if should append current char (i.e. if t is not the final closing paren)
                    ? q += t
                    : 0
            )
                && q
                    ? a + c + $ + a + f(q) + $       //         a = "(", guaranteed by the conditional check
                    : c
            : a + "(" + f(s) + $
    : a+s                                            // since s has length 1, appending it simply appends its first value