Soportes normales ( (), [], <>y {}) son agradables y sin ambigüedades, sin embargo alguien pensó que sería una buena idea de utilizar caracteres no soporte como soportes. Estos personajes |y "son ambiguos. Por ejemplo hace

""""

corresponden a las

(())

o

()()

Es imposible de decir.

Las cosas comienzan a ponerse interesantes cuando mezclas tipos de paréntesis ambiguos, por ejemplo

"|""||""|"

Podría ser cualquiera de los siguientes

([(([]))]),([()[]()]),([()][()])

Tarea

Su tarea es tomar una cadena hecha de caracteres ambiguos y generar todas las cadenas equilibradas posibles que el autor podría haber pensado.

Más concretamente que todas las cadenas de salida equilibradas que se pueden hacer en sustitución |, ya sea con [o ]y ", ya sea con (o ). No debe generar ninguna cadena equilibrada dos veces.

IO

Como entrada, debe tomar una cadena que consta de |y ". Si desea seleccionar dos caracteres distintos además de |y "servir como reemplazos, puede hacerlo. Debe generar un contenedor de cadenas equilibradas. Usted puede optar por sustituir []y ()en la salida con otras dos pares de soportes ( (), [], <>o {}) que desee. Su formato de salida debe ser coherente en todas las ejecuciones.

Puntuación

Este es el código de golf, por lo que las respuestas se puntuarán en bytes con menos bytes mejor.

Casos de prueba

"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]    
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]    

Python 2 , 135 bytes

s=input()
for k in range(2**len(s)):
 try:c=''.join("[]() , ,"[int(c)|k>>i&1::4]for i,c in enumerate(s));eval(c);print c[::2]
 except:0

Pruébalo en línea!

Espera entradas como en 2002lugar de "||", y entre comillas.

Itera sobre las 2 ^N posibles asignaciones de "abrir" y "cerrar" a la cadena, creando cadenas ccomo:

"( [ ( ),],[ ( ),],),( ),"

Si eval-ing esta cadena arroja una excepción, no tiene comparación. Si no, imprimimos c[::2], dando:

([()][()])()

Retina , 59 56 55 bytes

0`"
<$%">
}0`'
{$%"}
.+
$&_$&
+m`^_|(<>|{})(?=.*_)

A`_

Pruébalo en línea! Desafortunadamente, las pruebas para dos conjuntos de paréntesis coincidentes exceden el nivel de golf de una única expresión regular .NET, por lo que ahorra 15 bytes para verificar manualmente. Editar: Guardado 3 4 bytes gracias a @ H.PWiz. Explicación:

0`"
<$%">

Encuentra ay "haz dos copias de la línea, una con a <y otra con a >. Haga esto uno "a la vez, para que cada uno "duplique el número de líneas.

}0`'
{$%"}

Lo mismo ocurre con ', {y }. Luego, siga reemplazando hasta que todos "los 'sys de todas las copias hayan sido reemplazados.

.+
$&_$&

Haga un duplicado de los corchetes, separados por a _.

+m`^_|(<>|{})(?=.*_)

En el duplicado, elimine repetidamente los corchetes coincidentes, hasta que no quede ninguno, en cuyo caso elimine _también.

A`_

Eliminar todas las líneas que todavía tienen un _.

Retina , 74 71 70 bytes

0`"
<$%">
}0`'
{$%"}
Lm`^(.(?<=(?=\3)(<.*>|{.*}))(?<-3>)|(.))+(?(3)_)$

Pruébalo en línea! Explicación: Las dos primeras etapas son como las anteriores. La tercera etapa imprime directamente el resultado de unir dos conjuntos de corchetes coincidentes. Esto utiliza los grupos de equilibrio de .NET. En cada etapa de la partida, la expresión regular intenta hacer coincidir un personaje, luego mirar hacia atrás para ver un par de paréntesis coincidentes, luego verificar que la parte superior de la pila coincida con el paréntesis abierto. Si puede hacer esto, significa que el soporte se equilibra y el soporte abierto se saca de la pila. De lo contrario, se supone que estamos en un paréntesis abierto que necesita ser empujado a la pila. Si estos supuestos no se cumplen, la pila no estará vacía al final y la coincidencia fallará.

Enfoque alternativo, también 74 71 bytes:

Lm`^((?=(<.*>|{.*})(?<=(.))).|\3(?<-3>))+(?(3)_)$

Aquí, miramos hacia adelante para <... >o {... }, luego miramos hacia atrás para empujar el soporte de cierre hacia la pila. De lo contrario, debemos hacer coincidir y abrir el corchete de cierre que capturamos anteriormente. En esta versión, es posible que la expresión regular ni siquiera llegue al final de la cadena, pero algunas cadenas <<<>se deslizarían a través de la red si no verificamos si hay una pila vacía.

Casco , 19 bytes

fo¬ω`ḞoΣx½¨÷₂¨ΠmSe→

Pruébalo en línea! Utiliza los caracteres dsen la entrada y los pares de paréntesis correspondientes dey sten la salida.

Explicación

La idea es generar todos los corchetes posibles de la entrada y mantener aquellos que se reducen a la cadena vacía cuando eliminamos repetidamente los corchetes adyacentes. El ¨÷₂¨es una cadena comprimida que se expande en "dest", que fue elegida porque tiene una forma comprimida corta y consiste en pares de caracteres con puntos de código adyacentes. Por lo tanto, el programa es equivalente a lo siguiente.

fo¬ω`ḞoΣx½"dest"ΠmSe→  Implicit input, say "ddssdd".
                 m     Map over the string:
                  Se    pair character with
                    →   its successor.
                       Result: ["de","de","st","st","de","de"]
                Π      Cartesian product: ["ddssdd","ddssde",..,"eettee"]
f                      Keep those strings that satisfy this:
                        Consider argument x = "ddsted".
   ω                    Iterate on x until fixed:
         ½"dest"         Split "dest" into two: ["de","st"]
    `Ḟ                   Thread through this list (call the element y):
        x                 Split x on occurrences of y,
      oΣ                  then concatenate.
                          This is done for both "de" and "st" in order.
                        Result is "dd".
 o¬                    Is it empty? No, so "ddsted" is not kept.
                      Result is ["destde","ddstee"], print implicitly on separate lines.

Perl, 56 55 53 bytes

Incluye +1paran

usos [para []y {para{}

perl -nE 's%.%"#1$&,+\\$&}"^Xm.v6%eg;eval&&y/+//d+say for< $_>' <<< "[{[[{{[[{["

Genera todas las posibilidades de 2 ^ N, luego usa perl evalpara verificar si una cadena como '+ [+ {}]' es un código válido y, de ser así, elimina +e imprime el resultado

APL (Dyalog Classic) , 55 53 bytes

{a/⍨~×≢¨'\(\)|\[]'⎕r''⍣≡a←⊃∘'()[]'¨¨(⊂'".'⍳⍵)+,⍳2⊣¨⍵}

Pruébalo en línea!

Limpio , 203 186 179 bytes

?['(':l][')':t]= ?l t
?['[':l][']':t]= ?l t
?l[h:t]= ?[h:l]t
?[][]=True
?_ _=False
@['"']=[['('],[')']]
@['|']=[['['],[']']]
@[h:t]=[[p:s]\\[p]<- @[h],s<- @t]
$s=[k\\k<- @s| ?[]k]

Pruébalo en línea!

Utiliza solo la coincidencia de patrones y las comprensiones.

Perl, 56 bytes

Incluye +paran

Utiliza entrada [para salida [o]

Utiliza entrada {para salida {o}

perl -nE '/^((.)(?{$^R.$2})(?1)*\2(?{$^R.=$2^v6}))*$(?{say$^R})^/' <<< "[{[[{{[[{["

Utiliza una expresión regular extendida de Perl para hacer coincidir los aparatos ortopédicos mientras realiza un seguimiento de las elecciones realizadas durante el retroceso. Esto puede ser mucho más eficiente que generar todos los candidatos 2 ^ N, ya que ya rechaza muchas tareas imposibles mientras se encuentra en la mitad de la cadena de entrada.

Kotlin , 240 236 234 bytes

fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

Embellecido

    fold(listOf("")) {r,c ->
        r.flatMap {i-> when(c) {
            '"'-> "()".map {i+it}
            else -> "[]".map {i+it}
        }}
    }.filter {
        val d = ArrayList<Char>()
        it.all {
            fun f(c:Any)=d.size>1&&d.removeAt(0)==c
            when(it) {
                ')' -> f('(')
                ']' -> f('[')
                else -> {d.add(0,it);1>0}
            }
        } && d.size<1
    }

Prueba

private fun String.f(): List<String> =
fold(listOf("")){r,c->r.flatMap{i->when(c){'"'->"()".map{i+it}
else->"[]".map{i+it}}}}.filter{val d=ArrayList<Char>()
it.all{fun f(c:Any)=d.size>1&&d.removeAt(0)==c
when(it){')'->f('(')
']'->f('[')
else->{d.add(0,it);1>0}}}&&d.size<1}

data class Test(val input: String, val outputs: List<String>)

val tests = listOf(
    Test("""""""", listOf("()")),
    Test(""""|"|""", listOf()),
    Test("""|||""", listOf()),
    Test("""""""""", listOf("(())","()()")),
    Test("""""||""", listOf("()[]")),
    Test(""""|"||"|"""", listOf("([([])])")),
    Test(""""|""||""|"""", listOf("([(([]))])","([()[]()])","([()][()])"))
)

fun main(args: Array<String>) {
    for ((input, output) in tests) {
        val actual = input.f().sorted()
        val expected = output.sorted()
        if (actual != expected) {
            throw AssertionError("Wrong answer: $input -> $actual | $expected")
        }
    }

Ediciones

• -4 jrtapsell : predicado de comprobación reelaborado
• -2 jrtapsell - true-> 1>0y == 0->< 1

C (gcc) , 315 bytes

• Gracias a ceilingcat por 19 bytes.

j,b;B(char*S){char*s=calloc(strlen(S)+2,b=1)+1;for(j=0;S[j];b*=(S[j]<62||*--s==60)*(S[j++]-41||*--s==40))S[j]==60?*s++=60:0,S[j]<41?*s++=40:0;return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n<strlen(S))for(k=2;k--;)S[n]==46-k-k?S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k:0;else B(S)&&puts(S);}F(int*S){f(S,0);}

Pruébalo en línea!

C (gcc) , 334 bytes (versión anterior)

j,b;B(char*S){char*s=calloc(strlen(S)+2,1)+1;for(b=1,j=0;S[j];j++){if(S[j]==60)*s++=60;if(S[j]<41)*s++=40;b*=!(S[j]>61&&*--s!=60)*!(S[j]==41&&*--s!=40);}return*s>0&*--s<1&b;}f(S,n,k)char*S;{if(n>=strlen(S))return B(S)&&puts(S);for(k=0;k<2;k++)S[n]==46-k-k&&(S[n]=40+k*20,f(S,n+1),S[n]=41+k*21,f(S,-~n),S[n]=46-k-k);}F(char*S){f(S,0);}

Pruébalo en línea!

Explicación (versión anterior)

j,b;B(char*S){                   // determine if string is balanced
 char*s=calloc(strlen(S)+2,1)+1; // array to store matching brackets
 for(b=1,j=0;S[j];j++){          // loop through string (character array)
  if(S[j]==60)*s++=60;           // 60 == '<', opening bracket
  if(S[j]<41)*s++=40;            // 40 == '(', opening bracket
  b*=!(S[j]>61&&*--s!=60)*       // 62 == '>', closing bracket
   !(S[j]==41&&*--s!=40);}       // 41 == ')', closing bracket
 return*s>0&*--s<1&b;}           // no unmatched brackets and no brackets left to match
f(S,n,k)char*S;{                 // helper function, recursively guesses brackets
 if(n>=strlen(S))                // string replaced by possible bracket layout
  return B(S)&&puts(S);          // print if balanced, return in all cases
 for(k=0;k<2;k++)                // 46 == '.', guess 40 == '(',
  S[n]==46-k-k&&(S[n]=40+k*20,   //  guess 41 == '(', restore
   f(S,n+1),S[n]=41+k*21,        // 44 == ',', guess 60 == '<',
   f(S,-~n),S[n]=46-k-k);}       //  guess 62 == '>', restore
F(char*S){f(S,0);}               // main function, call helper function

Pruébalo en línea!