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.
JavaScript (ES6), 208 197 bytes

s=&gt;((q=x=&gt;x.map((_,i)=&gt;(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)=&gt;r.indexOf(l)&lt;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=&gt;(                                  // s = input string
  (q=x=&gt;                              // q = parenthesise array function
    x.map((_,i)=&gt;(
      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)=&gt;r.indexOf(l)&lt;i?0:o+=l+`
`
  ),o)                                // return o


Test



Input = &lt;input type="text" id="input" value="a * b|c|d" /&gt;&lt;button onclick='results.innerHTML=(

s=&gt;((q=x=&gt;x.map((_,i)=&gt;(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)=&gt;r.indexOf(l)&lt;i?0:o+=l+`
`),o)

)(input.value)'&gt;Go&lt;/button&gt;&lt;pre id="results"&gt;&lt;/pre&gt;