streamalism.org

1. Pregled

Uravnotežene zagrade, poznate i kao uravnotežene zagrade, čest je problem programiranja.

U ovom uputstvu provjerit ćemo jesu li zagrade u određenom nizu uravnotežene ili ne.

Ova vrsta žica dio je onoga što je poznato kao jezik Dyck.

2. Izjava o problemu

Zagradom se smatra bilo koji od sljedećih znakova - "(", ")", "[", "]", "{", "}".

Skup zagrada je smatra se podudarnim parom ako je otvorni nosač, “(“, “[“ I “{“, javlja se lijevo od odgovarajuće zagrade, “)”, “]”, Odnosno “}”.

Međutim, niz koji sadrži parove zagrada je nije uravnoteženo ako se skup zagrada koje zatvara ne podudara.

Slično tome, niz koji sadrži znakove koji nisu zagrade poput a-z, A-Z, 0-9 ili drugih posebnih znakova poput #, $, @ također se smatra neuravnoteženim.

Na primjer, ako je ulaz "{[(])}", par uglatih zagrada, "[]", zatvara jedan neuravnoteženi otvorni zagradni otvor, "(". Slično tome, par okruglih zagrada, "() ", Zatvara jednu neuravnoteženu zatvarajuću uglatu zagradu,"] ". Stoga je ulazni niz" {[(])} "neuravnotežen.

Stoga se za niz koji sadrži zagradne znakove kaže da je uravnotežen ako:

1. Odgovarajući nosač za otvaranje javlja se lijevo od svakog odgovarajućeg nosača za zatvaranje
2. Zagrade zatvorene u uravnotežene zagrade također su uravnotežene
3. Ne sadrži znakove koji nisu zagrade

Imajte na umu nekoliko posebnih slučajeva: null smatra se neuravnoteženim, dok se prazan niz smatra uravnoteženim.

Da bismo dodatno ilustrirali našu definiciju uravnoteženih zagrada, pogledajmo nekoliko primjera uravnoteženih zagrada:

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

I nekoliko koji nisu uravnoteženi:

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

Sad kad bolje razumijemo svoj problem, pogledajmo kako ga riješiti!

3. Pristupi rješenju

Postoje različiti načini rješavanja ovog problema. U ovom uputstvu razmotrit ćemo dva pristupa:

1. Korištenjem metoda Niz razred
2. Koristeći Deque provedba

4. Osnovno postavljanje i provjere valjanosti

Napravimo prvo metodu koja će se vratiti pravi ako je unos uravnotežen i lažno ako je unos neuravnotežen:

javna logička vrijednost isBalanced (niz str)

Razmotrimo osnovne provjere valjanosti ulaznog niza:

1. Ako je a null unos je prošao, onda nije uravnotežen.
2. Da bi žica bila uravnotežena, parovi zagrada za otvaranje i zatvaranje trebali bi se podudarati. Stoga bi bilo sigurno reći da ulazni niz čija je duljina neparna neće biti uravnotežen jer će sadržavati barem jednu nepodudarnu zagradu.
3. Prema izjavi problema, uravnoteženo ponašanje treba provjeriti u zagradama. Stoga je svaki ulazni niz koji sadrži znakove koji nisu zagrade neuravnoteženi niz.

S obzirom na ova pravila, možemo provesti provjere valjanosti:

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

Sada kada je ulazni niz provjeren, možemo prijeći na rješavanje ovog problema.

5. Korištenje String.replaceAll Metoda

U ovom ćemo pristupu provući kroz ulazni niz uklanjajući pojave “()”, “[]” i “{}” iz niza pomoću String.replaceAll. Nastavljamo ovaj postupak dok se u ulaznom nizu ne nađu daljnje pojave.

Kad je postupak dovršen, ako je duljina niza jednaka nuli, uklonjeni su svi odgovarajući parovi zagrada, a ulazni niz uravnotežen. Ako, međutim, duljina nije nula, tada su u nizu još uvijek prisutne neke neusporedive zagrade za otvaranje ili zatvaranje. Stoga je ulazni niz neuravnotežen.

Pogledajmo cjelovitu implementaciju:

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

6. Korištenje Deque

Deque je oblik Red koji pruža operacije dodavanja, dohvaćanja i zavirivanja na oba kraja reda. Za provjeru stanja u ulaznom nizu iskoristit ćemo značajku narudžbe Last-In-First-Out (LIFO) ove strukture podataka.

Prvo, konstruirajmo svoje Deque:

Deque deque = novi LinkedList ();

Imajte na umu da smo koristili a LinkedList ovdje jer pruža implementaciju za Deque sučelje.

Sad to naše deque je konstruiran, petlju ćemo prolaziti kroz svaki znak ulaznog niza jedan po jedan. Ako je znak otvorna zagrada, tada ćemo ga dodati kao prvi element u Deque:

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

Ali, ako je znak završna zagrada, tada ćemo izvršiti neke provjere na LinkedList.

Prvo provjeravamo je li LinkedList je prazan ili nije. Prazan popis znači da je zatvarajući nosač neusporediv. Stoga je ulazni niz neuravnotežen. Pa se vraćamo lažno.

Međutim, ako je LinkedList nije prazno, tada zavirujemo u njegov posljednji znak koristeći zaviritiPrvo metoda. Ako se može upariti sa zagradom za zatvaranje, tada uklanjamo ovaj gornji znak iz popis koristiti uklonitiPrvo metodu i prijeđite na sljedeću iteraciju petlje:

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

Na kraju petlje svi znakovi se provjeravaju ravnotežom, tako da se možemo vratiti pravi. Ispod je cjelovita implementacija Deque zasnovan pristup:

Deque deque = novi LinkedList (); za (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. Zaključak

U ovom vodiču razgovarali smo o problemu uravnoteženih zagrada i riješili ga pomoću dva različita pristupa.

Kao i uvijek, kôd je dostupan na Githubu.