Stacks voor overeenkomende haakjes

Een stack is een stapel waarbij het laatste element dat je toevoegt het eerste is dat je verwijdert, net als bij opgestapelde borden. 🍽️

In Python heb je geen speciale klasse nodig. Een gewone lijst werkt al als een snelle, kant-en-klare stack voor wedstrijden.

Om een element boven op de stack toe te voegen, roep je append aan. Die methode plaatst de waarde in O(1)-tijd aan het einde van de lijst.

Als je pop zonder index aanroept, wordt het laatste element verwijderd en teruggegeven: het element dat het meest recent aan de stack is toegevoegd.

Als je het bovenste element wilt bekijken zonder het weg te halen, lees je gewoon stack[-1]. Dit is handig voordat je besluit om pop aan te roepen.

Een lege stack verwijderen veroorzaakt een foutmelding. Controleer vóór elke pop eerst if stack, zodat je oplossing nooit crasht.

Haakjes nesten perfect, dus een stack ligt voor de hand. Voeg elk openend haakje toe en laat elk sluitend haakje overeenkomen met de bovenkant van de stack.

Houd een klein woordenboek bij dat elk sluitend haakje koppelt aan het openende haakje dat erbij hoort, zodat de controles duidelijk blijven.

Doorloop de tekenreeks één keer. Voeg openende haakjes toe en vergelijk bij een sluitend haakje het verwijderde bovenste element met je pairs-koppeling.

Als het verwijderde openende haakje niet overeenkomt, of de stack leeg is wanneer je die nodig hebt, is de tekenreeks meteen ongeldig.

Een overgebleven openend haakje betekent na het doorlopen dat iets nooit is gesloten. De tekenreeks is alleen geldig wanneer de stack uiteindelijk leeg is.

Je hebt geleerd dat een lijst als stack werkt: voeg openende haakjes toe, verwijder elementen bij sluitende haakjes en zorg dat de stack aan het einde leeg is. Goed gedaan! 🎉