Stack per le parentesi corrispondenti
Convalidare le parentesi con uno stack
Stack per le parentesi corrispondenti è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Ultimo entrato, primo uscito
Uno stack è una pila in cui l'ultimo elemento aggiunto è il primo a essere rimosso, proprio come una pila di piatti. 🍽️
Le liste Python sono stack
In Python non serve una classe speciale. Una semplice list funziona già come uno stack rapido e pronto all'uso nelle gare di programmazione.
stack = []Inserire con append
Per aggiungere un elemento in cima allo stack, chiami append, che inserisce il valore alla fine della lista in tempo O(1).
stack.append('(')
stack.append('[')Estrarre dalla cima
La chiamata a pop senza indice rimuove e restituisce l'ultimo elemento, cioè quello inserito più di recente nello stack.
top = stack.pop() # removes '['Consultare senza rimuovere
Per guardare l'elemento in cima senza rimuoverlo, legga semplicemente stack[-1]. Questa operazione di consultazione è utile prima di decidere se eseguire pop.
if stack:
top = stack[-1]Controllare sempre se è vuoto
Eseguire pop su uno stack vuoto genera un errore. Protegga ogni pop controllando prima if stack, così la soluzione non andrà mai in errore.
L'idea del controllo delle parentesi
Le parentesi si annidano perfettamente, quindi sono un caso ideale per uno stack. Inserisca ogni parentesi di apertura e una parentesi di chiusura dovrà corrispondere all'elemento in cima allo stack.
Associare la chiusura all'apertura
Utilizzi un piccolo dizionario che associ ogni parentesi di chiusura alla parentesi di apertura prevista, così i controlli restano chiari.
pairs = {')': '(', ']': '[', '}': '{'}Scansionare e decidere
Scorra la stringa una sola volta. Inserisca nello stack le parentesi di apertura e, davanti a una parentesi di chiusura, la confronti con l'elemento estratto dalla cima usando la mappa pairs.
for c in s:
if c in pairs.values():
stack.append(c)Una mancata corrispondenza significa non valido
Se la parentesi di apertura estratta non corrisponde, oppure lo stack è vuoto quando serve un elemento, la stringa è subito non valida.
elif not stack or stack.pop() != pairs[c]:
return FalseStack vuoto alla fine
Dopo la scansione, una parentesi di apertura rimasta nello stack significa che qualcosa non è mai stato chiuso. La stringa è valida solo quando lo stack è finalmente vuoto.
return not stackVerifica rapida
Sta verificando le parentesi con uno stack. Che cosa indica uno stack non vuoto alla fine?
Riepilogo: gli stack domano le parentesi
Ha imparato che una list funziona come uno stack: inserisca le parentesi di apertura, estragga quelle di chiusura e, se lo stack è vuoto alla fine, le parentesi sono bilanciate. Ottimo lavoro! 🎉
Domande Frequenti
La lezione «Stack per le parentesi corrispondenti» è gratuita?
Sì — il testo completo di «Stack per le parentesi corrispondenti» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Stack per le parentesi corrispondenti»?
Convalidare le parentesi con uno stack Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Stack per le parentesi corrispondenti»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stack per le parentesi corrispondenti
- Stack monotono: elemento successivo maggiore
- Code e collections.deque
- Massimo di una finestra scorrevole con Deque