Stakker for samsvarende parenteser
Valider parenteser med en stakk
Stakker for samsvarende parenteser er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Sist inn, først ut
En stakk er en bunke der det siste elementet du legger til, er det første du tar ut, akkurat som når du stabler tallerkener. 🍽️
Python-lister fungerer som stabler
I Python trenger du ikke en egen klasse. En vanlig list fungerer allerede som en rask og ferdig stakk i konkurranseprogrammering.
stack = []Legg til med append
For å legge et element øverst i stakken kaller du append, som legger verdien til på slutten av listen på O(1)-tid.
stack.append('(')
stack.append('[')Ta ut fra toppen
Når du kaller pop uten en indeks, fjernes og returneres det siste elementet – det som sist ble lagt på stakken.
top = stack.pop() # removes '['Se på toppen uten å fjerne
For å se på elementet øverst uten å ta det ut leser du bare stack[-1]. Dette er nyttig før du bestemmer deg for å bruke pop.
if stack:
top = stack[-1]Sjekk alltid om stakken er tom
Hvis du prøver å ta et element fra en tom stakk, oppstår det en feil. Beskytt hvert pop-kall ved først å sjekke if stack, slik at løsningen ikke krasjer.
Ideen bak parentesmatching
Parenteser nøstes perfekt, så en stakk passer godt. Legg alle åpningsparenteser på stakken, og la en lukkende parentes samsvare med toppen av stakken.
Knytt lukkende til åpnende
Bruk en liten dictionary som kobler hver lukkende parentes til åpningsparentesen den forventer, slik at kontrollene blir ryddige.
pairs = {')': '(', ']': '[', '}': '{'}Gå gjennom og avgjør
Gå gjennom strengen én gang. Legg åpningsparenteser på stakken, og sammenlign en lukkende parentes med toppen du tar av, ved hjelp av pairs-kartet.
for c in s:
if c in pairs.values():
stack.append(c)Ulikhet betyr ugyldig
Hvis åpningsparentesen du tok av, ikke samsvarer, eller stakken er tom når du trenger den, er strengen ugyldig med én gang.
elif not stack or stack.pop() != pairs[c]:
return FalseTom stakk til slutt
En åpningsparentes som ligger igjen etter gjennomgangen, betyr at noe aldri ble lukket. Strengen er bare gyldig når stakken til slutt er tom.
return not stackHurtigsjekk
Du validerer parenteser med en stakk. Hva forteller en stakk som ikke er tom helt til slutt?
Oppsummering: Stabler temmer parenteser
Du har lært at en liste fungerer som en stakk: Legg åpningsparenteser på stakken, ta dem av for lukkende parenteser, og en tom stakk til slutt betyr at parentesene er balanserte. Godt jobbet! 🎉
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Stakker for samsvarende parenteser» gratis?
Ja – hele teksten i «Stakker for samsvarende parenteser» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Stakker for samsvarende parenteser»?
Valider parenteser med en stakk Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Stakker for samsvarende parenteser»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Stakker for samsvarende parenteser
- Monoton stakk: neste større element
- Køer og collections.deque
- Maksimum i et skyvevindu med deque