Normalne wsporniki ( (), [], <>i {}) są ładne i jednoznaczne, jednak ktoś myślał, że będzie to dobry pomysł, aby wykorzystać znaki spoza Wspornik nawiasach. Te znaki, |i "są niejednoznaczne. Na przykład robi

""""

odpowiada

(())

lub

()()

Nie da się powiedzieć.

Na przykład zaczyna się robić ciekawie, gdy zmieszamy typy niejednoznacznych nawiasów kwadratowych

"|""||""|"

Może to być dowolny z poniższych

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

Zadanie

Twoim zadaniem jest pobranie ciągu złożonego z niejednoznacznych znaków i wygenerowanie wszystkich możliwych zrównoważonych ciągów, które autor mógł zamienić.

Mówiąc dokładniej, wyprowadzasz wszystkie zbalansowane ciągi, które można wykonać zamieniając na |jeden [lub na ]i na "jeden (lub ). Nie powinieneś wyprowadzać żadnego zbalansowanego ciągu dwa razy.

IO

Jako dane wejściowe powinieneś wziąć ciąg składający się z |i ". Jeśli chcesz wybrać dwa różne znaki inne niż |i "służyć jako zamienniki, możesz to zrobić. Powinieneś wyprowadzić kontener zrównoważonych ciągów. Możesz wybrać, aby zastąpić []i ()na wyjściu z dwoma innymi parami wspornik ( (), [], <>lub {}) chcesz. Twój format wyjściowy powinien być spójny między przebiegami.

Punktacja

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

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

Python 2 , 135 bajtów

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

Wypróbuj online!

Oczekuje danych wejściowych takich jak 2002zamiast "||"i zawiniętych w cudzysłów.

Iteruje wszystkie 2 ^N możliwych przypisań „open” i „close” do ciągu, tworząc ciągi ctakie jak:

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

Jeśli eval-ing ten ciąg zgłasza wyjątek, nie ma sobie równych. Jeśli nie, drukujemy c[::2], podając:

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

Retina , 59 56 55 bajtów

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

A`_

Wypróbuj online! Niestety testowanie dwóch zestawów dopasowanych nawiasów przekracza golfowość pojedynczego wyrażenia regularnego .NET, więc oszczędza 15 bajtów do ręcznego sprawdzania. Edycja: Zapisano 3 4 bajty dzięki @ H.PWiz. Wyjaśnienie:

0`"
<$%">

Znajdź a "i zrób dwie kopie linii, jedną z <a drugą z >. Zrób to pojedynczo ", aby każda z nich "podwoiła liczbę linii.

}0`'
{$%"}

Podobnie z ', {i }. Następnie kontynuuj wymianę, dopóki wszystkie "s i 's na wszystkich kopiach nie zostaną wymienione.

.+
$&_$&

Zrób duplikat nawiasów rozdzielonych znakiem _.

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

W duplikacie kilkakrotnie usuwaj dopasowane nawiasy, aż nie pozostaną żadne, w którym to przypadku również je usuń _.

A`_

Usuń wszystkie linie, które nadal mają _.

Retina , 74 71 70 bajtów

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

Wypróbuj online! Objaśnienie: Pierwsze dwa etapy są takie jak powyżej. Trzeci etap drukuje bezpośrednio wynik dopasowania dwóch zestawów dopasowanych nawiasów. Wykorzystuje grupy równoważące .NET. Na każdym etapie dopasowania wyrażenie regularne próbuje dopasować znak, a następnie spojrzeć wstecz na parę pasujących nawiasów, a następnie sprawdzić, czy góra stosu odpowiada otwartemu nawiasowi. Jeśli może to zrobić, oznacza to, że wspornik równoważy się, a otwarty wspornik wyskakuje ze stosu. W przeciwnym razie założymy, że mamy otwarty nawias, który należy zepchnąć na stos. Jeśli te założenia się nie sprawdzą, stos nie będzie pusty na końcu i dopasowanie się nie powiedzie.

Alternatywne podejście, także 74 71 bajtów:

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

Tutaj patrzymy w przyszłość albo <... >albo {... }, a następnie patrzymy w tył, aby przesunąć wspornik zamykający na stos. W przeciwnym razie musimy dopasować i przełamać nawias zamykający, który przechwyciliśmy wcześniej. W tej wersji wyrażenie regularne może nawet nie dojść do końca łańcucha, ale niektóre łańcuchy, takie jak np. <<<>Prześlizgnęłyby się przez sieć, gdybyśmy nie sprawdzili pustego stosu.

Łuska , 19 bajtów

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

Wypróbuj online! Wykorzystuje znaki dsna wejściu oraz odpowiednie pary nawiasów deist na wyjściu.

Wyjaśnienie

Chodzi o to, aby wygenerować wszystkie możliwe nawiasy klamrowe wejściowe i zachować te, które zmniejszają się do pustego ciągu, gdy wielokrotnie usuwamy sąsiednie nawiasy. ¨÷₂¨Jest sprężony znaków, który rozszerza się "dest", który został wybrany, ponieważ ma postać krótkiego sprężonego i składa się z par znaków z sąsiadującymi codepoints. Program jest więc równoważny z poniższym.

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 bajtów

Obejmuje +1dlan

zastosowania [dla []i {dla{}

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

Generuje wszystkie możliwości 2 ^ N, a następnie używa perla, evalaby sprawdzić, czy ciąg taki jak „+ [+ {}]” jest poprawnym kodem, a jeśli tak, usuwa +i drukuje wynik

APL (Dyalog Classic) , 55 53 bajtów

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

Wypróbuj online!

Czysty , 203 186 179 bajtów

?['(':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]

Wypróbuj online!

Wykorzystuje tylko dopasowanie wzorca i rozumienie.

Perl, 56 bajtów

Obejmuje +dlan

Wykorzystuje dane wejściowe [dla wyjścia [lub]

Wykorzystuje dane wejściowe {dla wyjścia {lub}

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

Używa rozszerzonego wyrażenia regularnego w Perlu, aby dopasować nawiasy klamrowe, jednocześnie śledząc wybory dokonane podczas cofania. Może to być o wiele bardziej wydajne niż generowanie wszystkich kandydatów 2 ^ N, ponieważ już odrzuca wiele niemożliwych przypisań podczas przechodzenia przez ciąg wejściowy

Kotlin , 240 236 234 bajtów

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}

Upiększony

    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
    }

Test

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

Edycje

• -4 jrtapsell - predykat sprawdzania
• -2 jrtapsell - true-> 1>0i == 0->< 1

C (gcc) , 315 bajtów

• Dzięki pułapowi cat na 19 bajtów.

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

Wypróbuj online!

C (gcc) , 334 bajty (stara wersja)

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

Wypróbuj online!

Objaśnienie (stara wersja)

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

Wypróbuj online!