streamalism.org

1. Oversigt

Balancerede parenteser, også kendt som Balanced Parentheses, er et almindeligt programmeringsproblem.

I denne vejledning vil vi validere, om parenteserne i en given streng er afbalancerede eller ej.

Denne type strenge er en del af det, der er kendt som Dyck-sproget.

2. Problemerklæring

En parentes betragtes som et af følgende tegn - “(“, “)”, “[“, “]”, “{“, “}”.

Et sæt parenteser er betragtes som et matchet par, hvis en åbningsbeslag, “(“, “[“ Og “{“, optræder til venstre for det tilsvarende lukkebeslag, Henholdsvis “)”, “]” og “}”.

Imidlertid er en streng, der indeholder parentespar ikke afbalanceret, hvis det parentesesæt, det lukker, ikke matches.

Tilsvarende en streng, der indeholder tegn, der ikke er parentes som a-z, A-Z, 0-9 eller andre specialtegn som #, $, @ betragtes også som ubalanceret.

For eksempel, hvis input er "{[(])}", lukker parret med firkantede parenteser, "[]" et enkelt ubalanceret åbningsrundbeslag, "(". Tilsvarende er parret med runde parenteser, "() ", Omslutter en enkelt ubalanceret lukning af firkantet parentes,"] ". Derfor er inputstrengen" {[(])} "ikke-afbalanceret.

Derfor siges en streng, der indeholder parentes-tegn, at være afbalanceret, hvis:

1. Et matchende åbningsbeslag forekommer til venstre for hver tilsvarende lukkende beslag
2. Beslag, der er lukket inden for afbalancerede parenteser, er også afbalancerede
3. Den indeholder ikke tegn, der ikke er parentes

Der er et par specielle tilfælde at huske på: nul anses for at være ubalanceret, mens den tomme streng anses for at være afbalanceret.

For yderligere at illustrere vores definition af afbalancerede parenteser, lad os se nogle eksempler på afbalancerede parenteser:

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

Og et par, der ikke er afbalancerede:

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

Nu hvor vi har en bedre forståelse af vores problem, lad os se, hvordan vi løser det!

3. Løsningsmetoder

Der er forskellige måder at løse dette problem på. I denne vejledning vil vi se på to tilgange:

1. Brug af metoder til Snor klasse
2. Ved brug af Deque implementering

4. Grundlæggende opsætning og valideringer

Lad os først oprette en metode, der vender tilbage rigtigt hvis input er afbalanceret og falsk hvis input er ubalanceret:

public boolean isBalanced (String str)

Lad os overveje de grundlæggende valideringer for inputstrengen:

1. Hvis en nul input sendes, så er det ikke afbalanceret.
2. For at en streng skal være afbalanceret, skal parene med åbnings- og lukningsbeslag matche. Derfor ville det være sikkert at sige, at en inputstreng, hvis længde er ulige, ikke vil blive afbalanceret, da den vil indeholde mindst en ikke-matchet parentes.
3. I henhold til problemangivelsen skal den afbalancerede adfærd kontrolleres mellem parenteser. Derfor er enhver inputstreng, der indeholder ikke-parentes-tegn, en ubalanceret streng.

I betragtning af disse regler kan vi implementere valideringerne:

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

Nu hvor inputstrengen er valideret, kan vi gå videre til at løse dette problem.

5. Brug String.replaceAll Metode

I denne tilgang slår vi igennem inputstrengen ved at fjerne forekomster af “()”, “[]” og “{}” fra strengen ved hjælp af String.replaceAll. Vi fortsætter denne proces, indtil der ikke findes yderligere forekomster i inputstrengen.

Når processen er færdig, hvis længden af ​​vores streng er nul, er alle matchende par af parenteser blevet fjernet, og inputstrengen er afbalanceret. Hvis længden imidlertid ikke er nul, er der stadig nogle umatchede åbnings- eller lukningsbeslag i strengen. Derfor er inputstrengen ikke afbalanceret.

Lad os se den komplette implementering:

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

6. Brug Deque

Deque er en form for Kø der giver tilføj, hent og kig operationer i begge ender af køen. Vi vil udnytte bestillingsfunktionen Last-In-First-Out (LIFO) i denne datastruktur for at kontrollere balancen i inputstrengen.

Lad os først konstruere vores Deque:

Deque deque = ny LinkedList ();

Bemærk, at vi har brugt en LinkedList her, fordi det giver en implementering af Deque interface.

Nu hvor vores deque er konstrueret, løber vi gennem hvert tegn i inputstrengen en efter en. Hvis tegnet er et åbningsbeslag, tilføjer vi det som det første element i Deque:

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

Men hvis tegnet er en lukkende parentes, udfører vi nogle kontroller af LinkedList.

Først kontrollerer vi, om LinkedList er tom eller ej. En tom liste betyder, at lukkebeslaget ikke kan matches. Derfor er inputstrengen ikke afbalanceret. Så vi vender tilbage falsk.

Men hvis den LinkedList er ikke tom, så kigger vi på dens sidste karakter ved hjælp af kigFørst metode. Hvis det kan parres med lukningsbeslaget, fjerner vi dette øverste tegn fra liste bruger Fjern første metode og gå videre til den næste iteration af sløjfen:

hvis (! deque.isEmpty () && ((deque.peekFirst () == '{' && ch == '}') || (deque.peekFirst () == '[' && ch == ']') || (deque.peekFirst () == '(' && ch == ')'))) {deque.removeFirst (); } andet {returner falsk; }

Ved slutningen af ​​sløjfen kontrolleres alle tegn på balance, så vi kan vende tilbage rigtigt. Nedenfor er en komplet implementering af Deque baseret tilgang:

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

7. Konklusion

I denne vejledning diskuterede vi problemstillingen for Balanced Brackets og løste den ved hjælp af to forskellige tilgange.

Som altid er koden tilgængelig på Github.