Stimmen die Klammern vollständig überein?

56

Sie müssen ein Programm oder eine Funktion schreiben, die eine Reihe von Klammern verwendet und ausgibt, ob diese Zeichenfolge vollständig übereinstimmt oder nicht. Ihr Programm sollte einen echten oder falschen Wert ausgeben , und IO kann in jedem vernünftigen Format vorliegen .

Regeln und Definitionen:

  • Für die Zwecke dieser Herausforderung ist eine „Klammer“ eines dieser Zeichen: ()[]{}<>.

  • Ein Klammerpaar wird als "übereinstimmend" betrachtet, wenn die öffnende und schließende Klammer in der richtigen Reihenfolge sind und keine Zeichen enthalten, z

    ()
    []{}
    

    Oder wenn jedes Unterelement in ihm auch übereinstimmt.

    [()()()()]
    {<[]>}
    (()())
    

    Unterelemente können auch mehrere Ebenen tief verschachtelt sein.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Eine Zeichenfolge wird genau dann als "vollständig zugeordnet" betrachtet, wenn:

    1. Jedes einzelne Zeichen ist eine Klammer,

    2. Jedes Paar von Klammern hat die richtige öffnende und schließende Klammer in der richtigen Reihenfolge und

    3. Jede Klammer ist abgestimmt.

  • Sie können davon ausgehen, dass die Eingabe nur druckbares ASCII enthält .

Testen Sie IO

Hier sind einige Eingaben, die einen Wahrheitswert zurückgeben sollten:

()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]

Und hier sind einige Ausgaben, die einen falschen Wert zurückgeben sollten:

(               Has no closing ')'
}{              Wrong order
(<)>            Each pair contains only half of a matched element
(()()foobar)    Contains invalid characters
[({}<>)>        The last bracket should be ']' instead of '>'
(((()))         Has 4 opening brackets, but only 3 closing brackets.

Wie üblich ist dies Codegolf, daher gelten Standardlücken und die kürzeste Antwort in Bytes gewinnt.

DJMcMayhem
quelle
1
Verbunden.
Martin Ender
7
Hinweis für potenzielle enge Wähler: Die Herausforderung, die ich verknüpft habe, enthält auch eine Prioritätsreihenfolge für die Klammertypen, sodass sie nicht in einer willkürlichen Reihenfolge verschachtelt werden können. Ich denke das macht es ausreichend anders.
Martin Ender
Ist [}eine Übereinstimmung? Und wenn nicht, wo wird es durch diese Regeln ausgeschlossen?
user207421
2
@EJP Nein, das ist es nicht. Each pair of brackets has the correct opening and closing bracket and in the right order.
DJMcMayhem
6
Ich werde die erste Lösung in Klammern
Leo

Antworten:

17

05AB1E , 19 Bytes

Die Eingabe erfolgt in Anführungszeichen . Code:

"[](){}<>"2÷)"":g2Q

Naja Mist, viele Bugs und nicht implementierte Features wurden gefunden. Erläuterung:

"[](){}<>"           # Push this string
          2÷         # Split into pieces of two
            )        # Wrap it into an array (which should not be needed)
             ""      # Push an empty string
               :     # Infinite replacement

Das ist eigentlich ein kniffliger Teil. Wie das im Pseudocode aussieht, ist:

input().replace(['[]', '()', '{}', '<>'], "")

Dies wird von diesem Teil aus dem 05AB1E-Code abgedeckt :

if type(b) is list:
    temp_string = temp_string_2 = str(a)
    while True:
        for R in b:
            temp_string = temp_string.replace(R, c)
        if temp_string == temp_string_2:
            break
        else:
            temp_string_2 = temp_string
    stack.append(temp_string)

Wie Sie sehen, ist dies eine unendliche Ersetzung (solange, bis sich die Zeichenfolge nicht mehr ändert). Ich muss mich also nicht darum kümmern, die Ersetzung in eine Schleife zu setzen, da dies bereits eingebaut ist. Nachdem:

                g    # Take the length of the final string
                 2Q  # Check if equal with 2 (which are the quotes at the end)

Verwendet die CP-1252- Codierung. Probieren Sie es online! (geringfügig geändert, da die obige Version veraltet ist).

Adnan
quelle
1
Schön golfen!
SamyQc
1
Wurde dies vorher õhinzugefügt?
Zacharý
@ Zacharý Ja, das ist richtig
Adnan
33

Brain-Flak , 1101, 1085 , 981 Bytes

{(<(({}))((((()()()()()){}){}){})({}[{}]<(())>){((<{}{}>))}{}>{({}<>)(<>)}{}<(({
}))((((()()()()()){}){}){}())({}[{}]<(())>){((<{}{}>))}{}>{({}<>)({}[{}](<()>)){
{}{}(<(())>)}{}{<>{{}}<>{{}}((<()>))}{}(<>)}{}<(({}))(((((()()()()()){}){})){}{}
)({}[{}]<(())>){((<{}{}>))}{}>{<({}()<>)>()(<>)}{}<(({}))(((((()()()()()){}){})(
)){}{})({}[{}]<(())>){((<{}{}>))}{}>{<({}()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{
<>{{}}<>{{}}((<()>))}{}(<>)}{}<(({}))((((()()()){}){}()){({}[()])}{})({}[{}]<(()
)>){((<{}{}>))}{}>{<({}()()<>)>()(<>)}{}<(({}))((((((()()()()()){})){}{}())){}{}
)({}[{}]<(())>){((<{}{}>))}{}>{<({}()()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{<>{{
}}<>{{}}((<()>))}{}(<>)}{}<(({}))((((((()()()()()){}){}){}())){}{})({}[{}]<(())>
){((<{}{}>))}{}>{<({}()()()<>)>()(<>)}{}<(({}))((((((()()()()()){}){}){}())()){}
{})({}[{}]<(())>){((<{}{}>))}{}>{<({}()()()<>)>()({}[{}](<()>)){{}{}(<(())>)}{}{
<>{{}}<>{{}}((<()>))}{}(<>)}{}<{}>[()]){<>{{}}(<()>)<>{{}}(<()>)}{}}<>([]<>)({}<
(())>){((<{}{}>))}{}

Probieren Sie es online!

Dies sind 980 Byte Quellcode und +1für das -aFlag, das ASCII-Eingabe (aber Dezimalausgabe) zulässt.

Dies ist eine Antwort, die ich schon sehr lange schreiben wollte . Mindestens 6 Monate. Ich habe darauf gewartet, dies zu posten, weil ich wusste, dass die Beantwortung dieser Herausforderung in der Gehirnflocke besonders schwierig sein würde. Aber es lohnt sich aus einem sehr wichtigen Grund: Der Quellcode selbst ist eine wahrheitsgemäße Eingabe, die den gesamten Sinn dieser Sprache ausmacht.

Und als ich schrieb hier , war diese Frage , was mich inspiriert Gehirn-Flakfeuer zu schreiben.

Kurz nachdem ich geschrieben habe, ob die Klammern vollständig übereinstimmen, habe ich mich gefragt, wie viele Informationen Sie nur mit übereinstimmenden Klammern speichern können. Eine Sache, die mir aufgefallen ist, war, dass Sie nur 4 "Atome" haben:

(){}[]<>

Sie haben wirklich 8 Informationseinheiten zu übermitteln, da jeder dieser Klammertypen leer sein kann oder andere Klammern dazwischen haben kann, die grundlegend unterschiedliche Informationen sind. Also habe ich beschlossen, eine Sprache zu schreiben, die nur übereinstimmende Klammern zulässt und in der leere Klammern etwas anderes als Klammern mit anderen Klammern enthalten.

Das Schreiben dieser Antwort dauerte ungefähr zwei Stunden. Ich gebe zu, es ist ziemlich schlecht golfen, vor allem, weil ein Großteil des Codes für jeden Bracket-Typ wiederholt wird. Aber ich bin größtenteils erstaunt, dass ich überhaupt eine Antwort schreiben konnte, vor allem angesichts der Tatsache, dass es Brain-Flak ist

Ein minimalistischer Esolang, dessen Gebrauch schmerzhaft ist

Ich werde versuchen, es später abzuspielen, aber ich wollte es trotzdem rausbringen.

Ich habe eine ausführliche Erklärung, aber es ist ungefähr 6000 Zeichen lang, daher halte ich es für nicht ratsam, das Ganze in diese Antwort einzufügen. Sie können es hier nachlesen , wenn Sie möchten. Ich werde hier eine kürzere Erklärung hinzufügen.

Die Grundidee ist, dass wir die folgenden Schritte für jedes Zeichen auf dem Stapel wiederholen:

  • Wir überprüfen jedes Zeichen, um festzustellen, ob es zu einer Klammer passt. Wenn es sich um eine öffnende Klammer handelt, schieben wir eine Zahl gemäß der folgenden Zuordnung auf den anderen Stapel:

    ( = 1
    < = 2
    [ = 3
    { = 4
    
  • Dann prüfen wir, ob es zu einer schließenden Klammer passt. In diesem Fall legen wir die entsprechende Zahl auf den alternativen Stapel, genau wie beim Öffnen von Klammern. Dann prüfen wir, ob die beiden oberen Zahlen gleich sind. Wenn dies der Fall ist, werden beide geknackt und das Programm wird normal fortgesetzt. Wenn dies nicht der Fall ist, löschen wir beide Stapel (um die Schleife zu beenden) und schieben einen auf den alternativen Stapel. Dies ist im Wesentlichen eine "break" -Anweisung.

  • Nachdem wir die 8 Klammertypen überprüft haben, schieben wir den Wert dieses Laufs durch die Schleife. Da wir das meiste herausfinden, sind die einzigen Ausschnitte, die irgendeinen Wert haben, die Bedingungen, wenn wir sie mit Klammern vergleichen. Wenn also eine Klammer übereinstimmt, hat die gesamte Schleife den Wert 1. Wenn keine übereinstimmt, hat die gesamte Schleife den Wert 0. In diesem Fall werden beide Stapel gelöscht und eine 0 auf den alternativen Stapel gelegt. Auch dies ist wie eine "break" -Anweisung.

Nachdem diese Hauptschleife ausgeführt wurde, ist der Rest ziemlich einfach. Wir befinden uns auf dem (leeren) Hauptstapel, und der alternative Stapel ist leer (wenn die Klammern übereinstimmen) oder nicht leer, wenn sie nicht übereinstimmen. Also führen wir Folgendes aus:

#Toggle to the alternate stack
<>

#Push this stack-height onto main-stack
([]<>)

#Logical not
({}<(())>){((<{}{}>))}{}

Dies drückt eine 0 oder eine 1 auf den Hauptstapel und wenn das Programm endet, wird es implizit gedruckt.


  • Vielen Dank an @WheatWizard für die Erstellung eines guten Stack-Clean-Snippets "equals" und "logical not" und für die regelmäßige Aktualisierung des Github-Wikis mit nützlichen Beispielen.

  • Dank an @ ASCII-only für das Schreiben eines Online- Ganzzahl-Metagolfers, der beim Schreiben dieses Programms ungemein hilfreich war


Überarbeitungen

  • Einige Push-Pop-Redundanzen wurden entfernt

  • Änderte meine Nullzählerlogik

DJMcMayhem
quelle
1
Awwwwwweeeeesommmmeeeee!
Arjun
23

Brain-Flak , 204 196 190 Bytes

{({}<>)<>((((()()()()()){})(({}){})())({}(({})((({}){})(<()>))))())(({<({}<>[({})])>[()]{()(<{}>)}{}<>}{}()<({}<>[({})]){(<{}({}())>)}{}<>>)){(<({}{}<>[{}]{}<>)>)}{}{<>{{}}}{}}<>((){[()]<>})

Probieren Sie es online!

-8 Bytes dank Weizen-Assistent. -6 Bytes dank Jo King.

Erläuterung

Dieses Programm speichert die Zeichencodes aller aktuellen nicht geschlossenen Klammern auf dem zweiten Stapel. Die Halterungspaar <>, []und {}haben jeweils Zeichencodes , die von genau 2 unterscheiden, so gibt es keine Notwendigkeit , die speziell für sie zu überprüfen. Das Paar ()unterscheidet sich nur um 1, daher überprüfen wir, ob es (spezifisch ist, und dekrementieren dieses Byte effektiv (inkrementieren tatsächlich jedes zweite Byte), bevor wir fortfahren.

# While there are bytes left to process
{

 # Move byte to second stack
 ({}<>)<>

 # Push 40, 0, 40, 60, 91, 123: (, then null, then all four opening brackets
 ((((()()()()()){})(({}){})())({}(({})((({}){})(<()>))))())

 ((

   # For each opening bracket type:
   {

    # Evaluate as zero
    <

     # Compute difference between bracket type and input byte
     ({}<>[({})])

    >

    # Evaluate loop iteration as -1 if equal, 0 otherwise
    [()]{()(<{}>)}{}<>

   }

   # Remove the 0 that was inserted to terminate that loop
   {}

   # Add 1 to result
   ()

   # Evaluate rest of this expression as zero
   <

    # Determine whether the byte is open parenthesis
    ({}<>[({})])

    # If not:
    {

     # Add 1 to byte and break if
     (<{}({}())>)

    }{}

    # Return to main stack
    <>

   >

 # Push result twice (0 if matched an opening bracket, 1 otherwise)
 ))

 # If byte was not an opening bracket:
 {

  # Push zero to break out of if
  (<

    # Push (open bracket + 2 - byte) below that zero
    ({}{}<>[{}]{}<>)

  >)

 }{}

 # If byte was neither an opening bracket nor the appropriate closing bracket:
 {

  # Clear alternate stack and stay there to break out of main loop early
  <>{{}}

 }{}

# End of main loop
}

# If a prefix was invalid, the top of the other stack is the same nonzero value
# that made us break out in the first place. If the string was a valid prefix,
# the other stack contains every unclosed bracket.  If the string is balanced,
# there are none of these. Thus, the other stack is empty if the
# brackets are balanced, and has a nonzero value on top otherwise.

# Push 1 on other stack if empty, and 0 on current stack otherwise
<>((){[()]<>})
Nitrodon
quelle
"Logical Not Of Difference" (auch als "Equals" bezeichnet) könnte kürzer sein als([{}]<>({}))((){[()](<{}>)}{})
Wheat Wizard
Ich denke, Sie können diese letzte Prüfung ({<>[()]}())durch -6 Bytes ersetzen
Jo King
Vielen Dank. Ich glaube nicht, dass ich das jemals bemerkt hätte.
Nitrodon
Ja, ich habe es in meiner eigenen Antwort herausgefunden und festgestellt, dass es auch auf deine zutrifft
Jo King,
13

JavaScript (ES6), 52 bis 50 Byte

f=s=>(t=s.replace(/\(\)|\[]|{}|<>/,''))==s?!s:f(t)

Entfernen Sie wiederholt Klammern, bis das Ergebnis mit dem Original übereinstimmt, und geben Sie dann false zurück, es sei denn, die Zeichenfolge ist jetzt leer.

Bearbeiten: 2 Bytes dank @ edc65 gespeichert.

Neil
quelle
11

CJam, 25 24 23 21 Bytes

Danke an Sp3000 für das Speichern von 2 Bytes.
Danke an jimmy23013 für das Speichern von 2 Bytes.

q_,{()<>}a`$2/*{/s}/!

Testsuite.

Arbeitet im Wesentlichen die gleiche wie die anderen Antworten: wir immer wieder zu entfernen (), [], <>und {}aus dem String und prüfen , ob wir mit dem leeren String enden. Um nicht zu prüfen, wann wir fertig sind, entfernen wir die Paare Nmal, wobei Ndie Länge der Zeichenfolge immer ausreicht (da bei jeder Iteration mindestens zwei Zeichen entfernt werden, es sei denn, wir sind fertig). Ich bin froh zu sehen, dass dies Retina nicht besiegt. :) (Obwohl Pyth oder Jelly vielleicht ...)

Hier gibt es einen lustigen Golftick: Um die Saite zu erhalten, verwenden ()<>[]{}wir Folgendes:

{()<>}a`$

Das, {()<>}ist nur ein Block (dh eine Funktion), der die anderen Klammern als Code enthält. Mit awickeln wir den Block in ein Array. Das `stringifiziert das Array, das gibt "[{()<>}]". Zuletzt sortieren wir die Zeichenkette mit $, wodurch die Klammern in neu angeordnet werden ()<>[]{}.

Martin Ender
quelle
Ich kenne Ihre Sprache nicht, aber Ihre Beschreibung Ihres Golftricks klingt ()<>[]{}`genauso gut und hat die gleiche Anzahl von Bytes, oder?
Mooing Duck
1
@MooingDuck Nein, da ()<>sind vier Operatoren (Dekrementieren, Inkrementieren und dann Vergleichen oder Abschneiden, abhängig von den Operanden), die sofort ausgeführt werden würden, wohingegen {}ein Block (CJams Äquivalent einer Funktion) bezeichnet wird, dh ein Stück Code, der gerade verschoben wird auf den Stapel, ohne ihn sofort auszuwerten. Das ist der Grund, warum ich {}das ()und umhüllen muss <>, aber dann ist die Verwendung azum Platzieren von allem in einem Array kürzer als [...].
Martin Ender
10

Python, 67 Bytes

lambda s:eval("s"+".replace('%s','')"*4%([],(),{},'<>')*len(s))==''

Erzeugt und bewertet einen Ausdruck, der aussieht

s.replace('[]','').replace('()','').replace('{}','').replace('<>','').replace('[]','').replace('()','').replace('{}','').replace('<>','')

und prüft, ob das Ergebnis leer ist.

Sp3000 sparte 8 Bytes, indem es darauf hinwies, dass [],(),{}es ohne Anführungszeichen eingebettet werden kann, da es sich um Python-Objekte handelt und zwei Parens nicht benötigt wurden.

xnor
quelle
8

Ja, 119 Bytes

Regex / Replace wird nicht verwendet.

%%input:r;r:%empty|'['r']'r|'{'r'}'r|'('r')'r|'<'r'>'r;%%yylex(){return getchar();}main(){return yyparse();}yyerror(){}

Ungolfed

%%                              # Grammar in BNF
input:
  r;
r:
  %empty
| '['r']'r
| '{'r'}'r
| '('r')'r
| '<'r'>'r;
%%                              # Minimal parser invocation and lexer
yylex(){return getchar();}
main(){return yyparse();}
yyerror(){}

Zusammenstellung

yacc -o bracket.c bracket.y
cc -o bracket bracket.c

Verwendungszweck

~/ % echo -n "<()[]>" | ./bracket
~/ %
~/ % echo -n "{" | ./bracket
~/ 1 %                                                                         :(
Rainer P.
quelle
7

Pyth, 31 25 24 Bytes

Dank FryAmTheEggMan auf 25 Byte reduziert 1 Byte entfernt

VQ=:Q"<>|\[]|{}|\(\)"k;!

Probieren Sie es hier aus: Test Suite !

Ich bin immer noch ein Pyth-Neuling, jede Hilfe wird geschätzt.

Erläuterung

VQ                         For N in range(0, len(z)), with Q being the evaluated input.
                           Optimal solution would be to use range(0, len(z)/2) instead, but it add two bytes.
  =:Q"<>|\[]|{}|\(\)"k     assign Q without {}, [], <> nor () (regex replacement) to Q
                      ;    End of For loop
                       !   Logical NOT of Q's length (Q is the input, but has gone several times through y, and Q is implicit).
                           This last operation returns True if len(Q) is 0 (which means all brackets were matched), False otherwise

Übrigens, herzlichen Glückwunsch zu der anderen Pyth-Antwort (die derzeit 20 Bytes ist)

FliiFe
quelle
Willkommen bei Programming Puzzles und Code Golf!
Adnan
@Adnan Danke! Dies ist mein erstes Golf!
FliiFe
Schönes erstes Golf! Mit etwas Neuanordnung und Sachen, können Sie bis 25 erhalten: Vz=:z"<>|\[]|{}|\(\)"k;!z. Insbesondere ist zu beachten, dass Sie im Grunde genommen nie verwenden müssen, lwenn Sie die Zahl nicht wirklich benötigen, und =die erste in einem Ausdruck verwendete Variable automatisch erraten. Lassen Sie mich wissen, wenn Sie möchten, dass ich im Pyth-Chatraum etwas anderes erkläre :)
FryAmTheEggman
@FryAmTheEggman Danke! Ich wusste nicht, dass les unnötig war, das ist gut zu wissen. Zuerst habe ich eine Funktion deklariert, weil meine Logik anders war, und vergessen, sie zu entfernen. Soll ich Ihre Antwort auf meine aufnehmen? (Ich bin ein Neuling>. <)
FliiFe
3
Wenn es in einem Kommentar gepostet wird, möchte der Autor, dass Sie es verwenden. Also mach weiter so! :)
FryAmTheEggman
6

Pyth, 20 Bytes

!uuscNTc"[](){}<>"2G

Probieren Sie es online aus: Test Suite

Wiederholt entfernt Vorkommen von [], (), <>und {}durch Aufspalten und Wiederzusammenführen. Überprüft, ob die resultierende Zeichenfolge leer ist oder nicht.

Jakube
quelle
4

Javascript ES6, 54 Bytes

f=_=>_.match(x=/\(\)|\[]|{}|<>/)?f(_.replace(x,'')):!_

Verwendet eine rekursive Ersetzungsimplementierung. Einfach genug.

Mama Fun Roll
quelle
4

Regex (PCRE-Geschmack), 41 37 Bytes

^((<(?1)>|{(?1)}|\[(?1)]|\((?1)\))*)$

Nur eine Standardlösung mit rekursivem regulären Ausdruck.

Danke jimmy23013, dass du 4 Bytes gespart hast

n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳
quelle
4

Perl, 34 33 Bytes

Beinhaltet +2 für -lp

Mit Eingabe auf STDIN ausführen:

./brackets.pl <<< "{<>()}"

brackets.pl:

#!/usr/bin/perl -lp
s/\(\)|\[]|<>|{}//&&redo;$_=!$_

Findet das erste Klammerpaar ohne irgendetwas dazwischen und entfernt es, solange es welche gibt. Überprüft dann, ob die letzte Zeichenfolge leer ist.

Tonne Hospel
quelle
Würde nicht s/\(\)|\[]|<>|{}//&&redo;$_=!$_funktionieren :)
Dada
Es wäre toll, wenn Sie auch eine Erklärung geben könnten.
Prashant Pokhriyal
@Dada Natürlich. Ich muss senil werden ..
Ton Hospel
4

Brain-Flak , 204 Bytes

(()){{}{({}<>)<>}<>({<(<(({})<>)>)(((((((([(())()()()]){}){}){}())(()))(((())()){}()){})){})(({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}))<>{}<>{{}({}[({})]<>({})){(<>)(<>)}{}{}(<>)}{}>{}<>}<>)}{}((){<>[()]})

Probieren Sie es online!

Nicht ganz so kurz wie die Antwort von Nitroden , verwendet aber einen ganz anderen Ansatz. Dieser Befehl durchläuft die Eingabe wiederholt und entfernt jedes Mal benachbarte passende Klammerpaare, bis keine mehr vorhanden sind. Wenn zu diesem Zeitpunkt noch etwas auf dem Stapel vorhanden ist, wurde die Zeichenfolge nicht vollständig zugeordnet.

Erläuterung:

(())  Push 1 to simulate the check at the start of the loop
{  While check
	{}           Pop check
	{({}<>)<>}<> Reverse input
	({           Loop over input
		< Don't push the values of these calculations
		(<(({})<>)>)  Create a copy of the top of the input and push to the other stack
		(((((
		((([(())()()()]){}){}){}())
		(()))
		(((())()){}()){})
		){})          Push the differences in values of the end brackets 
		(({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}))  If the copy is the same as any of these, push the difference between the other bracket twice
		<>{}<>  Pop copy
		{  If this character is a start bracket
			{}({}[({})]<>({}))  Check if the next character is the end bracket
			{(<>)(<>)}{}          If not, push a 0 to each stack as buffer
			{}       Pop the top of the input stack, either the start bracket if they matched or the buffer 0
			(<>)     Push 0 to other stack to end check
		}{}>
		{}   Pop the top of the other stack
		         If the character was not an end bracket, pop the copy of check, which is 0
		         If it was, but didn't match the next character, pop the buffer 0
		         If the brackets matched, pop the end bracket and add it to the loop total
	<>}	Repeat with the rest of the input
	<>)	Push the loop total
		If any brackets were matched, the loop total is non zero
}{}
((){<>[()]}) If there is anything left on the stack, push 0 to the other stack, otherwise push 1
Scherzen
quelle
3

Brainfuck, 132 Bytes

+>,[[<->>+>[-]<<-]<[>+>[<+<+>>>+<-]+++++[>--------<-]>[<<+>++++[>-----<-]>[<++++
+[>------<-]>-[<++++[>--------<-]>[,>]]]]<],]<<[>]>.

Formatiert:

+>,
[
  [<-> >+>[-]<<-]
  <
  [
    not matching closing bracket
    >+>[<+<+>> >+<-]
    +++++[>--------<-]
    >
    [
      not open paren
      <<+>
      ++++[>-----<-]>
      [
        not open angle bracket
        <+++++[>------<-]>-
        [
          not open square bracket
          <++++[>--------<-]>
          [
            not open brace
            ,>
          ]
        ]
      ]
    ]
    <
  ]
  ,
]
<<[>]
>.

Erwartet Eingaben ohne abschließende Zeilenumbrüche. Druckt \x00für falsch und \x01für wahr.

Probieren Sie es online aus.

Ansatz: Behalten Sie einen Stapel bei \x01, der mit beginnt , und drücken Sie die entsprechende schließende Klammer, wenn eine öffnende Klammer angetroffen wird. Bevor Sie prüfen, ob das aktuelle Zeichen eine öffnende Klammer ist, prüfen Sie zunächst, ob es mit der schließenden Klammer oben auf dem Stapel übereinstimmt, und platzieren Sie sie gegebenenfalls. Wenn es weder die richtige schließende noch die öffnende Klammer ist, verbrauchen Sie den Rest der Eingabe, während Sie den Zeiger nach rechts bewegen. Überprüfen Sie am Ende, ob sich der Zeiger neben dem Anfangsbuchstaben befindet \x01.

Mitch Schwartz
quelle
2

Grime v0.1, 34 Bytes

M=\(M\)|\[M\]|\{M\}|\<M\>|MM|_
e`M

Druckt 1für eine Übereinstimmung und 0für keine Übereinstimmung. Probieren Sie es online!

Erläuterung

Grime ist meine 2D-Pattern-Matching-Sprache, die für diese Herausforderung entwickelt wurde . Es kann auch verwendet werden, um 1D-Zeichenfolgen abzugleichen. Dies ist meine erste Antwort damit. Ich habe Grime heute modifiziert, aber nur, um den Charakter eines Syntaxelements ( `statt ,) zu ändern , damit es meine Punktzahl nicht beeinflusst.

M=                         Define pattern called M that matches:
\(M\)|\[M\]|\{M\}|\<M\>      a smaller M inside matched brackets,
|MM                          or two smaller Ms concatenated,
|_                           or the empty pattern.
e`M                        Match the entire input against M.
Zgarb
quelle
2

Reng v.3.3, 137 Bytes, nicht konkurrierend

Probieren Sie es hier aus!

aií0#zl2,q!~1ø
:"]"eq!v:"}"eq!v:">"eq!v:")"eq!v)1z+#z
ve¤[2-2<       <       <     +1<
>]?v$$$zÀ0#z >ðq!vlqv¤l2%[1Ø
   \$2+)1z+#z/   ~n1/

Es gibt noch ein bisschen mehr zu golfen, aber zumindest funktioniert es. Ich habe einen Befehl hinzugefügt ð, um die Stapel nach dieser Herausforderung zu verfolgen, damit dies aus der Ferne möglich / einfach ist. Ich werde das gleich erklären, aber es verfolgt im Allgemeinen alle Zeichenfolgen, die durchlaufen wurden, und sucht nach Wiederholungen. Wenn es eine Wiederholung gibt, ist die Zeichenfolge nicht reduzierbar. Andernfalls wird der String auf den leeren String / Stack reduziert und ausgegeben 1. Andernfalls wird keine Ausgabe erzeugt.

Conor O'Brien
quelle
2

PowerShell v2 +, 63 bis 62 Byte

param($a)for(;$a-ne$b){$a=($b=$a)-replace"\[\]|\(\)|<>|{}"}!$a

Kann JavaScript nicht ganz einfangen, verdrängt aber derzeit die anderen Nicht-Esolangs.

Ähnlicher Ansatz wie andere Antworten: eine einfache Schleife , die so lange weiter , wie wir entfernen [], ()oder <>(mit mehreren irrelevanten Zeichen , weil wir die Regex Angebote entkommen müssen). Wir verwenden sie $bals Hilfe , um uns zu erinnern, wie unsere vorherigen Schleifen $aeingestellt waren. Eine nicht initialisierte Variable ist $nullalso $aoffensichtlich ungleich, wenn die Schleife zum ersten Mal angetroffen wird $null.

Am Ende der Schleife $aist entweder leer oder nicht, und der Boolesche Wert dieser Zeichenfolge ist entweder Trueoder False.

Beispiel

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({})]"
True

PS C:\Tools\Scripts\golfing> .\are-the-brackets-fully-matched.ps1 "[({])}"
False
AdmBorkBork
quelle
2

C 121 122 114 Bytes

Rasiert von 8 Bytes dank @xsot!

a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!k*!i);}

Verwendet einen Stapel.

mIllIbyte
quelle
Ich mag das c%7&2. Eigentlich brauchst du nicht k. Stattdessen können Sie einfach inkrementieren, iwo Sie Änderungen vornehmen würden, kda Sie iohnehin überprüfen müssen, ob irgendwann Null ist. So etwas wie dieser (ungetestet Code): a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i--]^c/9:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}.
Xsot
@xsot - Funktioniert das Inkrementieren von i? Wir müssen auch vermeiden, das Array mit einem negativen Wert zu subskribieren, also müssen wir entweder i oder k in the for testen.
MIllIbyte
Ah ich sehe. Es gibt jedoch noch Raum für Verbesserungen:a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!i*!k);}
xsot
@xsot - Vielen Dank! Um die Einsparungen zusammenzufassen, lesen Sie 5 Bytes gespeichert, ^ 1 gespeichert und den mittleren Operanden des bedingten Operators 2 gespeichert. Ich bin überrascht, dass der mittlere Operand des bedingten Operators eine Zuweisung sein kann. Ich dachte, dass es einen Fehler geben würde, so etwas wie "missing: before =".
MIllIbyte
@xsot - Ich habe versucht, i zu erhöhen, anstatt k zu verwenden, wie Sie zuerst angedeutet haben: a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i]^c/9?1:-1:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}Dies funktioniert jedoch noch nicht für Eingaben wie ())), da das "Poppen" vom Stapel die Werte im Array nicht auf Null setzt.
MIllIbyte
2

Java 7, 156 151 Bytes

class A{public static void main(String[]a){for(int i=0;i<-1>>>1;++i,a[0]=a[0].replaceAll("<>|\\[]|\\(\\)|\\{}",""));System.out.print(a[0].isEmpty());}}

Ich erwarte nicht, dass dies Preise gewinnt, aber ich habe noch keine Java-Antwort erhalten. Außerdem lauere ich gerne in PPCG herum und würde gerne über andere Antworten abstimmen / Kommentare abgeben.

Die Eingabe erfolgt als Programmparameter. Dies folgt dem gleichen Format wie viele andere Antworten hier, indem ein regulärer Ausdruck in einer Schleife ersetzt wird. Ursprünglich hatte ich es N-mal in der Schleife, wobei N die Länge der ursprünglichen Zeichenfolge ist, aber die Schleife zu Integer.MAX_VALUEkürzer ist:]. Dies sollte in Ordnung sein, da Integer.MAX_VALUEes sich um die maximale Länge von a Stringin Java handelt. Daher wird implizit davon ausgegangen, dass die Länge der Eingabe von Java verarbeitet werden kann. Die Laufzeit ist aufgrund der Schleife ziemlich schlecht (hat auf meinem Laptop ungefähr 20 Minuten gedauert), aber ich habe keine Einschränkung darin gesehen.

Sack
quelle
2

Haskell , 151 Bytes

infix 1#
'(':x#y=x#')':y
'<':x#y=x#'>':y
'[':x#y=x#']':y
'{':x#y=x#'}':y
')':x#')':y=x#y
'>':x#'>':y=x#y
']':x#']':y=x#y
'}':x#'}':y=x#y
""#""=1
_#_=0

Probieren Sie es online!

Roman Czyborra
quelle
Ein paar Dinge: Da die Funktion (#)mit dem leeren String als zweitem Argument aufgerufen werden muss, müssen Sie (#"")auf Ihre Byteanzahl angerechnet werden. Auch nur Trueund Falseals wahr / falsch gelten, siehe den Guide to Golfing Rules .
Laikoni
1
Die vier Zeilen mit den schließenden Klammern können jedoch durch ersetzt werden a:x#b:y|a==b=x#y, wodurch sich die Anzahl der Bytes auf 113 verringert
Laikoni
2
109 Bytes: Probieren Sie es online!
Laikoni
2

Python 2.7, 96 Bytes

def r(s):i=max(map(s.find,['()','[]','{}','<>']));return not len(s)if i<0 else r(s[:i]+s[i+2:])
user5983247
quelle
2
Willkommen auf der Seite!
DJMcMayhem
1

Python 2, 80 Bytes

def m(s,i=0):exec's=s.replace("[({<])}>"[i%4::4],"");i+=1;'*4*len(s);return"">=s
orlp
quelle
1

Julia, 51 Bytes

~z=z==(n=replace(z,r"\(\)|\[]|{}|<>",""))?z=="":~n

Die am wenigsten verrückte von mehreren Optionen. Es überrascht nicht, dass der kürzeste Weg zum String-Matching darin besteht, die Potenz von Regex zu nutzen. Dies gilt jedoch nur dann, wenn das zu vergleichende Muster regelmäßig ist. Wenn Sie versuchen, rekursive PCRE-Muster zu erstellen, wird die Größe des Codes vergrößert, indem Sie entweder feststellen, ob die gesamte Zeichenfolge übereinstimmt, oder indem Sie die Enden verankern und dann ein Konstrukt erstellen, um den inneren Körper für die Regex-Rekursion anzugeben. Weder von denen sind hübsch oder förderlich für Code Golf.

Erläuterung:

~z=                            # Define ~z to be the following:
    z==(                       # If z is equal to                                     
        n=replace(z,           # z with the replacement of 
            r"\(\)|\[]|{}|<>", # adjacent matching brackets ((),[],{}, or <>)
            ""                 # with empty strings
        )                      # (which is assigned to n)
    )?z==""                    # whether z is an empty string
    :~n                        # else ~ applied to the substituted string

Die Funktion entfernt wiederholt benachbarte Klammerpaare aus ihrem einzigen Argument und gibt true zurück, wenn sie auf diese Weise eine leere Zeichenfolge ableiten kann.

eaglgenes101
quelle
1

sed, 39 36 Bytes (34 für Code, 2 für -r)

:a
s/\(\)|\[]|<>|\{}//;ta
/./c0
c1

Probieren Sie es online!

sed-Version des scheinbar Standardansatzes. Benötigt erweiterte reguläre Ausdrücke ( sed -r)

3 Bytes gespart dank Cows Quack

Strahl
quelle
Sie können die entfernen aheißt :aund taBytes speichern
Kritixi Lithos
@KritixiLithos Anscheinend war das ein Fehler in GNU sed , der in 4.3 behoben wurde . Ich würde diese Charaktere wahrscheinlich fallen lassen, wenn dieser Eintrag nah genug am Anführer wäre, um eine Gewinnchance zu haben, aber da dies nicht der Fall ist, lasse ich ihn einfach in der portableren Form, damit er nicht aufhört zu funktionieren wenn mehr Systeme auf 4.3 aktualisiert werden.
Ray
1
Rückblickend bin ich sicher, dass Sie das qvon /./und die Klammern dort auch fallen lassen können. Probieren Sie es online! Dies liegt daran, wie cHange funktioniert
Kritixi Lithos
@Cowsquack Danke. Bearbeitet
Ray
0

05AB1E, 9 Bytes

žu2ôõ:g2Q

Die Eingabe erfolgt in Anführungszeichen.

Probieren Sie es online!

Erläuterung:

žu          # Push "()<>[]{}"
  2ô        # Split into pieces of size 2
    õ       # Push empty string
            # Implicit input
      :     # Infinite replacement
       g2Q  # Is length equal to 2?
            # Implicit print
Oliver Ni
quelle
0

Clojure, 153 Bytes

Länger als C und Brainfuck antwortet: o

(defn f[[s & r]](if s(let[[a b](split-at(.indexOf(reductions + 1(for[c r](get(zipmap[s({\(\)\[\]\{\}\<\>}s)][1 -1])c 0)))0)r)](and(not=()a)(f(butlast a))(f b))))1)

Verwendet keine regulären Ausdrücke, verwendet stattdessen das erste Zeichen, um zu bestimmen, was das schließende Tag ist, und findet den ersten Index, in dem diese Klammer ausgeglichen ist (kumulative Summe ist Null). Anschließend wird iterativ überprüft, ob die Angaben in Klammern und nach Klammern gültig sind.

Mal sehen, ob es einen besseren Ansatz gibt ...

NikoNyrh
quelle
0

Lua , 295 Bytes

f = false g = string.gsub t=table s={}b=io.read()for c in b:gmatch('.')do if c:find("[%[<{%(]")then s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")")elseif c:find("[%]>}%)]")then if t.remove(s)~=c then print(f)return end else print(f)return end end if#s>0 then print(f)else print(1)end

Ungolfed Version

f = false
g = string.gsub
t=table
s={} --Define a stack of opening brackets
b=io.read() --get the input
for c in b:gmatch('.') do   --for every character
    if c:find("[%[<{%(]") then
        s[#s + 1] = g(g(g(g(c,"<",">"),"{","}"),"%[","]"),"%(",")") --if the current character is an opening bracket, push the closing bracket onto the stack
    elseif c:find("[%]>}%)]") then
        if t.remove(s)~=c then
            print(f) --if the character is a closing bracket, pop the closing bracket off the stack and test if they match, if not print false
            return
        end
    else 
        print(f) --if the character is not a bracket print false
        return
    end
end
if #s>0 then
    print(f) --if there are still brackets on the stack print false
else
    print(1) --print 1 there are no brackets on the stack
end

Probieren Sie es online!

Alex Allen
quelle
0

R 298

function(.){s=strsplit;u=paste0;.=s(.,"")[[1]];p=s("><)(}{][","")[[1]];.[!.%in%p]="§";for(i in 1:4*2){.[.==p[i]]=sprintf("S('%s',{",p[i]);.[.==p[i-1]]=sprintf("},'%s');",p[i])};S=function(H,B,T)if(H!=T)stop();r=try(eval(parse(,,u(.,collapse=""))),1);if(inherits(r,"try-error"))FALSE else TRUE}

Der Ansatz hier besteht darin, die Sequenz in R-Code umzuwandeln und dann zu analysieren und auszuwerten. Wenn dies zu einem Fehler führt, kehren Sie zurück FALSE.

Aber es gibt ein kleines Problem ... R Regeln für Klammern sind unterschiedlich, so <und >nicht Klammern überhaupt, und die anderen Typen haben Regeln ihrer eigenen. Dies wird durch einen revolutionären Ansatz gelöst - eine Quietschfunktion, deren einzige Funktion darin besteht, einen Fehler zu signalisieren, wenn Kopf und Schwanz auf unterschiedliche Weise quietschen.

Zum Beispiel []wird transformiert in S('[', {}, ']'), wobei S definiert ist als ...

S=function(H,B,T)if(H!=T)stop() 

Da das Kopfquietschen und das Schwanzquietschen übereinstimmen, wird kein Fehler geworfen.

Einige andere Beispiele (der linke Teil ist eine Folge von Klammern und der rechte Teil ist die Umwandlung in einen gültigen R-Code, der ausgewertet werden kann):

[}     -->  S('[', {}, '}')     # squeaks an error
[()]   -->  S('[', {S('(',{},'(')}, "[")
({[]}) -->  S('(',{S('{',{S('[',{},'[');},'{');},'(');

Einige andere Folgen von Klammern führen zu Analysefehlern:

[[)    -->   S('[',{S('[',{},'('); 

Der verbleibende Teil fängt also nur die Fehler ab und gibt FALSE zurück, falls es welche gibt, und TRUE, falls es keine gibt.

Der für Menschen lesbare Code:

 sqk <- function(.){
   s=strsplit;u=paste0
   .=s(.,"")[[1]]            # break the argument up into 1-character pieces
   p=s("><)(}{][","")[[1]]   # vector of brackets
   .[!.%in%p]="§"            # replace anything besides brackets by § (--> error)
   for(i in 1:4*2){     
     .[.==p[i]]=sprintf("S('%s',{",p[i])    # '<' -->   S('<',{     ... etc
     .[.==p[i-1]]=sprintf("},'%s');",p[i])  # '>' -->   },'<');     ... etc  
   }
   S=function(H,B,T)if(H!=T)stop()          # define the working horse
   r=try(eval(parse(,,u(.,collapse=""))),1) # evaluate the sequence
   if(inherits(r,"try-error"))FALSE else TRUE   # any errors?
   }

Anwendung auf Musterfälle:

truthy<-readLines(textConnection("()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]"))
falsy<-readLines(textConnection("(
}
(<2)>
(()()foobar)
[({}<>)>
(((()))"))
> sapply(truthy,sqk)
                      ()                 [](){}<>                 (((()))) 
                    TRUE                     TRUE                     TRUE 
                ({[<>]})             [{()<>()}[]] [([]{})<{[()<()>]}()>{}] 
                    TRUE                     TRUE                     TRUE 
> sapply(falsy,sqk)
           (            }        (<2)> (()()foobar)     [({}<>)>      (((())) 
       FALSE        FALSE        FALSE        FALSE        FALSE        FALSE 
lebatsnok
quelle