Grundlegende Rekursion, überprüfen Sie die ausgeglichene Klammer
Habe ich software geschrieben, die in der Vergangenheit verwendet einen stack, um zu überprüfen für symmetrische Gleichungen, aber jetzt bin ich gefragt, zu schreiben, die einen ähnlichen Algorithmus rekursiv zu überprüfen, korrekt geschachtelte Klammern und Klammern.
Gute Beispiele: () [] ()
([]()[])Schlechte Beispiele: ( (] ([)]
Nehme an, meine Funktion aufgerufen wird: isBalanced.
Sollte jedem Durchlauf zu bewerten, ein kleiner substring (bis zum erreichen einer base bei 2 Links)? Oder, sollte ich immer bewerten Sie die volle Zeichenkette und verschieben Sie Indizes nach innen?
InformationsquelleAutor der Frage pws5068 | 2010-04-26
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gibt es viele Möglichkeiten, dies zu tun, aber der einfachste Algorithmus ist einfach zu verarbeiten, nach vorne Links, nach rechts, vorbei an den stack als parameter
Hier ist es in Java implementiert. Beachten Sie, dass ich gewechselt haben, ist es nun so, dass der Stapel schiebt in vor statt am zurück der Zeichenfolge, für die Bequemlichkeit. Hab ich auch so bearbeitet, dass es nur springt Sie nicht-Klammer-Symbole anstelle von Berichterstattung es als Fehler.
Testumgebung:
Ausgabe:
InformationsquelleAutor der Antwort polygenelubricants
Erste, zu deiner ursprünglichen Frage, nur bewusst sein, dass, wenn Sie arbeiten mit sehr langen Saiten, die Sie nicht wollen, machen exakte Kopien minus einen einzelnen Buchstaben jedes mal, wenn Sie eine Funktion aufrufen. Also Sie sollte zugunsten der Verwendung von Indizes oder stellen Sie sicher, dass Ihre Sprache der Wahl ist nicht die Erstellung von Kopien hinter die kulissen.
Zweiten, ich habe ein Problem mit all den Antworten hier, dass sind die Verwendung einer stack-Datenstruktur. Ich denke, dass der Punkt Ihre Aufgabe ist es für Sie, zu verstehen, dass mit Rekursion eine Funktion ruft erstellen Sie einen Stapel. Sie nicht brauchen, um eine stack-Datenstruktur, halten Sie Ihre Klammern, da jeder rekursive Aufruf wird ein neuer Eintrag auf eine implizite stack.
Werde ich zeigen, mit einem C-Programm entspricht
(
und)
. Hinzufügen von anderen Arten wie[
und]
ist eine übung für den Leser. Alle, die ich halten in der Funktion ist meine position in der Zeichenfolge (übergeben als pointer), da die Rekursion ist mein stack.Getestet mit diesem code:
Ausgabe:
InformationsquelleAutor der Antwort indiv
Die Idee ist, eine Liste der geöffneten Klammern, und wenn Sie eine Schließung brackt, prüfen Sie, ob es schließt sich der Letzte geöffnet:
Wenn die Zeichenfolge ist endlich leer, wenn die Liste der brackes leer ist (also alle brackes geschlossen wurde) zurück
true
, sonstfalse
ALGORITHMUS (in Java):
TEST:
AUSGABE:
Beachten Sie, dass ich importiert haben, werden die folgenden Klassen:
InformationsquelleAutor der Antwort Luca Mastrostefano
Ist es eigentlich egal, von einem logischen Standpunkt-wenn Sie halten einen Stapel von allen derzeit un-ausgewogene parens, dass Sie an jedem Schritt der Rekursion, die Sie nie brauchen, um nach hinten zu schauen, also ist es egal, ob Sie sich schneiden Sie die Zeichenfolge an jedem rekursiven Aufruf, oder einfach nur Inkrementieren eines index und nur ein Blick auf die gegenwärtige erste Zeichen.
In den meisten Programmiersprachen, die nicht-veränderliche Zeichenfolgen, ist es wahrscheinlich teurer (performance-wise) zu verkürzen, wird die Zeichenfolge als es ist, an einem etwas größeren string auf den stack. Auf der anderen Seite, in eine Sprache wie C kann man Inkrementieren eines Zeigers innerhalb des char-array. Ich denke, es ist ziemlich der Sprache abhängig, welcher der beiden Ansätze ist "effizient". Sie sind beide gleich aus einer konzeptionellen Sicht.
InformationsquelleAutor der Antwort Adrian Petrescu
InformationsquelleAutor der Antwort jot
Ich würde sagen, das hängt von Ihrem design. Konnte man entweder zwei Zähler oder einen Stapel mit zwei verschiedenen Symbolen, oder Sie behandeln können es mit Rekursion, der Unterschied wird im design-Ansatz.
InformationsquelleAutor der Antwort Gabriel Ščerbák
InformationsquelleAutor der Antwort siva k
PHP-Lösung um zu überprüfen, ausgewogene Klammern
InformationsquelleAutor der Antwort Swatantra Kumar
In der Scala-Programmiersprache, ich würde es so machen:
Bitte Bearbeiten Sie perfekt zu machen.
War ich nur vorschlagen, eine Umwandlung in Scala.
InformationsquelleAutor der Antwort MrOnyancha
Es soll eine einfache Verwendung von Stacks.
InformationsquelleAutor der Antwort ttk
@indiv Antwort ist schön genug, um lösen der Klammern Grammatik Probleme. Wenn Sie verwenden möchten stack oder nicht verwenden Sie die rekursive Methode kann man sich die python - Skript auf github. Es ist einfach und schnell.
InformationsquelleAutor der Antwort RockOnGom