streamalism.org

1. Overzicht

Gebalanceerde haakjes, ook wel gebalanceerde haakjes genoemd, is een veelvoorkomend programmeerprobleem.

In deze tutorial zullen we valideren of de haakjes in een bepaalde string gebalanceerd zijn of niet.

Dit type snaren maakt deel uit van wat bekend staat als de Dyck-taal.

2. Probleemstelling

Een haakje wordt beschouwd als een van de volgende tekens - "(", ")", "[", "]", "{", "}".

Een set beugels is beschouwd als een gematcht paar als een openingsbeugel, "(", "[", En "{", vindt links van de corresponderende sluitbeugel plaats, ")", "]" En "}", respectievelijk.

Een string met haakjesparen is echter niet gebalanceerd als de set beugels die het omsluit niet overeenkomt.

Evenzo een tekenreeks die niet-vierkante tekens bevat zoals a-z, A-Z, 0-9 of andere speciale tekens zoals #, $, @ wordt ook als onevenwichtig beschouwd.

Als de invoer bijvoorbeeld '{[(])}' is, omsluit het paar vierkante haakjes '[]' een enkele ronde haak met ongebalanceerde opening, '('. Evenzo omvat het paar ronde haakjes '() ”, Omsluit een enkele ongebalanceerde afsluitende vierkante haak,“] ”. De invoertekenreeks“ {[(])} ”is dus onevenwichtig.

Daarom wordt gezegd dat een string die haakjes bevat, gebalanceerd is als:

1. Links van elke corresponderende sluitingsbeugel bevindt zich een bijpassende openingsbeugel
2. Beugels tussen gebalanceerde beugels zijn ook gebalanceerd
3. Het bevat geen tekens die geen haakjes zijn

Er zijn een aantal speciale gevallen waarmee u rekening moet houden: nul wordt als ongebalanceerd beschouwd, terwijl de lege string als gebalanceerd wordt beschouwd.

Laten we, om onze definitie van gebalanceerde beugels verder te illustreren, enkele voorbeelden van gebalanceerde beugels bekijken:

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

En een paar die niet in balans zijn:

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

Nu we ons probleem beter begrijpen, gaan we kijken hoe we het kunnen oplossen!

3. Oplossingsbenaderingen

Er zijn verschillende manieren om dit probleem op te lossen. In deze tutorial zullen we twee benaderingen bekijken:

1. Met behulp van methoden van de Draad klasse
2. Gebruik makend van Deque implementatie

4. Basisinstellingen en validaties

Laten we eerst een methode maken die zal terugkeren waar als de input is gebalanceerd en false als de ingang ongebalanceerd is:

openbare boolean isBalanced (String str)

Laten we eens kijken naar de basisvalidaties voor de invoertekenreeks:

1. Als een nul input wordt doorgegeven, dan is het niet gebalanceerd.
2. Om een ​​snaar in evenwicht te brengen, moeten de paar haakjes voor openen en sluiten overeenkomen. Daarom zou het veilig zijn om te zeggen dat een invoertekenreeks waarvan de lengte oneven is, niet zal worden gebalanceerd omdat deze ten minste één niet-overeenkomende haak bevat.
3. Volgens de probleemstelling moet het gebalanceerde gedrag tussen haakjes worden gecontroleerd. Daarom is elke invoertekenreeks die niet-vierkante tekens bevat, een ongebalanceerde tekenreeks.

Gezien deze regels kunnen we de validaties implementeren:

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

Nu de invoerstring is gevalideerd, kunnen we verder gaan met het oplossen van dit probleem.

5. Met behulp van String.replaceAll Methode

In deze benadering doorlopen we de invoertekenreeks waarbij we "()", "[]" en "{}" uit de tekenreeks verwijderen met String.replaceAll. We gaan door met dit proces totdat er geen andere exemplaren meer worden gevonden in de invoertekenreeks.

Als het proces eenmaal is voltooid en de lengte van onze tekenreeks nul is, zijn alle overeenkomende paar haakjes verwijderd en is de invoerstring gebalanceerd. Als de lengte echter niet nul is, zijn er nog steeds enkele ongeëvenaarde openings- of sluitingshaken in de string. Daarom is de invoerstring onevenwichtig.

Laten we de volledige implementatie bekijken:

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

6. Met behulp van Deque

Deque is een vorm van de Wachtrij die bewerkingen voor toevoegen, ophalen en bekijken aan beide uiteinden van de wachtrij biedt. We zullen de Last-In-First-Out (LIFO) -bestelfunctie van deze gegevensstructuur gebruiken om het saldo in de invoerstring te controleren.

Laten we eerst onze Deque:

Deque deque = nieuwe LinkedList ();

Merk op dat we een LinkedList hier omdat het een implementatie biedt voor het Deque koppel.

Nu dat onze deque is geconstrueerd, zullen we elk teken van de invoerstring een voor een doorlopen. Als het karakter een openingshaakje is, zullen we het toevoegen als het eerste element in de Deque:

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

Maar als het karakter een sluitende haak is, zullen we enkele controles uitvoeren op de LinkedList.

Eerst controleren we of de LinkedList is leeg of niet. Een lege lijst betekent dat de sluitbeugel ongeëvenaard is. Daarom is de invoerstring onevenwichtig. Dus we keren terug false.

Als het LinkedList is niet leeg, dan kijken we naar het laatste teken met behulp van de eerste methode. Als het kan worden gekoppeld met het sluitende haakje, verwijderen we dit bovenste teken uit de lijst de ... gebruiken removeFirst methode en ga verder met de volgende iteratie van de lus:

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

Aan het einde van de lus worden alle karakters op balans gecontroleerd, zodat we kunnen terugkeren waar. Hieronder vindt u een volledige implementatie van het Deque gebaseerde aanpak:

Deque deque = nieuwe 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;}}} retourneert waar;

7. Conclusie

In deze tutorial hebben we de probleemstelling van Balanced Brackets besproken en deze op twee verschillende manieren opgelost.

Zoals altijd is de code beschikbaar op Github.