streamalism.org

1. Prehľad

Vyvážené zátvorky, tiež známe ako vyvážené zátvorky, sú bežným programovacím problémom.

V tomto tutoriáli overíme, či sú zátvorky v danom reťazci vyvážené alebo nie.

Tento typ strún je súčasťou toho, čo je známe ako jazyk Dyck.

2. Vyhlásenie o probléme

Za zátvorku sa považuje akýkoľvek z nasledujúcich znakov - „(“, “)“, „[“, „]“, „{“, „}“.

Sada zátvoriek je sa považuje za párový pár, ak sa otváracia konzola, “(„, “[“ A „{“, sa vyskytuje naľavo od príslušnej zatváracej zátvorky, „)“, „]“ A „}“.

Reťazec obsahujúci páry zátvoriek však je nie je vyvážené, ak sada zátvoriek, ktoré obsahuje, nie je v zhode.

Podobne reťazec obsahujúci znaky bez zátvoriek ako a-z, A-Z, 0-9 alebo iné špeciálne znaky ako #, $, @ sa tiež považuje za nevyváženú.

Napríklad ak je vstup „{[(])}“, dvojica hranatých zátvoriek „[]“ ohraničuje jednu nevyváženú otváraciu okrúhlu zátvorku „((. Podobne, dvojica okrúhlych zátvoriek„ ()) ”, Uzatvára jednu nevyváženú uzatváraciu hranatú zátvorku,“] ”. Vstupný reťazec„ {[(])} “je teda nevyvážený.

Preto sa hovorí, že reťazec obsahujúci znaky zátvorky je vyvážený, ak:

1. Zodpovedajúca otváracia konzola sa nachádza naľavo od každej zodpovedajúcej zatváracej konzoly
2. Konzoly uzavreté vo vyvážených zátvorkách sú tiež vyvážené
3. Neobsahuje žiadne znaky, ktoré nie sú v zátvorkách

Je potrebné pamätať na niekoľko zvláštnych prípadov: nulový sa považuje za nevyvážený, zatiaľ čo prázdny reťazec sa považuje za nevyvážený.

Na ďalšiu ilustráciu našej definície vyvážených zátvoriek si ukážeme niekoľko príkladov vyvážených zátvoriek:

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

A niekoľko nevyvážených:

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

Teraz, keď lepšie rozumieme nášmu problému, pozrime sa, ako ho vyriešiť!

3. Prístupy k riešeniu

Tento problém možno vyriešiť rôznymi spôsobmi. V tomto výučbe sa pozrieme na dva prístupy:

1. Pomocou metód String trieda
2. Použitím Deque implementácia

4. Základné nastavenie a validácie

Najprv si vytvorme metódu, ktorá sa vráti pravda ak je vstup vyvážený a nepravdivé ak je vstup nevyvážený:

public boolean isBalanced (String str)

Uvažujme o základných validáciách vstupného reťazca:

1. Ak nulový vstup je odovzdaný, potom nie je vyvážený.
2. Aby bola šnúra vyvážená, mali by sa zhodovať páry otváracích a zatváracích zátvoriek. Dalo by sa teda s istotou povedať, že vstupný reťazec, ktorého dĺžka je nepárna, nebude vyvážený, pretože bude obsahovať minimálne jednu nezhodnú zátvorku.
3. Podľa vyhlásenia o probléme treba vyvážené správanie skontrolovať v zátvorkách. Preto je každý vstupný reťazec obsahujúci znaky bez hranatej zátvorky nevyvážený reťazec.

Na základe týchto pravidiel môžeme implementovať validácie:

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

Teraz, keď je vstupný reťazec overený, môžeme prejsť k riešeniu tohto problému.

5. Používanie String.nahradiťVšetko Metóda

V tomto prístupe urobíme slučku cez vstupný reťazec a odstránime z reťazca výskyty „()“, „[]“ a „{}“ pomocou String.nahradiťVšetko. V tomto procese pokračujeme, kým sa vo vstupnom reťazci nenájdu ďalšie výskyty.

Po dokončení procesu, ak je dĺžka nášho reťazca nulová, boli odstránené všetky zodpovedajúce páry zátvoriek a vstupný reťazec je vyvážený. Ak však dĺžka nie je nula, potom sú v reťazci stále nejaké neprekonateľné zátvorky alebo zátvorky. Preto je vstupný reťazec nevyvážený.

Pozrime sa na kompletnú implementáciu:

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

6. Používanie Deque

Deque je forma Fronta ktorá poskytuje operácie pridávania, načítania a prehliadania na oboch koncoch frontu. Na kontrolu zostatku vo vstupnom reťazci využijeme funkciu objednávky Last-In-First-Out (LIFO) tejto dátovej štruktúry.

Najprv si zostrojme našu Deque:

Deque deque = nový LinkedList ();

Všimnite si, že sme použili a LinkedList tu, pretože poskytuje implementáciu pre Deque rozhranie.

Teraz, keď naše deque je konštruovaný, budeme postupne prechádzať každý znak vstupného reťazca. Ak je znak otváracou zátvorkou, pridáme ho ako prvý prvok do Deque:

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

Ale ak je znak zatváracia zátvorka, vykonáme niekoľko kontrol na LinkedList.

Najskôr skontrolujeme, či LinkedList je prázdny alebo nie. Prázdny zoznam znamená, že zatváracia konzola je neprekonateľná. Preto je vstupný reťazec nevyvážený. Takže sa vraciame nepravdivé.

Ak však LinkedList nie je prázdny, potom nakukneme na jeho posledný znak pomocou nahliadnuťPrvé metóda. Ak sa dá spárovať s uzatváracou zátvorkou, odstránime tento najhornejší znak z zoznam pomocou removeFirst a prejdite na ďalšiu iteráciu slučky:

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

Na konci cyklu sú všetky znaky skontrolované na vyváženie, aby sme sa mohli vrátiť pravda. Nižšie je uvedená úplná implementácia Deque založený prístup:

Deque deque = nový LinkedList (); pre (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. Záver

V tomto tutoriáli sme diskutovali o problémovom vyjadrení Balanced Brackets a vyriešili sme ho pomocou dvoch rôznych prístupov.

Ako vždy, kód je k dispozícii na stránkach Github.