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
ora(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)
- as with the input you may choose between
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.