Sie sind Projektmanager. Eines Tages wurde einer Ihrer Programmierer wahnsinnig ( nicht Ihre Schuld ), nahm alle Ausdrücke in die Codebasis und fügte ihnen zufällige Klammern hinzu, bevor er sofort aufhörte und über Ihre Inkompetenz schwärmte ( auch nicht Ihre Schuld ). Dies ist jedoch eine einfache Lösung, da Sie aus irgendeinem Grund die Versionskontrolle nicht verwenden ( ganz und gar nicht Ihre Schuld ). Und aus irgendeinem Grund möchte keiner der anderen Programmierer alle Ausdrücke durchgehen, um die nicht übereinstimmenden Klammern zu korrigieren ( das ist übrigens nicht Ihre Schuld ). Programmierer heutzutage, denken Sie. Sie müssen es selbst tun. Der Horror! Solche Aufgaben sollten unter Ihnen sein ...
Die Eingabe wird eine einzelne Zeile sein, die eine Reihe von linken Klammern ( ( [ {
) und rechten Klammern ( ) ] }
) enthält. Es kann auch, aber nicht immer, Kommentare ( /* */
) und Zeichenkettenliterale ( " "
oder ' '
) sowie verschiedene Zahlen, Buchstaben oder Symbole enthalten.
Es wird mindestens eine eckige Klammer (außerhalb eines Kommentars oder eines String-Literal) geben, die kein entsprechendes Gegenteil hat (außerhalb eines Kommentars oder eines String-Literal). Zum Beispiel ein Irrtum }
ohne {
Prior. Ein anderes Beispiel: a, (
das )
hinterher kein hat . Ihr Programm ersetzt durch ein Leerzeichen die Mindestanzahl von Klammern, die erforderlich sind, damit die Klammern übereinstimmen.
Beispiele:
(4 + (2 + 3))]
==> (4 + (2 + 3))
(die eckige Klammer am Ende)
][][[]]
==> [][[]]
(die eckige Klammer am Anfang)
("Hel(o!"))
==> ("Hel(o!")
(die Klammer am Ende)
( /* )]*/
==> /* )]*/
(die Klammer am Anfang)
{()]
==> ()
(die geschweifte Klammer und die eckige Klammer)
- Die Eingabe kann von einem beliebigen Ort aus erfolgen (STDIN, Befehlszeilenargument, Lesen aus einer Datei usw.).
- Wenn es mehr als eine Möglichkeit gibt, die Nichtübereinstimmung mit der gleichen Anzahl von Entfernungen zu beheben, ist beides akzeptabel.
- In Klammern werden nur Abweichungen angezeigt. Zeichenkettenliterale und Kommentare werden immer korrekt gebildet.
- Der Titel stammt aus diesem SO-Thread
- Es wird niemals Anführungszeichen in Kommentaren, Anführungszeichen in Anführungszeichen, Kommentare in Kommentaren oder Kommentare in Anführungszeichen geben.
Dies ist Codegolf, daher gewinnt die Mindestanzahl an Bytes. Stellen Sie Fragen in Kommentaren, wenn die Spezifikation nicht klar ist.
quelle
("foo (\") bar")
)?{{(})
sollte{ }
oder gleichwertig sein, da das Eröffnungsszenario impliziert, dass der Code zu Beginn arbeitete, und{(})
als nicht übereinstimmende Klammern in jeder mir bekannten Programmiersprache zählt (dh "verursacht Stasis" ??). Aber dann habe ich bereits eine Antwort geschrieben, also bin ich voreingenommen.Antworten:
Ruby, 223 Zeichen
Dieser erwies sich als etwas lang.
Es werden zuerst die Zeichenfolgen und Kommentare entfernt, damit sie nicht gezählt werden (und später wieder eingefügt werden).
Dann wird die Zeichenfolge zeichenweise durchlaufen. Wenn es eine öffnende Klammer findet, speichert es seine Position. Wenn eine schließende geschweifte Klammer gefunden wird, wird sie aus dem entsprechenden Speicherarray für offene geschweifte Klammern entfernt.
Bei
pop
Rückgabenil
(dh es gab nicht genügend öffnende Klammern) wird die schließende Klammer entfernt. Nachdem dies alles erledigt ist, werden die verbleibenden zusätzlichen öffnenden Klammern entfernt (dh es gab nicht genügend schließende Klammern).Am Ende des Programms werden alle Zeichenfolgen und Kommentare zurückgesetzt und ausgegeben.
Ungolfed:
quelle
(("string"/*comment*/)"string"
? Wenn ich die ungolfed-Version richtig lese, ersetzen Sie Zeichenfolgen und Kommentare durch ihren Index imunparsed
Array, was zu einer Substitution führen würde((12)3
und dann nach einem nicht vorhandenen Index12
(oder11
) suchen würde . Ich sehe, die Golf-Version verwendet nurshift
, aber könnte es nicht immer noch ein ähnliches Problem haben?Python 3,
410322317Versucht jeden möglichen Satz von Löschungen, beginnend mit kleineren, bis er einen findet, bei dem die Klammern ausgeglichen sind. (Womit ich voll richtig ausbalanciert meine:
{{(})
produziert( )
, nicht{(})
.)Die erste Version verwendete eine rekursive Generatorfunktion, die sehr cool, aber auch sehr lang war. Diese Version führt eine einfache Breitensuche mit einer Warteschlange durch. (Ja, es ist ein faktorieller Zeitalgorithmus. Was ist das Problem?: ^ D)
quelle
C - 406
Ein Versuch in C ohne reguläre Ausdrücke.
Kompilieren und ausführen (auf einem Linux-Computer):
gcc -o Klammern brackets.c
./brackets "[(])"
In undefinierten Fällen wie [(]) wird das letzte gültige Klammerpaar zurückgegeben ()
quelle
Python 3, 320
Wie bei der DLosc-Lösung wird hier jede mögliche Löschung untersucht, es wird jedoch eine viel schnellere rekursive Erkundungs- und Ausweichstrategie verwendet. Ich weiß, dass Geschwindigkeit im Code-Golf kein Kriterium ist und eine erschöpfende Suche auf jeden Fall exponentiell ist, aber diese kann Eingaben wie
({({({({({({({({(}}}}}}}}
in ein paar Sekunden verarbeiten.quelle
O(n!!)
Lösung, nichtO(n!)
. (Mein Golf istO(n*2^n)
stattdessenO(2^n)
, weilo
tatsächlich alle Muster mit bis zur
Entfernungen erzeugt werden, anstatt genaur
Entfernungen. Einfach zu reparieren, aber es würde ein paar Zeichen kosten.)