Verificarea parantezelor returnează True pentru „((” (stiva rămâne nevidă)
Funcția verifică doar parantezele închise, dar la final nu verifică dacă au rămas paranteze deschise în stivă. Înlocuiește return True de la final cu return not stiva (sau len(stiva) == 0).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Algoritmul clasic cu stivă: pui fiecare paranteză deschisă pe stivă, iar la una închisă scoți vârful și verifici că se potrivesc. Codul tratează corect (] și )(, dar uită ultimul pas: un text e echilibrat doar dacă stiva e goală la final. Pentru (( sau ([], nicio paranteză închisă nu dă greș, bucla se termină, iar funcția returnează True.
Nu e o eroare a lui Python, ci un rezultat greșit pe un caz limită pe care testele îl verifică aproape întotdeauna. În „Repară tu”, testul cu assert afișează textul și rezultatul.
Aceeași omisiune apare la alte probleme cu stivă: validarea tag-urilor HTML, evaluarea expresiilor, simplificarea căilor de fișiere. Gândește-te mereu ce înseamnă „au rămas elemente” la sfârșit.
De ce apare: cauzele frecvente
1Lipsește verificarea de la final
for ch in s:
...
return Truefor ch in s:
...
return not stivanot stiva e True doar dacă lista e goală, adică toate parantezele deschise au fost închise.
2Pop pe stivă goală, apoi corectat greșit
if stiva and stiva.pop() != pereche[ch]:
return Falseif not stiva or stiva.pop() != pereche[ch]:
return FalsePrima variantă evită eroarea la ), dar acceptă textul. O paranteză închisă fără pereche înseamnă că textul nu e echilibrat.
Repară eroarea, direct în pagină
Funcția echilibrat(s) verifică dacă parantezele (), [] și {} dintr-un text sunt echilibrate. Testul cu assert pică pentru ((. Repar-o ca testele să treacă și să afișeze True, False, False și True.
def echilibrat(s):
pereche = {')': '(', ']': '[', '}': '{'}
stiva = []
for ch in s:
if ch in '([{':
stiva.append(ch)
elif ch in pereche:
if not stiva or stiva.pop() != pereche[ch]:
return False
return True
for s, corect in [('{[()]}', True), ('(]', False), ('((', False), ('', True)]:
rez = echilibrat(s)
assert rez == corect, f'paranteze gresit pentru {s!r}: {rez}'
print(rez)True False False True
Indiciu
La final, textul e echilibrat doar dacă nu a rămas nimic în stivă.
Reparația
def echilibrat(s):
pereche = {')': '(', ']': '[', '}': '{'}
stiva = []
for ch in s:
if ch in '([{':
stiva.append(ch)
elif ch in pereche:
if not stiva or stiva.pop() != pereche[ch]:
return False
return not stiva
for s, corect in [('{[()]}', True), ('(]', False), ('((', False), ('', True)]:
rez = echilibrat(s)
assert rez == corect, f'paranteze gresit pentru {s!r}: {rez}'
print(rez)De ce merge
Pentru ((, ambele paranteze ajungeau pe stivă, nu urma nicio închidere care să dea greș, iar funcția returna True. return not stiva adaugă condiția lipsă: la final, fiecare paranteză deschisă trebuie să fi fost închisă, deci stiva trebuie să fie goală. Textul gol rămâne corect, pentru că stiva e goală de la început.
Cum o eviți pe viitor
La orice algoritm cu stivă, scrie explicit trei cazuri: ce faci la deschidere, ce faci la închidere (inclusiv cu stiva goală) și ce înseamnă stiva la final. Testează mereu cu: textul gol (True), doar deschideri (((), doar o închidere ()), perechi greșite ((]) și un exemplu corect imbricat ({[()]}).
Întrebări frecvente
Merge și doar cu un contor, fără stivă?
Doar dacă ai un singur tip de paranteze. Cu (), [] și {} ai nevoie de stivă, pentru că ([)] are contoarele corecte, dar nu e echilibrat.
Ce complexitate are?
O(n) timp și O(n) memorie în cel mai rău caz, când toate caracterele sunt paranteze deschise.
Erori înrudite
IndexError: pop from empty list Ai apelat stiva.pop() pe o stivă goală. La verificarea parantezelor înseamnă de obicei o paranteză închisă fără pereche. Verifică înainte cu if not stiva: (și tratează cazul) sau pune condiția în while stiva and ... KeyError: 'a' la frecv[litera] += 1 frecv[litera] += 1 citește întâi valoarea cheii, iar la prima apariție a literei cheia nu există încă. Folosește frecv[litera] = frecv.get(litera, 0) + 1, un defaultdict(int) sau direct Counter(text). Inversarea listei înlănțuite pierde noduri (curent.urm suprascris înainte de avans) Ai schimbat curent.urm = anterior înainte să salvezi următorul nod, iar apoi curent = curent.urm te duce înapoi, nu înainte. Salvează întâi urmator = curent.urm, abia apoi întoarce legătura și avansează cu curent = urmator. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
