Suportes normais ( (), [], <>e {}) são agradáveis e inequívoca, no entanto alguém pensou que seria uma boa idéia usar caracteres não suporte como suportes. Esses caracteres |e "são ambíguos. Por exemplo,

""""

Corresponde a

(())

ou

()()

É impossível dizer.

As coisas começam a ficar interessantes quando você mistura tipos de colchetes ambíguos, por exemplo

"|""||""|"

Pode ser um dos seguintes

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

Tarefa

Sua tarefa é pegar uma sequência de caracteres ambíguos e gerar todas as sequências equilibradas possíveis que o autor poderia ter pretendido.

Mais concretamente, você produz todas as cordas balanceadas que podem ser feitas substituindo |por um [ou outro ]e "por um (ou outro ). Você não deve emitir nenhuma string balanceada duas vezes.

IO

Como entrada, você deve usar uma string composta por |e ". Se você gostaria de selecionar outros de dois personagens distintos |e "para servir como substitutos você pode fazê-lo. Você deve produzir um contêiner de cadeias equilibradas. Você pode optar por substituir []e ()na saída com outros dois pares de suporte ( (), [], <>ou {}) que você deseja. Seu formato de saída deve ser consistente entre as execuções.

Pontuação

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

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

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

Experimente online!

Espera entrada como em 2002vez de "||", e entre aspas.

Repete todas as 2 ^N atribuições possíveis de "aberto" e "fechado" para a sequência, criando sequências ccomo:

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

Se eval-ing esta sequência de caracteres lança uma exceção, é incomparável. Caso contrário, imprimimos c[::2], dando:

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

Retina , 59 56 55 bytes

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

A`_

Experimente online! Infelizmente, o teste para dois conjuntos de colchetes correspondentes excede a capacidade de golfe de um único regex .NET, portanto, ele economiza 15 bytes para verificação manual. Editar: Salvo 3 4 bytes graças a @ H.PWiz. Explicação:

0`"
<$%">

Encontre ae "faça duas cópias da linha, uma com a <e outra com a >. Faça isso de "cada vez, para que cada" dobre o número de linhas.

}0`'
{$%"}

Da mesma forma com ', {e }. Então, mantenha substituindo até que todos os "s e' todas as cópias tenham sido substituídos.

.+
$&_$&

Faça uma duplicata dos colchetes, separados por um _ .

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

Na duplicata, exclua repetidamente os colchetes correspondentes, até não sobrar nenhum; nesse caso, exclua _também.

A`_

Exclua todas as linhas que ainda possuem a _.

Retina , 74 71 70 bytes

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

Experimente online! Explicação: Os dois primeiros estágios são os descritos acima. O terceiro estágio imprime diretamente o resultado da correspondência de dois conjuntos de colchetes correspondentes. Isso usa grupos de balanceamento do .NET. Em cada estágio da partida, o regex tenta combinar um caractere, depois procura um par de colchetes correspondentes e depois verifica se a parte superior da pilha corresponde ao colchete aberto. Se isso puder ser feito, significa que o suporte se equilibra e o suporte aberto é retirado da pilha. Caso contrário, a suposição é que estamos em um colchete aberto que precisa ser empurrado para a pilha. Se essas suposições não se mantiverem, a pilha não ficará vazia no final e a partida falhará.

Abordagem alternativa, também 74 71 bytes:

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

Aqui, olhamos à frente para <... >ou {... }, depois olhamos para trás para empurrar o suporte de fechamento para a pilha. Caso contrário, precisamos corresponder e colocar o colchete de fechamento que capturamos anteriormente. Nesta versão, o regex pode até não chegar ao final da string, mas algumas strings como as <<<>que passam pela rede se não verificássemos uma pilha vazia.

Casca , 19 bytes

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

Experimente online! Usa os caracteres dsna entrada e os pares de colchetes correspondentes dee stna saída.

Explicação

A idéia é gerar todos os suportes possíveis da entrada e manter aqueles que se reduzem à cadeia vazia quando removemos repetidamente os colchetes adjacentes. A ¨÷₂¨é uma sequência compactada que se expande para a "dest"qual foi escolhida porque possui uma forma compactada curta e consiste em pares de caracteres com pontos de código adjacentes. Assim, o programa é equivalente ao seguinte.

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

Inclui +1paran

usa [para []e {para{}

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

Gera todas as possibilidades de 2 ^ N e usa perl evalpara verificar se uma string como '+ [+ {}]' é um código válido e, se assim for, remove o +e imprime o resultado

APL (Dyalog Classic) , 55 53 bytes

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

Experimente online!

Limpo , 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]

Experimente online!

Usa apenas correspondência e compreensão de padrões.

Perl, 56 bytes

Inclui +paran

Usa entrada [para saída [ou]

Usa entrada {para saída {ou}

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

Usa uma expressão regular perl estendida para combinar chaves, acompanhando as escolhas feitas durante o retorno. Isso pode ser muito mais eficiente do que gerar todos os candidatos 2 ^ N, já que ele já rejeita muitas atribuições impossíveis enquanto está no meio da string 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}

Embelezado

    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
    }

Teste

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")
        }
    }

Editar% s

• -4 jrtapsell - predicado de verificação retrabalhado
• -2 jrtapsell - true-> 1>0e == 0->< 1

C (gcc) , 315 bytes

• Obrigado ao 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);}

Experimente online!

C (gcc) , 334 bytes (versão antiga)

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);}

Experimente online!

Explicação (versão antiga)

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

Experimente online!