Balanced Brackets-Algorithmus in Java

1. Übersicht

Balanced Brackets, auch als Balanced Parentheses bezeichnet, sind ein häufiges Programmierproblem.

In diesem Tutorial überprüfen wir, ob die Klammern in einer bestimmten Zeichenfolge ausgeglichen sind oder nicht.

Diese Art von Zeichenfolgen ist Teil der sogenannten Dyck-Sprache.

2. Problemstellung

Eine Klammer ist eines der folgenden Zeichen: "(", ")", "[", "]", "{", "}".

Ein Satz von Klammern wird als übereinstimmendes Paar betrachtet, wenn links von der entsprechenden schließenden Klammer ")", "]" und "} eine öffnende Klammer " ("," ["und" {") vorkommt ", beziehungsweise.

Eine Zeichenfolge mit Klammerpaaren ist jedoch nicht ausgeglichen, wenn die darin enthaltenen Klammern nicht übereinstimmen .

In ähnlicher Weise wird auch eine Zeichenfolge, die nicht in Klammern gesetzte Zeichen wie az, AZ, 0-9 oder andere Sonderzeichen wie #, $, @ enthält , als unausgeglichen betrachtet .

Wenn die Eingabe beispielsweise "{[(])}" lautet, schließt das Paar eckiger Klammern "[]" eine einzelne runde Klammer mit unausgeglichener Öffnung "(" ein. Ebenso das Paar runder Klammern "()). ”, Umschließt eine einzelne unsymmetrische schließende eckige Klammer,“] ”. Somit ist die Eingabezeichenfolge“ {[(])} ”unsymmetrisch.

Daher wird eine Zeichenfolge mit Klammerzeichen als ausgeglichen bezeichnet, wenn:

  1. Links von jeder entsprechenden schließenden Klammer befindet sich eine passende Öffnungsklammer
  2. Klammern, die in ausgeglichenen Klammern eingeschlossen sind, sind ebenfalls ausgeglichen
  3. Es enthält keine Zeichen ohne Klammern

Es sind einige Sonderfälle zu beachten: Null wird als nicht ausgeglichen angesehen, während die leere Zeichenfolge als ausgeglichen betrachtet wird .

Um unsere Definition von ausgeglichenen Klammern weiter zu veranschaulichen, sehen wir uns einige Beispiele für ausgeglichene Klammern an:

() [()] {[()]} ([{{[(())]}}])

Und einige, die nicht ausgewogen sind:

abc[](){} {{[]()}}}} {[(])}

Nachdem wir unser Problem besser verstanden haben, wollen wir sehen, wie wir es lösen können!

3. Lösungsansätze

Es gibt verschiedene Möglichkeiten, dieses Problem zu lösen. In diesem Tutorial werden zwei Ansätze betrachtet:

  1. Verwenden von Methoden der String- Klasse
  2. Verwenden der Deque- Implementierung

4. Grundlegende Einrichtung und Validierungen

Erstellen wir zunächst eine Methode, die true zurückgibt, wenn die Eingabe ausgeglichen ist, und false, wenn die Eingabe nicht ausgeglichen ist:

public boolean isBalanced(String str)

Betrachten wir die grundlegenden Validierungen für die Eingabezeichenfolge:

  1. Wenn eine Null- Eingabe übergeben wird, ist sie nicht ausgeglichen.
  2. Damit eine Saite ausgeglichen werden kann, sollten die Paare der öffnenden und schließenden Klammern übereinstimmen. Daher kann man mit Sicherheit sagen, dass eine Eingabezeichenfolge mit ungerader Länge nicht ausgeglichen wird, da sie mindestens eine nicht übereinstimmende Klammer enthält.
  3. Gemäß der Problemstellung sollte das ausgeglichene Verhalten in Klammern überprüft werden. Daher ist jede Eingabezeichenfolge, die Zeichen ohne Klammern enthält, eine nicht ausgeglichene Zeichenfolge.

Mit diesen Regeln können wir die Validierungen implementieren:

if (null == str || ((str.length() % 2) != 0)) { return false; } else { char[] ch = str.toCharArray(); for (char c : ch) { if (!(c == '' || c == ']' || c == ')')) { return false; } } }

Nachdem die Eingabezeichenfolge überprüft wurde, können wir dieses Problem lösen.

5. Verwenden der String.replaceAll- Methode

Bei diesem Ansatz durchlaufen wir die Eingabezeichenfolge und entfernen mit String.replaceAll die Vorkommen von "()", "[]" und "{}" aus der Zeichenfolge . Wir setzen diesen Prozess fort, bis keine weiteren Vorkommen in der Eingabezeichenfolge gefunden werden.

Wenn der Vorgang abgeschlossen ist und die Länge unserer Zeichenfolge Null ist, wurden alle übereinstimmenden Klammerpaare entfernt und die Eingabezeichenfolge ausgeglichen. Wenn die Länge jedoch nicht Null ist, sind in der Zeichenfolge noch einige nicht übereinstimmende öffnende oder schließende Klammern vorhanden. Daher ist die Eingabezeichenfolge nicht ausgeglichen.

Sehen wir uns die vollständige Implementierung an:

while (str.contains("()") || str.contains("[]") || str.contains("{}")) { str = str.replaceAll("\\(\\)", "") .replaceAll("\\[\\]", "") .replaceAll("\\{\\}", ""); } return (str.length() == 0);

6. Verwenden von Deque

Deque ist eine Form der Warteschlange , die an beiden Enden der Warteschlange Operationen zum Hinzufügen, Abrufen und Durchsuchen bereitstellt. Wir werden die LIFO-Ordnungsfunktion (Last-In-First-Out) dieser Datenstruktur nutzen, um den Saldo in der Eingabezeichenfolge zu überprüfen.

Lassen Sie uns zuerst unsere Deque konstruieren :

Deque deque = new LinkedList();

Beachten Sie, dass wir hier eine LinkedList verwendet haben, da diese eine Implementierung für die Deque- Schnittstelle bietet.

Nachdem unsere Deque erstellt wurde , werden wir jedes Zeichen der Eingabezeichenfolge einzeln durchlaufen. Wenn das Zeichen eine öffnende Klammer ist, fügen wir es als erstes Element in die Deque ein :

if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); }

Wenn das Zeichen jedoch eine schließende Klammer ist, werden wir einige Überprüfungen der LinkedList durchführen .

Zuerst prüfen wir, ob die LinkedList leer ist oder nicht. Eine leere Liste bedeutet, dass die schließende Klammer nicht übereinstimmt. Daher ist die Eingabezeichenfolge nicht ausgeglichen. Also geben wir false zurück .

Wenn die LinkedList jedoch nicht leer ist, sehen wir uns mit der peekFirst- Methode das letzte Zeichen an . Wenn es mit der schließenden Klammer gepaart werden kann, entfernen wir dieses oberste Zeichen mit der removeFirst- Methode aus der Liste und fahren mit der nächsten Iteration der Schleife fort:

if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; }

Am Ende der Schleife werden alle Zeichen auf Balance geprüft, sodass wir true zurückgeben können . Nachfolgend finden Sie eine vollständige Implementierung des Deque- basierten Ansatzes:

Deque deque = new LinkedList(); for (char ch: str.toCharArray()) { if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); } else { if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; } } } return true;

7. Fazit

In diesem Tutorial haben wir die Problemstellung von Balanced Brackets diskutiert und mit zwei verschiedenen Ansätzen gelöst.

Wie immer ist der Code auf Github verfügbar.