Las secuencias regulares de paréntesis consisten en paréntesis de apertura y cierre de uno o más tipos, cada paréntesis de apertura tiene un paréntesis de cierre y (en el caso de varios tipos) sus tipos no se superponen.
SP correcto:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP no válido:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Para verificar si una secuencia de corchetes es del mismo tipo, solo verifique el saldo.
Es decir, partimos de una variable igual a cero (saldo). Luego repasamos la cadena (si no sabes cómo hacerlo, ¡CORRE, ESTÚPIDO!), aumentando el saldo cuando se encuentra con el paréntesis de apertura y disminuyéndolo cuando se encuentra con el de cierre. Si en algún momento el saldo se vuelve negativo o al final no es igual a cero, entonces la secuencia es incorrecta.
|
En el caso de la presencia de brackets de varios tipos, todo se vuelve un poco más complicado. Creamos una pila para que actúe como esa variable de equilibrio. Esto es necesario porque los paréntesis no se pueden superponer. Cuando recorremos una línea y encontramos un paréntesis de apertura, lo colocamos en la pila. Cuando encontramos una llave de cierre, intentamos sacar la llave de apertura de ese tipo de la pila. Si hay una llave de un tipo diferente en la pila, la secuencia no es válida. Si la pila no está vacía al final, la secuencia tampoco es válida.
|
La generación de secuencias de corchetes correctas se deriva directamente de la forma en que se realiza la verificación: solo necesitamos agregar nuevos corchetes sin violar la corrección. Esto se hace por iteración recursiva. Si no lo conoces - BE... ah, no, puedes tratar de entender leyendo más. Este es un ejemplo de código para un tipo de paréntesis:
#incluir <vector>
#incluye <iostream>
utilizando espacio de nombres std;
intn; // Media longitud
vector<char> respuesta; // Nuestra respuesta
void rec(int balance) {
if (ans.size() == 2 * n) { // Si es así, entonces estamos hecho < /span>
para (int i = 0; i < 2 * n; i++)
cout << y[yo] << " ";
cout << "\n";
}
si (ans.size() + balance + 2 <= n * 2) { // Comprueba, nosotros Lo haremos, cerramos la nueva llave de apertura
// Ahora ten cuidado: no necesitamos hacer un vector separado para cada secuencia
respuesta.push_back('(');
rec(saldo + 1);
respuesta.pop_back(); // Para comprender esto, debe conocer la recursividad. Primero, agregamos un paréntesis al vector y luego ejecutamos todo este código nuevamente.
// Es decir, agregar un paréntesis nuevamente, si podemos.
// Y esto sucederá hasta que empecemos a salir de la recursividad, es decir, hasta que alcancemos la longitud deseada.
// Entonces se empezarán a quitar los corchetes. Si entiendes esto, te felicito, eres increíble.
}
si (saldo > 0) { // Si podemos cerrar un paréntesis, lo cerramos.
respuesta.push_back(')');
rec(saldo - 1);
respuesta.pop_back();
}
}
int principal()
{
cin>> norte;
rec(0);
return 0;
}
Y ahora el momento de las dificultades: ¡tendrá que escribir el algoritmo para varios tipos de corchetes USTED MISMO! Muahahahahahahahahahahahaha!
|