Expresiones completamente entre paréntesis

11

Hoy su desafío es producir todos los paréntesis completos posibles de una expresión.

Su entrada es una sola línea de ASCII imprimible que contiene uno o más términos separados por operadores. La entrada también puede contener espacios; debe ignorarlos. Un término es [a-zA-Z0-9], un operador es [^ ()a-zA-Z0-9]. Puede suponer que la entrada siempre es válida.

Imprima todas las formas posibles de paréntesis completos de la expresión dada, separados por nuevas líneas con una nueva línea final opcional.

Hacer no :

  • Términos entre paréntesis: solo entre paréntesis alrededor de los operadores.
  • Reordenar los términos.
  • Salida de cualquier espacio.

Ejemplo de entrada / salida:

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)

El código más pequeño en bytes gana.

code-golf balanced-string orlp
fuente
Debe enumerar los operadores exactos que debemos tener en cuenta. Es !un operador? ¿Qué hay de ↑?
Optimizador
@Optimizer Enumeré la expresión regular exacta de lo que se considera un operador. !se ajusta a la expresión regular, también lo hace ↑, sin embargo, no ↑puede ser parte de la entrada porque no es ASCII imprimible.
orlp
Ah bien. Entonces, cualquier cosa, excepto un término, es un operador ...
Optimizer
Entonces, ¿tanto los términos como los operadores tienen siempre un carácter?
user81655
1
inserte aquí un juego de palabras obligatorio relacionado con LISP
gato el

Respuestas:

2

Pyth, 38 bytes

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

Pruébalo en línea.

Define una función recursiva que:

  • devuelve la entrada si su longitud es 1
  • toma todas las dos divisiones de la entrada en los operadores y para cada división:
    • se llama recursivamente en cada una de las mitades
    • toma el producto cartesiano de los resultados de cada mitad
    • une cada resultado por el operador en la división
    • entre paréntesis el resultado unido
  • y finalmente concatena las matrices resultantes.

Luego se llama a la función con la cadena de entrada con espacios eliminados y los resultados se unen mediante nuevas líneas.

PurkkaKoodari
fuente
3

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)

Explicación

Utiliza una función recursiva que toma una matriz [ t, o, t, o, etc... ]y paréntesis de cada par de dos términos consecutivos, [ (tot), o, etc... ]y repite este proceso hasta que solo haya un elemento en la matriz, luego filtra los valores duplicados.

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

Prueba

Mostrar fragmento de código

usuario81655
fuente