streamalism.org

1. Oversikt

Balanserte parenteser, også kjent som Balanced Parentheses, er et vanlig programmeringsproblem.

I denne opplæringen vil vi validere om parentesene i en gitt streng er balansert eller ikke.

Denne typen strenger er en del av det som kalles Dyck-språket.

2. Problemstilling

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

Et sett med parenteser er anses å være et matchet par hvis en åpningsbrakett, “(“, “[“ Og “{“, oppstår til venstre for den tilsvarende lukkebraketten, “)”, “]” Og “}”, henholdsvis.

Imidlertid er en streng som inneholder brakettpar ikke balansert hvis braketten ikke følger med.

På samme måte, en streng som inneholder tegn som ikke er parentes som a-z, A-Z, 0-9 eller andre spesialtegn som #, $, @ regnes også som ubalansert.

For eksempel, hvis inngangen er “{[(])}”, lukker paret med firkantede parenteser, “[]”, en enkelt ubalansert åpningsrunde parentes, “(“. Tilsvarende er paret med runde parentes, “() ", Vedlegger en enkelt ubalansert, lukket firkantet parentes,"]. Dermed er inngangsstrengen "{[(])}" ubalansert.

Derfor sies det at en streng som inneholder parentestegn er balansert hvis:

1. En samsvarende åpningsbrakett oppstår til venstre for hver tilsvarende lukkebrakett
2. Braketter lukket i balanserte parenteser er også balanserte
3. Den inneholder ikke tegn som ikke er parentes

Det er et par spesielle tilfeller å huske på: null anses å være ubalansert, mens den tomme strengen anses å være balansert.

For ytterligere å illustrere vår definisjon av balanserte parenteser, la oss se noen eksempler på balanserte parenteser:

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

Og noen få som ikke er balansert:

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

Nå som vi har bedre forståelse av problemet vårt, la oss se hvordan vi kan løse det!

3. Løsningsmetoder

Det er forskjellige måter å løse dette problemet på. I denne opplæringen vil vi se på to tilnærminger:

1. Ved hjelp av metoder for String klasse
2. Ved hjelp av Deque gjennomføring

4. Grunnleggende oppsett og valideringer

La oss først lage en metode som kommer tilbake ekte hvis inngangen er balansert og falsk hvis inngangen er ubalansert:

offentlig boolsk isBalanced (String str)

La oss vurdere de grunnleggende valideringene for inngangsstrengen:

1. Hvis en null innspill er bestått, så er det ikke balansert.
2. For at en streng skal balanseres, bør parene med åpnings- og lukkeparenteser samsvare. Derfor ville det være trygt å si at en inngangsstreng hvis lengden er merkelig ikke vil bli balansert, da den vil inneholde minst en brakett som ikke samsvarer.
3. I henhold til problemstillingen, bør den balanserte oppførselen kontrolleres mellom parentes. Derfor er enhver inngangsstreng som inneholder tegn som ikke er parentes, en ubalansert streng.

Gitt disse reglene, kan vi implementere valideringene:

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

Nå som inngangsstrengen er validert, kan vi gå videre til å løse dette problemet.

5. Bruke String.replaceAll Metode

I denne tilnærmingen vil vi gå gjennom inngangsstrengen og fjerne forekomster av “()”, “[]” og “{}” fra strengen ved å bruke String.replaceAll. Vi fortsetter denne prosessen til det ikke blir funnet flere forekomster i inndatastrengen.

Når prosessen er fullført, hvis lengden på strengen vår er null, så er alle samsvarende par parenteser fjernet og inngangsstrengen balanseres. Hvis lengden imidlertid ikke er null, er det fremdeles noen uovertruffen åpnings- eller lukkeparenteser i strengen. Derfor er inngangsstrengen ubalansert.

La oss se den komplette implementeringen:

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

6. Bruke Deque

Deque er en form for Kø som gir tilleggs-, hentings- og tittoperasjoner i begge ender av køen. Vi vil utnytte best-funksjonen Last-In-First-Out (LIFO) i denne datastrukturen for å sjekke om balansen i inngangsstrengen er.

La oss først konstruere vår Deque:

Deque deque = ny LinkedList ();

Merk at vi har brukt a LinkedList her fordi det gir en implementering for Deque grensesnitt.

Nå som vår deque er konstruert, vil vi gå gjennom hvert tegn i inngangsstrengen en etter en. Hvis tegnet er et åpningsbrakett, vil vi legge det til som det første elementet i Deque:

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

Men hvis tegnet er en sluttbrakett, vil vi utføre noen kontroller på LinkedList.

Først sjekker vi om LinkedList er tom eller ikke. En tom liste betyr at lukkebraketten er uovertruffen. Derfor er inngangsstrengen ubalansert. Så vi kommer tilbake falsk.

Imidlertid, hvis LinkedList ikke er tom, så ser vi på den siste karakteren ved hjelp av kikk først metode. Hvis det kan pares med lukkebraketten, fjerner vi dette øverste tegnet fra liste bruker Fjern første metode og gå videre til neste iterasjon av løkken:

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

Ved slutten av løkken blir alle tegn balansekontrollert, slik at vi kan komme tilbake ekte. Nedenfor er en fullstendig implementering av Deque basert tilnærming:

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

7. Konklusjon

I denne opplæringen diskuterte vi problemstillingen til Balanced Brackets og løste den ved hjelp av to forskjellige tilnærminger.

Som alltid er koden tilgjengelig på Github.