Le normali sequenze di parentesi sono costituite da parentesi di apertura e chiusura di uno o più tipi, con ciascuna parentesi di apertura che ha una parentesi di chiusura e (nel caso di più tipi) i loro tipi non si sovrappongono.
SP corretto:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP non valido:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Per verificare se una sequenza di parentesi quadre è dello stesso tipo, basta controllare il bilanciamento.
Cioè, iniziamo una variabile uguale a zero (saldo). Quindi percorriamo la stringa (se non sai come farlo - CORRI, STUPIDO!), aumentando il saldo quando incontra la parentesi di apertura e diminuendolo quando incontra quella di chiusura. Se in qualsiasi momento il saldo diventa negativo o alla fine non è uguale a zero, allora la sequenza è sbagliata.
|
Nel caso della presenza di parentesi di più tipi, tutto diventa un po' più complicato. Creiamo uno stack che funga da variabile di equilibrio. Questo è necessario perché le parentesi non possono sovrapporsi. Quando percorriamo una riga e incontriamo una parentesi di apertura, la mettiamo in pila. Quando incontriamo una parentesi graffa di chiusura, proviamo a estrarre la parentesi graffa di apertura di quel tipo dallo stack. Se nello stack è presente una parentesi graffa di tipo diverso, la sequenza non è valida. Se lo stack non è vuoto alla fine, anche la sequenza non è valida.
|
La generazione di sequenze di parentesi corrette segue direttamente dal modo in cui viene eseguito il controllo: dobbiamo solo aggiungere nuove parentesi senza violare la correttezza. Questo viene fatto mediante iterazione ricorsiva. Se non lo conosci - BE... ah, no, puoi provare a capire leggendo oltre. Ecco un esempio di codice per un tipo di parentesi:
#include <vettore>
#include <iostream>
utilizzando spazio dei nomi std;
int n; // Mezza lunghezza
vettore<carattere> ans; // La nostra risposta
void rec(int saldo) {
if (ans.size() == 2 * n) { // Se lo fa, allora siamo fatto < /span>
for (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Controlla, noi provvediamo a chiudere la nuova parentesi graffa di apertura
// Ora fai attenzione: non abbiamo bisogno di creare un vettore separato per ogni sequenza
ans.push_back('(');
rec(saldo + 1);
ans.pop_back(); // Per capirlo, devi essere consapevole della ricorsione. Innanzitutto, aggiungiamo una parentesi al vettore, quindi eseguiamo nuovamente tutto questo codice.
// Ovvero, aggiungi di nuovo una parentesi, se possibile.
// E questo accadrà finché non inizieremo a lasciare la ricorsione, cioè finché non raggiungeremo la lunghezza desiderata.
// Quindi le parentesi inizieranno a essere rimosse. Se lo capisci, mi congratulo con te, sei fantastico.
}
if (balance > 0) { // Se possiamo chiudere una parentesi, la chiudiamo.
ans.push_back(')');
rec(saldo - 1);
ans.pop_back();
}
}
int main()
{
cin>> N;
rec(0);
ritorno 0;
}
E ora è il momento delle difficoltà: dovrai scrivere TU STESSO l'algoritmo per diversi tipi di parentesi! Muahahahahahahahahahahahaha!
|