Bracket-Ausgleich

20

Sie erhalten eine (möglicherweise leere) Zeichenfolge mit Klammern ( [{()}]) und anderen Zeichen ( A- Z, a- z, 0- 9, Interpunktion). Sie müssen überprüfen, ob die folgenden Regeln eingehalten werden:

  • Nicht in Klammern gesetzte Zeichen werden ignoriert.
  • Jede offene Klammer [{(hat eine schließende Klammer )}]. Ist [](also nicht erlaubt.
  • Klammern sind richtig verschachtelt. [(])ist nicht erlaubt.
  • Geschweifte Klammern dürfen keine eckigen Klammern enthalten. Einfache Klammern dürfen keine geschweiften oder eckigen Klammern enthalten. Also [({})], [{[]}]und ({})sind nicht erlaubt. Klammern können mit ähnlichen Klammern verschachtelt werden, dies [[{((()))}{{(())}}]()]{()}ist also zulässig.

Die Ausgabe ist ein einzelner Wahrheits- / Falsch-Wert gemäß Ihrer Wahl.

Kürzester Code gewinnt.


Testfälle

b[[a{(/)}(())+={{}-}],] -> Gültig

([h][e][l][l][o]) -> Ungültig

[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Gültig

hi -> Gültig

ghosts_in_the_code
quelle
2
Mögliches Duplikat von Fix unsymmetrischen Klammern
FUZxxl
9
@FUZxxl Das sieht nach einer viel härteren Herausforderung aus. Ich habe das Gefühl, dass es irgendwo einen anderen Trottel gibt.
Martin Ender
@ MartinBüttner Ja, das kann es. Ich habe einige Testfälle hinzugefügt. Und haben Sie das gesuchte Duplikat gefunden?
ghosts_in_the_code
1
@ MartinBüttner: An diese Herausforderung haben Sie vielleicht gedacht.
Ilmari Karonen
1
Ich denke, wir sollten die andere Frage als ein Duplikat davon schließen. Das ist besser, weil es weniger Boni hat.
Lirtosiast

Antworten:

5

Retina , 84 Bytes

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

Probieren Sie es online aus.

Dies ist eine recht unkomplizierte (aber gelungene) Erweiterung des regulären .NET- Ausdrucks, der in Klammern überprüft wird .

Während dies mit Bilanzgruppen durchaus möglich ist, hat Perls Rekursion hier definitiv den Vorteil . Bei beiden Ansätzen wird jedoch die Eleganz eines einzelnen Regex-Matches aufgegeben, um die Eingabe durch wiederholte Ersetzungen schrittweise zu reduzieren, wie dies die sed-Antwort von Digital Trauma tut . Dies kann in Retina in 34 Bytes implementiert werden, aber ich zögere, den Code selbst zu posten, da ich nicht auf die Idee gekommen bin.

Martin Ender
quelle
5

Retina, 34

Erstens Kredit, bei dem Kredit fällig ist:

Ich bin unabhängig (später) auf den gleichen Ansatz in sed gekommen , also hoffe ich, dass ich nicht auf Zehen tritt ( groß oder anders), indem ich Folgendes poste :

[^][(){}]

+`\(\)

+`{}

+`\[]

^$

Also jetzt mit sudo apt-get install mono-completeund git clone https://github.com/mbuettner/retina.gitich habe eine funktionierende Netzhaut auf meiner Ubuntu VM. Hier ist die Testausgabe:

$ 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
$ 
Digitales Trauma
quelle
@ThomasKwa Siehe Testausgabe. Ich glaube, der Code ist korrekt und alle Testfälle bestehen. Gab es ein bestimmtes Problem im Code oder einen bestimmten Testfall, von dem Sie glauben, dass er fehlschlagen wird?
Digitales Trauma
@ThomasKwa Ich habe ihren Code nicht portiert, weil ich keine Ahnung habe, was ein Teil von ESMIN tut. Ich habe diesen Code nur auf der Grundlage dessen geschrieben, wie er aussehen würde. Ich glaube also nicht, dass es einen Grund dafür gibt, warum dies der gleiche Fehler sein sollte.
Martin Ender
Wow, @ MartinBüttner, du hast es richtig gemacht! Ja, ich fand es am logischsten, die passenden Klammern rekursiv von innen nach außen zu ersetzen. Eine schnelle Anpassung an die Codespezifikationen hat funktioniert.
Mama Fun Roll
3

Sed, 53

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

Hier behaupte ich, dass da sednicht wirklich ein Konzept von Wahrhaftigkeit / Falschheit existiert, dann definiere ich die leere Zeichenkette als Wahrhaftigkeit und alle anderen Zeichenketten als Falschheit.

Wenn das nicht akzeptabel ist, können wir ein paar Zeilen hinzufügen, also:

Sed, 66

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

Dies gibt 0 für falsch und 1 für wahr aus.

Digitales Trauma
quelle
Siehe meinen Kommentar zur Antwort von molarmanful für die Retina-Version der exakt gleichen Lösung (bei 34 Bytes; Drucken 0oder 1). Ich kann nicht sagen, wer es posten soll, aber es sollte wahrscheinlich einer von euch beiden sein.
Martin Ender
3

CJam, 27 26 Bytes

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

Dies gibt 1 (wahr) oder 0 (falsch) aus. Probieren Sie es online! oder überprüfen Sie alle Testfälle.

Wie es funktioniert

"(){}[]"                    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
quelle
3

𝔼𝕊𝕄𝕚𝕟 43 Zeichen / 62 Bytes

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

Try it here (Firefox only).

Nee.


Wenn ich jedoch neu implementierte Funktionen verwende, kann ich bis zu 28 Zeichen / 47 Byte reduzieren:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”
Mama Fun Roll
quelle
Ohhh, entfernen Sie die passenden Klammern von innen nach außen? Das wären nur 34 Bytes in Retina: pastebin.com/bU77LzbR
Martin Ender
2

Japt , 42 37 Bytes

5 Bytes mit einer Funktion gespeichert, die ich nicht erkannt habe ... Vielen Dank für das Hinzufügen, @Downgoat!

Japt braucht wirklich bessere RegExp-Unterstützung ...

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

Probieren Sie es online!

Wie es funktioniert

               // 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
ETHproductions
quelle
2

C99, 226 208 207 Bytes

Ich versuche zum ersten Mal etwas Golf zu spielen

#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['(']);}

Lesbar:

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['(']);
}

Es gibt einen Pufferüberlauf, aber er scheint nichts zu beeinflussen - ich glaube, das liegt an der Ausrichtung.

dj0wns
quelle
1
Sie können das Leerzeichen weglassen inchar* s
Cyoce
Wusste
1

Perl, 50 + 1 = 51 Bytes

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

Benötigt die -pFlagge und Drucke 1für die Wahrheit und nichts für falsche Ergebnisse. Ich zähle -pals eins, weil es mit kombiniert werden kann -e:

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

Der Code ist im Grunde genommen nur eine einfache Regex-Übereinstimmung mit der Eingabe, wobei die raffinierte rekursive Regex-Funktion von Perl verwendet wird.

Vielen Dank an Dennis, der mir geholfen hat, dies zu testen und das Perl-Boilerplate zu spielen.

Martin Ender
quelle
1

Python 3: 120 Bytes

Aufbauend auf der Antwort von @ Adnan erwies sich die Verwendung als kürzer:

import re
x=re.sub('[^[\](){}]','',input())  
for i in('()','{}','[]'):  
 while x.find(i)>=0:x=x.replace(i,'')  
print(x=='')
Karhell
quelle
1

Python 3, 196 170 160 154 Bytes

Umständlich lang, danke an Mego für die Einsparung von 6 Bytes:

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
quelle