streamalism.org

1. Áttekintés

A kiegyensúlyozott zárójelek, más néven kiegyensúlyozott zárójelek, gyakori programozási probléma.

Ebben az oktatóanyagban ellenőrizni fogjuk, hogy az adott karakterlánc zárójelei kiegyensúlyozottak-e vagy sem.

Az ilyen típusú karakterláncok a Dyck nyelv néven ismertek.

2. Probléma-kimutatás

Zárójel a következő karakterek bármelyikének tekinthető - „(“, “)”, „[“, “]”, “{“, “}”.

A zárójelek egy párosított párnak tekinthető, ha nyitó zárójel, „(„, „[“ És „{“, a megfelelő zárójel bal oldalán található, „)”, „]” És „}”.

A zárójelpárokat tartalmazó karakterlánc azonban az nem kiegyensúlyozott, ha az általa körülvett zárójel-készlet nem egyezik.

Hasonlóképpen, nem zárójeles karaktereket tartalmazó karakterlánc mint a-z, A-Z, 0-9 vagy más speciális karakterek, például #, $, @ szintén kiegyensúlyozatlannak tekinthető.

Például, ha a bemenet „{[(])}”, akkor a szögletes zárójelek („[]”) egyetlen kiegyensúlyozatlan nyitó kerek zárójelet tartalmaznak („. Hasonlóképpen, a kerek zárójelek párja, ”, Egyetlen kiegyensúlyozatlan záró szögletes zárójelet tartalmaz,„]. Így a „{[(])}” bemeneti karakterlánc kiegyensúlyozatlan.

Ezért a zárójeles karaktereket tartalmazó karakterlánc kiegyensúlyozottnak mondható, ha:

1. Minden megfelelő zárójel bal oldalán egy megfelelő nyitó konzol található
2. A kiegyensúlyozott zárójelek közé zárt tartók kiegyensúlyozottak is
3. Nem tartalmaz nem zárójeles karaktereket

Néhány különleges esetet érdemes szem előtt tartani: nulla kiegyensúlyozatlannak, míg az üres húr kiegyensúlyozottnak tekinthető.

A kiegyensúlyozott zárójelek meghatározásának további szemléltetéséhez nézzünk néhány példát a kiegyensúlyozott zárójelekre:

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

És néhány nem kiegyensúlyozott:

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

Most, hogy jobban megértsük problémánkat, nézzük meg, hogyan lehet megoldani!

3. Megoldás megközelítések

Különböző módon lehet megoldani ezt a problémát. Ebben az oktatóanyagban két megközelítést vizsgálunk meg:

1. A Húr osztály
2. Használata Deque végrehajtás

4. Alapbeállítások és ellenőrzések

Először hozzunk létre egy módszert, amely visszatér igaz ha a bemenet kiegyensúlyozott és hamis ha a bemenet kiegyensúlyozatlan:

nyilvános logikai érték kiegyensúlyozott (String str)

Vizsgáljuk meg a bemeneti karakterlánc alapvető érvényesítéseit:

1. Ha egy nulla az input átadva van, akkor nem kiegyensúlyozott.
2. A húr kiegyensúlyozása érdekében a nyitó és záró zárójel párjának meg kell egyeznie. Ezért biztos lehet azt mondani, hogy a páratlan hosszúságú bemeneti karakterlánc nem lesz kiegyensúlyozott, mivel legalább egy nem illesztett zárójelet tartalmaz.
3. A probléma megállapításának megfelelően a kiegyensúlyozott viselkedést zárójelek között kell ellenőrizni. Ezért minden nem zárójeles karaktert tartalmazó beviteli karakterlánc kiegyensúlyozatlan karakterlánc.

Ezeket a szabályokat figyelembe véve megvalósíthatjuk az érvényesítéseket:

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

Most, hogy a bemeneti karakterlánc érvényesült, továbbléphetünk a probléma megoldására.

5. Használata String.replaceAll Módszer

Ebben a megközelítésben végigvezetjük a bemeneti karakterláncot, eltávolítva a karakterláncból a ( String.replaceAll. Addig folytatjuk ezt a folyamatot, amíg további előfordulásokat nem találunk a beviteli karakterláncban.

Ha a folyamat befejeződött, ha a karakterláncunk hossza nulla, akkor az összes megfelelő zárójelpár eltávolításra került, és a bemeneti karakterlánc kiegyensúlyozott. Ha azonban a hossz nem nulla, akkor néhány páratlan nyitó vagy záró zárójel még mindig jelen van a húrban. Ezért a bemeneti karakterlánc kiegyensúlyozatlan.

Lássuk a teljes megvalósítást:

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

6. Használata Deque

Deque a Sor amely a sor mindkét végén hozzáadási, visszakeresési és bekukkantási műveleteket biztosít. Kihasználjuk ennek az adatstruktúrának a Last-In-First-Out (LIFO) rendelési funkcióját, hogy ellenőrizzük a bemeneti karakterlánc egyensúlyát.

Először állítsuk össze a sajátunkat Deque:

Deque deque = új LinkedList ();

Vegye figyelembe, hogy a LinkedList itt, mert megvalósítást nyújt a Deque felület.

Most, hogy a mi deque felépítésre kerül, a bemeneti karakterlánc minden egyes karakterét egyesével hurcoljuk. Ha a karakter nyitó zárójel, akkor hozzáadjuk az első elemként a Deque:

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

De, ha a karakter záró zárójel, akkor néhány ellenőrzést végrehajtunk a LinkedList.

Először ellenőrizzük, hogy a LinkedList üres vagy sem. Egy üres lista azt jelenti, hogy a záró konzol páratlan. Ezért a bemeneti karakterlánc kiegyensúlyozatlan. Tehát visszatérünk hamis.

Ha azonban a LinkedList nem üres, akkor a kukucskáljElőször módszer. Ha a záró zárójelhez párosítható, akkor eltávolítjuk ezt a legfelső karaktert a lista használni a removeFirst metódust, és lépjen a hurok következő iterációjára:

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

A ciklus végére az összes karakter egyensúlyban van, így visszatérhetünk igaz. Az alábbiakban bemutatjuk a Deque alapú megközelítés:

Deque deque = új LinkedList (); mert (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;}}} true true;

7. Következtetés

Ebben az oktatóanyagban megvitattuk a Kiegyensúlyozott zárójelek problémamegállapítását, és két különböző megközelítéssel oldottuk meg.

Mint mindig, a kód elérhető a Githubon.