11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have to list down the exact operators we have to consider. Is ! an operator? What about ? \$\endgroup\$ – Optimizer Nov 29 '15 at 10:31
  • \$\begingroup\$ @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. \$\endgroup\$ – orlp Nov 29 '15 at 10:34
  • \$\begingroup\$ Ah okay. So anything except a term is an operator... \$\endgroup\$ – Optimizer Nov 29 '15 at 10:37
  • \$\begingroup\$ So both terms and operators are always one character long? \$\endgroup\$ – user81655 Nov 29 '15 at 11:05
  • 1
    \$\begingroup\$ insert obligatory LISP-related pun here \$\endgroup\$ – cat Nov 29 '15 at 12:27
2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.