Stakke til matchende parenteser
Validér parenteser med en stack
Stakke til matchende parenteser er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Sidst ind, først ud
En stak er en bunke, hvor det sidste element, du lægger på, er det første, du tager af igen, ligesom når du stabler tallerkener. 🍽️
Python-lister fungerer som stakke
I Python har du ikke brug for en særlig klasse. En almindelig liste fungerer allerede som en hurtig, klar-til-brug-stak til konkurrencer.
stack = []Skub ind med append
Hvis du vil lægge et element øverst på stakken, kalder du append, som placerer værdien sidst i listen på O(1)-tid.
stack.append('(')
stack.append('[')Tag det øverste element med pop
Når du kalder pop uden et indeks, fjerner og returnerer den det sidste element, altså det element, der senest blev lagt på stakken.
top = stack.pop() # removes '['Se uden at fjerne
Hvis du vil se det øverste element uden at tage det af, skal du blot læse stack[-1]. Dette kig er nyttigt, før du beslutter dig for at bruge pop.
if stack:
top = stack[-1]Tjek altid, om den er tom
Hvis du fjerner et element fra en tom stak, opstår der en fejl. Beskyt hvert kald af pop ved først at tjekke if stack, så din løsning aldrig går ned.
Idéen bag matchning af parenteser
Parenteser kan indlejres perfekt, så her er en stak oplagt. Læg hver åbningsparentes på stakken, og en lukningsparentes skal passe med stakkens øverste element.
Knyt lukning til åbning
Brug en lille ordbog, der knytter hver lukningsparentes til den åbningsparentes, den forventer, så kontrollen forbliver enkel.
pairs = {')': '(', ']': '[', '}': '{'}Gennemgå og afgør
Gennemgå strengen én gang. Læg åbningsparenteser på stakken, og sammenlign ved en lukningsparentes med det øverste element, du har taget af, ved hjælp af dit pairs-kort.
for c in s:
if c in pairs.values():
stack.append(c)Uoverensstemmelse betyder ugyldig
Hvis den åbningsparentes, du tager af stakken, ikke passer, eller stakken er tom, når du har brug for den, er strengen straks ugyldig.
elif not stack or stack.pop() != pairs[c]:
return FalseTom stak til sidst
En åbningsparentes, der er tilbage efter gennemgangen, betyder, at noget aldrig blev lukket. Strengen er kun gyldig, når stakken til sidst er tom.
return not stackHurtigt tjek
Du validerer parenteser med en stak. Hvad fortæller en ikke-tom stak helt til sidst?
Opsummering: Stakke tæmmer parenteser
Du har lært, at en liste fungerer som en stak: Læg åbningsparenteser på, tag dem af ved lukningsparenteser, og en tom stak til sidst betyder, at de er korrekt matchet. Godt gået! 🎉
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Stakke til matchende parenteser” gratis?
Ja — hele teksten til “Stakke til matchende parenteser” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Stakke til matchende parenteser”?
Validér parenteser med en stack Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Stakke til matchende parenteser”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Stakke til matchende parenteser
- Monoton stack: næste større element
- Køer og collections.deque
- Maksimum i et glidende vindue med deque