Desparéntesis de una cadena

25

Dada una cadena correctamente entre paréntesis como entrada, genera una lista de todas las subcadenas no vacías dentro de paréntesis coincidentes (o fuera de todos los paréntesis), con paréntesis anidados eliminados. Cada subcadena debe ser la secuencia de caracteres en exactamente los mismos paréntesis coincidentes. Las subcadenas se deben enumerar en orden de profundidad, y las subcadenas de la misma profundidad se deben enumerar en el orden en que aparecen en la cadena. Suponga que la entrada siempre está entre paréntesis correctamente.

Puede suponer que la entrada contiene solo letras minúsculas y paréntesis ASCII.

Su respuesta debe ser una función que, cuando se le da una cadena, devuelve una lista de cadenas.

Ejemplos:

                   'a(b)c(d)e' -> ['ace', 'b', 'd']
                   'a(b(c)d)e' -> ['ae', 'bd', 'c']
                  'a((((b))))' -> ['a', 'b']
                        'a()b' -> ['ab']
                            '' -> []
                           'a' -> ['a']
          '(((a(b)c(d)e)f)g)h' -> ['h', 'g', 'f', 'ace', 'b', 'd']
'ab(c(((d)ef()g)h()(i)j)kl)()' -> ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Pocos bytes ganan.

Redstonerodent
fuente
¿Están 'i'y 'd'en el orden correcto en el último caso de prueba?
PurkkaKoodari
@ Pietu1998 iestá menos anidado que d.
fiesta
@feersum Oh, cierto.
PurkkaKoodari
1
¿Le importaría permitir también los otros tipos de envío estándar, en particular los programas completos? No todos los idiomas tienen un concepto de funciones. Para obtener un consenso predeterminado, consulte meta.codegolf.stackexchange.com/a/2422/8478 y meta.codegolf.stackexchange.com/questions/2447/… .
Martin Ender
2
@redstonerodent La redacción que tiendo a usar es "Puede escribir un programa o función, tomando entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o alternativa más cercana), valor de retorno de función o parámetro de función (fuera) ". y en su caso "El resultado puede estar en cualquier formato conveniente, inequívoco y de lista plana".
Martin Ender

Respuestas:

11

JavaScript ES6, 91 93104133148

Edit2 2 bytes guardados thx user81655

Editar usando más cadenas y menos matrices

Pruebe a ejecutar el fragmento a continuación en un navegador compatible con EcmaScript 6

f=s=>[...s].map(c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),o=[],l=0)&&(o+'').match(/\w+/g)||[]

// Less golfed

u=s=>{
  o=[]; l=0;
  [...s].map(c=>{
    if (c>'(') // letters or close bracket
      o[l]=(o[l]||'')+c, // add letter or close bracket to current level string
      l-=c<'a' // if close bracket, decrement level
    else
      ++l // open bracket, increment level
  })
  o = o+'' // collapse array to comma separated string
  return o.match(/\w+/g)||[] // fetch non empty strings into an array
}

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[ 'a(b)c(d)e'                    // ['ace', 'b', 'd']
 , 'a(b(c)d)e'                    // ['ae', 'bd', 'c']
 , 'a((((b))))'                   // ['a', 'b']
 , 'a()b'                         // ['ab']
 , ''                             // []
 , 'a'                            // ['a']
 , '(((a(b)c(d)e)f)g)h'           // ['h', 'g', 'f', 'ace', 'b', 'd']
 , 'ab(c(((d)ef()g)h()(i)j)kl)()' // ['ab', 'ckl', 'hj', 'efg', 'i', 'd']
].forEach(t=>console.log(t +" -> " + f(t)))
<pre id=O></pre>

edc65
fuente
Ahorre 2 bytes con c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),.
user81655
@ user81655 agradable, gracias
edc65
8

Julia, 117 86 83 bytes

v->(while v!=(v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))end;split(v))

Es una solución regex.

Sin golf:

function f(v)
  w=""
  while v!=w
    w=v
    v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))
  end
  split(v)
end

r"(\(((?>\w|(?1))*)\))(.*)"es una (?1)expresión regular recursiva ( grupo recursivo 1) que coincidirá con los primeros paréntesis balanceados más externos (que no contienen paréntesis desequilibrados / invertidos), con el segundo grupo que contiene todo dentro de los paréntesis (sin incluir los paréntesis mismos) y el tercer grupo que contiene todo después de los paréntesis (hasta el final de la cadena).

replace(v,r"...",s"\g<3> \g<2>")luego moverá el segundo grupo al final de la cadena (después de un espacio, para actuar como delimitador), con los paréntesis relevantes eliminados. Al iterar hasta v == w, se garantiza que la sustitución se repita hasta que no queden paréntesis. Debido a que las coincidencias se mueven hasta el final, y luego la siguiente coincidencia corresponde al primer paréntesis, el resultado será la cadena desglosada en orden de profundidad.

Luego splitdevuelve todos los componentes que no son espacios en blanco de la cadena en forma de una matriz de cadenas (que no tienen espacios en blanco).

Tenga en cuenta que w=""se usa en el código no protegido para asegurarse de que el ciclo while se ejecuta al menos una vez (excepto si la cadena de entrada está vacía, por supuesto), y no es necesaria en la forma de golf.

Gracias a Martin Büttner por su ayuda con el ahorro de 3 bytes.

Glen O
fuente
Aseado, he llegado a la misma solución de forma independiente en Retina. Hay 44 bytes allí, pero tal como están las soluciones de programa completo no están permitidas. : /
Martin Ender
Puede guardar tres bytes usando en \wlugar de [^()].
Martin Ender
@ MartinBüttner - gracias. En realidad lo había considerado, pero me preocupaba haber pasado por alto algo y que fallara en algún caso extremo. Sin embargo, si dices que está bien, entonces está bien.
Glen O
6

Python, 147 bytes

def f(s):
 d=0;r=[['']for c in s]
 for c in s:
  if c=='(':d+=1;r[d]+=['']
  elif c==')':d-=1
  else:r[d][-1]+=c
 return[i for i in sum(r,[])if i]

Pruebas unitarias:

assert f('a(b)c(d)e') == ['ace', 'b', 'd']
assert f('a(b(c)d)e') == ['ae', 'bd', 'c']
assert f('a((((b))))') == ['a', 'b']
assert f('a()b') == ['ab']
assert f('') == []
assert f('a') == ['a']
assert f('(((a(b)c(d)e)f)g)h') == ['h', 'g', 'f', 'ace', 'b', 'd']
assert f('ab(c(((d)ef()g)h()(i)j)kl)()') == ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Me gusta este acertijo; ¡es muy lindo!

Quuxplusone
fuente
4

Pyth, 32 bytes

fTscR)uX0.<GJ-FqLH`()@[Hdk)Jzmkz

Banco de pruebas

Basado libremente en el enfoque de @ Quuxplusone. Construye listas de caracteres separadas por espacios en cada profundidad, luego las divide y filtra los grupos vacíos. La lista de trabajo se gira para mantener la lista de profundidad actual al frente en todo momento.

isaacg
fuente
4

Retina , 44 41 bytes

+`\(((\w|(\()|(?<-3>.))*).(.*)
$4 $1
S_` 

Corre con la -sbandera. Observe el espacio al final de la última línea.

Se me ocurrió esta solución independientemente de Glen O, pero resulta ser idéntica. La idea es hacer coincidir el primer par de paréntesis, eliminarlo e insertar su contenido al final de la salida (repetidamente). Debido a la falta de recursividad de .NET en expresiones regulares, tuve que usar grupos de equilibrio que son cuatro bytes más largos.

Si no comprende la primera expresión regular, permítame remitirlo a mi respuesta SO sobre el equilibrio de grupos . Como se garantiza que la entrada esté entre paréntesis correctamente, podemos guardar dos bytes haciendo coincidir )con en .lugar de \). Luego simplemente hacemos coincidir el resto de la cadena con (.*). $4 $1primero escribe dicho resto de la cadena (omitiendo los paréntesis y su contenido), y luego el contenido de los paréntesis después de un espacio. El +`le dice a Retina que repita este paso hasta que la cadena deje de cambiar (lo que solo sucede una vez que se han eliminado todos los paréntesis).

Los paréntesis vacíos darán como resultado dos espacios consecutivos, por lo que finalmente dividimos la cadena completa en espacios ( S`activa el modo de división y la expresión regular es un solo espacio). La _opción le dice a Retina que omita las partes vacías de la división, por lo que no incluimos los resultados vacíos en la salida.

Martin Ender
fuente
3

Lisp común, 160

(lambda(x)(labels((g(l)(cons(#1=format()"~(~{~A~}~)"(#2=remove-if'listp l))(mapcan #'g(#2#'atom l)))))(remove""(g(read-from-string(#1#()"(~A)"x))):test'equal))))

Esto podría ser cuatro bytes menos si la conversión de mayúsculas y minúsculas no fuera necesaria. La idea es agregar paréntesis izquierdo y derecho a cada lado de la cadena de entrada, tratarlo como una lista, escribir los elementos de nivel superior de la lista en una cadena y luego procesar las sublistas de la misma manera.

Joshua Taylor
fuente
2

Haskell, 114 112 111 bytes

')'%(h:i:t)=("":i):t++[h]
'('%l=last l:init l
c%((h:i):t)=((c:h):i):t
g x=[a|a<-id=<<foldr(%)(x>>[[""]])x,a>""]

Ejemplo de uso: g "ab(c(((d)ef()g)h()(i)j)kl)()"-> ["ab","ckl","hj","efg","i","d"].

Voy hacia atrás a través de la cadena de entrada. La estructura de datos intermedios es una lista de la lista de cadenas. La lista externa es por nivel y la lista interna es por grupo dentro de un nivel, por ejemplo [["ab"],["ckl"],["hj"],["efg","i"],["d"]](nota: la lista real tiene muchas cadenas vacías intermedias). Todo comienza con una serie de cadenas vacías iguales a la longitud de la entrada, más que suficiente, pero las listas vacías se filtran de todos modos. Las listas de exteriores, bien en gira (/ )o añade el carácter de elemento frontal. )También comienza un nuevo grupo.

Editar: @Zgarb ha encontrado un byte para guardar.

nimi
fuente
1

Sed, 90 bytes

:
s/^(\w*)\((.*)\n?(.*)/\1\n\3_\2/M
s/(\n\w*_)(\w*)\)(.*)/\3\1\2/M
t
s/[_\n]+/,/g
s/,$//

Utiliza expresiones regulares extendidas ( -rbandera), representadas por +1 byte. Además, esto usa una extensión GNU (la Mbandera en el scomando).

Uso de muestra:

$ echo 'ab(c(((d)ef()g)h()(i)j)kl)()' | sed -r -f deparenthesize.sed
ab,ckl,hj,efg,i,d

Explicación: Dado que sed no admite cosas como expresiones regulares recursivas, se requiere trabajo manual. La expresión se divide en varias líneas, cada una de las cuales representa un nivel de profundidad de anidamiento. Las expresiones individuales en la misma profundidad (y por lo tanto en la misma línea) están separadas por un _. El script funciona a través de la cadena de entrada un paréntesis a la vez. La entrada restante siempre se mantiene al final de la línea que corresponde al nivel de anidamiento actual.

matz
fuente
0

Python, 161 bytes

Esto es lo que se me ocurrió, una solución python funcional de una línea:

p=lambda s:filter(None,sum([''.join([s[i]for i in range(len(s))if s[:i+1].count('(')-s[:i+1].count(')')==d and s[i]!=')']).split('(')for d in range(len(s))],[]))

Este desafío se inspiró en https://github.com/samcoppini/Definition-book , que genera una cadena larga con una palabra definida entre paréntesis. Quería escribir un código que me diera cada oración, sin paréntesis. La solución funcional es demasiado lenta para ser efectiva en cadenas largas, pero las soluciones imperativas (como la solución de @ Quuxplusone) son mucho más rápidas.

Redstonerodent
fuente