# Fully parenthesize expressions

Today your challenge is to produce all possible full parenthesizations of an expression.

Your input is a single line of printable ASCII containing one or more terms separated by operators. The input might also contains spaces - you must ignore these. A term is [a-zA-Z0-9], an operator is [^ ()a-zA-Z0-9]. You may assume that the input is always valid.

Output all possible ways to fully parenthesize the given expression, separated by newlines with an optional trailing newline.

Do not:

• Parenthesize terms - only parenthesize around operators.
• Reorder the terms.
• Output any spaces.

Example input/output:

N
N

a * b
(a*b)

x_x_0
(x_(x_0))
((x_x)_0)

a * b|c|d
(a*(b|(c|d)))
(a*((b|c)|d))
((a*b)|(c|d))
((a*(b|c))|d)
(((a*b)|c)|d)


Smallest code in bytes wins.

• You have to list down the exact operators we have to consider. Is ! an operator? What about ↑ ? Nov 29 '15 at 10:31
• @Optimizer I listed the exact regular expression of what is considered an operator. ! fits the regex, so does ↑, however ↑ can not be part of the input because it is not printable ASCII.
– orlp
Nov 29 '15 at 10:34
• Ah okay. So anything except a term is an operator... Nov 29 '15 at 10:37
• So both terms and operators are always one character long? Nov 29 '15 at 11:05
• insert obligatory LISP-related pun here
– cat
Nov 29 '15 at 12:27

# Pyth, 38 bytes

L?tbsmmjj@bdk"()"*y<bdy>bhd:1lb2bjy-zd


Try it online.

It defines a recursive function that:

• returns the input if its length is 1
• takes all two-splits of the input on operators, and for each split:
• calls itself recursively on each of the halves
• takes the Cartesian product of the results of each half
• joins each result by the operator at the split
• parenthesizes the joined result
• and finally concatenates the resulting arrays.

The function is then called with the input string with spaces removed and the results are joined by newlines.

# JavaScript (ES6), 208 197 bytes

s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+
),o)


## Explanation

Uses a recursive function that takes an array of [ t, o, t, o, etc... ] and parenthesises each consecutive pair of two terms together like [ (tot), o, etc... ] and repeats this process until there is only one element in the array, then filters out the duplicate values.

s=>(                                  // s = input string
(q=x=>                              // q = parenthesise array function
x.map((_,i)=>(
a=[                             // a = p with parenthesised pair of terms
...x.slice(0,i*=2),
p="("+x[i]+x[++i]+x[++i]+")", // parenthesise and join 2 terms and an operator
...x.slice(i+1)
],
x[i]?a[1]                       // make sure the loop is not over
?q(a)                         // check next level of permutations
:r.push(p)                    // add the permutation to the results
:0
))
)([...s.replace(/ /g,               // remove spaces and parenthesise all expressions
o="")],                           // o = output string
r=[]),                            // r = array of result strings
r.map(                              // filter out duplicates
(l,i)=>r.indexOf(l)<i?0:o+=l+

),o)                                // return o


## Test

Input = <input type="text" id="input" value="a * b|c|d" /><button onclick='results.innerHTML=(

s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+
),o)

)(input.value)'>Go</button><pre id="results"></pre>