En este tutorial, aprenderá a buscar paréntesis válidos en Python.
Dada una cadena de paréntesis, comprobar si la combinación de paréntesis es válida es una pregunta de entrevista de codificación popular. Y en los próximos minutos, aprenderá la técnica para resolver esta pregunta y también codificará una función de Python para validar una cadena determinada.
Tabla de contenido
¿Qué es el problema de los paréntesis válidos?
Comencemos nuestra discusión respondiendo la pregunta, ¿cuál es el problema de los paréntesis válidos?
Dada una cadena que contiene los caracteres paréntesis simples, llaves y llaves cuadradas: () [] {}, debe verificar si la combinación de paréntesis dada es válida o no.
Una cadena de paréntesis válida cumple las dos condiciones siguientes:
Estos son algunos ejemplos de cadenas de paréntesis válidas e inválidas.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
En nuestro enfoque de resolución de problemas, la pila es la estructura de datos que jugará un papel fundamental. Revisemos los conceptos básicos de una pila en la siguiente sección.
La estructura de datos de la pila revisada
La pila es una estructura de datos de último en entrar, primero en salir (LIFO), donde puede agregar elementos a la parte superior de la pila y también eliminarlos de la parte superior de la pila.
Cuando agrega un elemento a la parte superior de la pila, realiza una operación de inserción, cuando elimina un elemento de la parte superior de la pila, realiza una operación emergente.
Usaremos las siguientes dos reglas para generar un conjunto de operaciones que podemos realizar en la cadena de paréntesis.
- Empuje todos los soportes de apertura en la pila.
- Si encuentra un soporte de cierre, levante la parte superior de la pila.
Procedamos a resolver el problema de verificación de paréntesis válidos.
Cómo verificar paréntesis válidos
Juntando todas las observaciones de los ejemplos anteriores, tenemos lo siguiente.
Compruebe la longitud de la cadena de paréntesis: si es impar, la cadena no es válida
Como cada corchete de apertura debe tener un corchete de cierre, una cadena válida debe contener un número par de caracteres. Si la longitud de la cadena es impar, puede concluir de inmediato que tiene una combinación de paréntesis no válida.
# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"
# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"
# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"
A continuación, veamos cómo podemos abordar cuando el número de caracteres en la cadena es par.
La longitud de la cadena de paréntesis es par: ¿y ahora qué?
Paso 1: Atraviesa la cuerda de izquierda a derecha. Llamemos a la cadena test_str ya los caracteres individuales de la cadena char.
Paso 2: si el primer carácter char es un corchete de apertura (, { o [, push it to the top of the stack and proceed to the next character in the string.
Step 3: Now, check if the next character (char) is an opening or a closing bracket.
Step 3.1: If it’s an opening bracket, push it again onto the stack.
Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.
Step 4: Here again, there are 3 possibilities based on the value popped off the stack:
Step 4.1: If is an opening bracket of the same type, loop back to step 3.
Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.
Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.
Valid Parentheses String Examples Walkthrough
Now let’s take three examples and walk through the above steps.
📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.
#1. As a first example, let test_str = “{()”.
- { is the first character, and it’s an opening bracket, so you push it to the stack.
- The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
- The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
- At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.
#2. In this second example, let test_str = “()]”
- El primer carácter ( es un corchete de apertura; empújelo hacia la pila.
- El segundo carácter ) es un corchete de cierre; salga de la parte superior de la pila, que resulta ser ) – un soporte de apertura del mismo tipo. Continúe con el siguiente carácter.
- El tercer carácter ]es un corchete de cierre, y debe volver a abrir la parte superior de la pila. Sin embargo, como puede ver, la pila está vacía, lo que significa que no hay un paréntesis de apertura coincidente. [. Hence, this string is invalid.
#3. In this final example, test_str = “{()}”.
- The first two characters {( are opening brackets, so push them onto the stack.
- The third character is a closing ), so pop off the stack top – (.
- The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
- After you have traversed the entire string, the stack is empty and test_str is valid! ✅
📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!
In the next section, let’s see how to translate our concept to Python code.
Python Program to Check for Valid Parentheses
In Python, you can use the list to emulate a stack.
You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.
The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.
So you now know how to implement the push and pop operations on a Python list, emulating the stack.
As a next step, let’s answer the question: how to differentiate between opening and closing brackets?
Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]’, ‘)’ como los valores. Puede usar el método .keys() para acceder a claves individuales en el diccionario.
Usemos todo lo que hemos aprendido para escribir la definición de la función is_valid().
Comprender la definición de la función
Lea la siguiente celda de código que contiene la definición de la función. Puede ver que hemos utilizado los pasos del diagrama de flujo junto con la explicación anterior.
Además, también hemos añadido un cadena de documentación incluido:
- una breve descripción de la función
- los argumentos en la llamada de función
- los valores de retorno de la función
▶ Puede usar help(is_valid) o is_valid.__doc__ para recuperar la cadena de documentación.
def isValid(test_str):
'''Check if a given parentheses string is valid.
Args:
test_str (str): The parentheses string to be validated
Returns:
True if test_str is valid; else False
'''
# len(test_str) is odd -> invalid!
if len(test_str)%2 != 0:
return False
# initialize parentheses dict
par_dict = {'(':')','{':'}','[':']'}
stack = []
for char in test_str:
# push opening bracket to stack
if char in par_dict.keys():
stack.append(char)
else:
# closing bracket without matching opening bracket
if stack == []:
return False
# if closing bracket -> pop stack top
open_brac = stack.pop()
# not matching bracket -> invalid!
if char != par_dict[open_brac]:
return False
return stack == []
La función de Python is_valid comprueba si la cadena de paréntesis es válida y funciona de la siguiente manera.
- La función is_valid toma un parámetro, test_str, que es la cadena de paréntesis que se va a validar. Devuelve True o False dependiendo de si la cadena test_str es válida o no.
- Aquí, stack es la lista de Python que emula la pila.
- Y par_dict es el diccionario de Python, con corchetes de apertura como claves y corchetes de cierre como los valores correspondientes.
- Mientras recorremos la cadena, si nos encontramos con alguna condición que hace que la cadena de paréntesis no sea válida, la función devuelve False y sale.
- Después de recorrer todos los caracteres de la cadena, apilar == [] comprueba si la pila está vacía. En caso afirmativo, test_str es válido y la función devuelve True. De lo contrario, la función devuelve False.
Ahora, avancemos y hagamos algunas llamadas de función para verificar que nuestra función funcione correctamente.
str1 = '{}[]'
isValid(str1)
# Output: True
str2 = '{((}'
isValid(str2)
# Output: False
str3 = '[{()}]'
isValid(str3)
# Output: True
str4 = '[{)}]'
isValid(str4)
# Output: False
str5 = '[[]}'
isValid(str5)
# Output: False
Del fragmento de código anterior, podemos concluir que la función funciona como se esperaba.
Conclusión 🧑💻
Aquí hay un breve resumen de lo que has aprendido.
- En primer lugar, se le presentó el problema de la verificación de paréntesis válidos.
- A continuación, aprendió un enfoque para resolver el problema usando la pila como la estructura de datos elegida.
- Luego aprendió a validar una combinación de paréntesis usando un diccionario de Python: con corchetes de apertura, las claves y los corchetes de cierre correspondientes como valores.
- Finalmente, definió la función de Python para verificar si una cadena de paréntesis dada es válida.
Como siguiente paso, intente codificar el problema en el editor Python en línea de kirukiru.es. ¡Siéntete libre de revisar esta guía si necesitas ayuda!
Vea más tutoriales de Python. ¡Feliz codificación!🎉