Wyważanie wspornika

20

Otrzymasz (ewentualnie pusty) ciąg zawierający nawiasy kwadratowe ( [{()}]) i wszelkie inne znaki ( A- Z, a- z, 0- 9, interpunkcja). Musisz sprawdzić, czy przestrzega następujących zasad:

  • Znaki bez nawiasów są ignorowane.
  • Każdy otwarty wspornik [{(ma zamykający wspornik )}]. Więc [](nie jest dozwolone.
  • Wsporniki są prawidłowo zagnieżdżone. [(])nie jest dozwolone.
  • Nawiasy klamrowe nie mogą zawierać nawiasów kwadratowych. Proste nawiasy kwadratowe nie mogą zawierać nawiasów klamrowych ani kwadratowych. Tak [({})], [{[]}]i ({})nie są dozwolone. Nawiasy można zagnieżdżać za pomocą podobnych nawiasów, więc [[{((()))}{{(())}}]()]{()}jest to dozwolone.

Dane wyjściowe to jedna wartość true / falsey zgodnie z wyborem.

Najkrótszy kod wygrywa.


Przypadki testowe

b[[a{(/)}(())+={{}-}],] -> Ważne

([h][e][l][l][o]) -> Niepoprawny

[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Ważne

hi -> Ważne

ghosts_in_the_code
źródło
2
Możliwy duplikat nawiasów niezbilansowanych Fix
FUZxxl
9
@FUZxxl To wygląda na znacznie trudniejsze wyzwanie. Wydaje mi się jednak, że gdzieś jest inny dupek.
Martin Ender,
@ MartinBüttner Tak, może. Dodałem kilka przypadków testowych. I czy znalazłeś duplikat, którego szukasz?
ghosts_in_the_code
1
@ MartinBüttner: To wyzwanie może być tym, o czym myślałeś.
Ilmari Karonen,
1
Myślę, że powinniśmy zamknąć drugie pytanie jako duplikat tego; jest to lepsze, ponieważ ma mniej bonusów.
lirtosiast

Odpowiedzi:

5

Siatkówka , 84 bajty

^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

Wypróbuj online.

Jest to dość proste (ale grało w golfa) rozszerzenie podstawowego wyrażenia regularnego sprawdzania nawiasów .NET .

Chociaż jest to całkiem możliwe w przypadku grup równoważących, rekurencja Perla zdecydowanie ma tutaj przewagę . Jednak każde z tych podejść zostaje pokonane przez porzucenie elegancji pojedynczego dopasowania wyrażenia regularnego na rzecz stopniowego zmniejszania wkładu poprzez powtarzanie podstawień, jak robi sed odpowiedź Digital Trauma . Można to zaimplementować w 34 bajtach w Retinie, ale waham się, czy sam opublikować kod, ponieważ nie wpadłem na ten pomysł.

Martin Ender
źródło
5

Retina, 34

Po pierwsze, kredyt wymagalny:

Niezależnie (później) wymyśliłem to samo podejście w sed , więc mam nadzieję, że nie stąpam po palcach ( dużych lub innych), publikując to:

[^][(){}]

+`\(\)

+`{}

+`\[]

^$

Więc teraz z sudo apt-get install mono-completea git clone https://github.com/mbuettner/retina.gitmam działającą siatkówkę na mojej maszynie Wirtualnej Ubuntu. Oto wynik testu:

$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt 
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$ 
Cyfrowa trauma
źródło
@ThomasKwa Zobacz wyniki testu. Uważam, że kod jest poprawny i wszystkie testy wypadły pomyślnie. Czy w kodzie pojawił się konkretny problem, czy jakaś szczególna przypadek testowy, który Twoim zdaniem się nie powiedzie?
Cyfrowy uraz
@ThomasKwa Nie przeniosłem ich kodu, ponieważ nie mam pojęcia, co robi jakikolwiek ESMIN. Właśnie napisałem ten kod na podstawie tego, jak by to wyglądało , więc nie sądzę, aby istniał jakiś powód, dla którego powinien mieć ten sam błąd.
Martin Ender,
Wow, @ MartinBüttner, masz rację! Tak, myślałem, że rekurencyjne zastępowanie pasujących nawiasów na lewą stronę jest najbardziej logiczne. Szybkie dostosowanie do specyfikacji kodu sprawiło, że działało.
Mama Fun Roll
3

Sed, 53

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

Twierdzę tutaj, że skoro sedtak naprawdę nie ma pojęcia prawda / falsey, to definiuję pusty ciąg znaków jako prawdę, a wszystkie inne ciągi znaków oznacza falsey.

Jeśli jest to nie do przyjęcia, możemy dodać kilka wierszy, a zatem:

Sed, 66

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

Daje to 0 dla false i 1 dla true.

Cyfrowa trauma
źródło
Zobacz mój komentarz do odpowiedzi Molarmanfula na wersję Retina tego samego rozwiązania (34 bajty; drukowanie 0lub 1). Nie mogę powiedzieć, kto powinien to opublikować, ale prawdopodobnie powinna to być jedna z was.
Martin Ender
3

CJam, 27 26 bajtów

"(){}[]"q1$f&_,@2/e*{/s}/!

Drukuje 1 (truthy) lub 0 (falsy). Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe.

Jak to działa

"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.
Dennis
źródło
3

𝔼𝕊𝕄𝕚𝕟, 43 znaki / 62 bajty

!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

Try it here (Firefox only).

Nie.


Jeśli jednak użyję nowo zaimplementowanych funkcji, mogę uzyskać do 28 znaków / 47 bajtów:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”
Mama Fun Roll
źródło
Ohhh, czy usuwasz pasujące nawiasy od wewnątrz? To byłoby zaledwie 34 bajty w Retina: pastebin.com/bU77LzbR
Martin Ender
2

Japt , 42 37 bajtów

Zapisałem 5 bajtów z funkcją, o której nie wiedziałem, że mój własny język ... Dziękuję za dodanie go, @Downgoat!

Japt naprawdę potrzebuje lepszego wsparcia RegExp ...

!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

Wypróbuj online!

Jak to działa

               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression
ETHprodukcje
źródło
2

C99, 226 208 207 bajtów

To jest moja pierwsza gra w golfa

#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

Czytelny:

int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

Jest przepełnienie bufora, ale wydaje się, że nic to nie wpływa - uważam, że jest to spowodowane wyrównaniem.

dj0wns
źródło
1
Możesz pominąć to miejsce wchar* s
Cyoce
Nie wiedziałem, że - dzięki
dj0wns
1

Perl, 50 + 1 = 51 bajtów

$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

Wymaga -pflagi i wydruków 1dla prawdziwości i nic dla wyników fałszywych. Liczę -pjako jeden, ponieważ można go połączyć z -e:

> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

Kod jest po prostu zwykłym dopasowaniem wyrażenia regularnego względem danych wejściowych, za pomocą fajnej rekurencyjnej funkcji wyrażenia regularnego Perla.

Podziękowania dla Dennisa za pomoc w przetestowaniu tego i zagranie w golfa na płycie Perla.

Martin Ender
źródło
1

Python 3: 120 bajtów

Opierając się na odpowiedzi @ Adnana , okazało się, że jest on krótszy w użyciu:

import re
x=re.sub('[^[\](){}]','',input())  
for i in('()','{}','[]'):  
 while x.find(i)>=0:x=x.replace(i,'')  
print(x=='')
karhell
źródło
1

Python 3, 196 170 160 154 bajtów

Niezwykle długi, dzięki Mego za zaoszczędzenie 6 bajtów:

d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)
Adnan
źródło