English English French French Spanish Spanish German German
Geekflare cuenta con el apoyo de nuestra audiencia. Podemos ganar comisiones de afiliados comprando enlaces en este sitio.
Comparte en:

Cómo verificar paréntesis válidos en Python

paréntesis de pitón
Escáner de seguridad de aplicaciones web Invicti – la única solución que ofrece verificación automática de vulnerabilidades con Proof-Based Scanning™.

En este tutorial, aprenderá a verificar si hay paréntesis válidos en Python. 

Dada una cadena de paréntesis, verificar si la combinación de paréntesis es IMPORTANTE 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á un Función de Python para validar una cadena dada.

What is the Valid Parentheses Problem?

 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 simple, rizado y cuadrado tirantes: () [] {}, 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:

  1. Cada soporte de apertura debe tener un pareo soporte de cierre del mismo tipo.
  2. Los paréntesis deben cerrarse en el correcta orden.

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 un ú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 add un elemento a la parte superior de la pila, realiza un empuje operación, cuando usted Removere un elemento de la parte superior de la pila, realiza un Deliciosos operación.

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.

How to Check for Valid Parentheses

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 incluso número 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_stry los caracteres individuales de la cadena char.

Paso 2: Si el primer carácter char es un soporte de apertura (, {o [, empújelo hasta la parte superior de la pila y continúe con el siguiente carácter de la cadena.

Paso 3: Ahora, comprueba si el siguiente carácter (char) es un paréntesis de apertura o de cierre.

Paso 3.1: Si se trata de un soporte de apertura, empújelo nuevamente sobre la pila.

Paso 3.2: Si encuentra un soporte de cierre, levante la parte superior de la pila y continúe con el paso 4.

Paso 4: Aquí nuevamente, hay 3 posibilidades basadas en el valor extraído de la pila:

Paso 4.1: Si es un soporte de apertura de la mismo escriba, vuelva al paso 3.

Paso 4.2: Si se trata de un soporte de apertura de un una experiencia diferente type, puede concluir de nuevo que no es una cadena de paréntesis válida.

Paso 4.3: La última posibilidad es que la pila esté vacío. Nuevamente, este es el caso de una cadena no válida, ya que se encontró con un corchete de cierre que no tiene un corchete de apertura coincidente.

Valid Parentheses String Examples Walkthrough

Ahora tomemos tres ejemplos y sigamos los pasos anteriores.

📑 Si ya entendió cómo funciona esto, no dude en pasar a la siguiente sección.

#1. Como primer ejemplo, dejemos test_str = "{()".

  • { es el primer carácter, y es un corchete de apertura, por lo que lo empuja a la pila.
  • El siguiente carácter ( también es un corchete de apertura, así que continúe y empújelo también a la pila.
  • El tercer carácter en la cadena) es un corchete de cierre, por lo que debe sacar la parte superior de la pila, que devuelve (.
  • En este punto, has llegado al final de la cadena. Pero la pila aún contiene la apertura { , que nunca se cerró. Así que la cadena de paréntesis dada test_str es inválido.
paréntesis válidos-python-1

#2. En este segundo ejemplo, sea test_str = "()]"

  • El primer personaje ( es un soporte de apertura; empujarlo a la pila.
  • El segundo personaje ) es un paréntesis 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 personaje ] es un corchete de cierre, y deberías volver a sacar la parte superior de la pila. Sin embargo, como puede ver, la pila es vacío—lo que significa que no hay un soporte de apertura coincidente [. Por lo tanto, esta cadena no es válida.
paréntesis válidos-python-3

#3. En este último ejemplo, test_str = "{()}".

  • Los dos primeros personajes {( son corchetes de apertura, así que empújelos hacia la pila.
  • El tercer personaje es un cierre. ), así que saca la parte superior de la pila: (.
  • el siguiente personaje } es una llave de cierre, y cuando abres la parte superior de la pila, obtienes { – una llave de apertura.
  • Después de haber recorrido toda la cadena, la pila se vacío y test_str ¡es válida! ✅
paréntesis válidos-python-2

📌 He elaborado el siguiente diagrama de flujo que describe los pasos en el problema de verificación de paréntesis válidos. ¡Puede guardarlo para una referencia rápida!

Diagrama de flujo de paréntesis válidos Python

En la siguiente sección, veamos cómo traducir nuestro concepto al código de Python.

Python Program to Check for Valid Parentheses

En Python, puede usar la lista para emular una pila.

Puede utilizar el .append() para agregar elementos al final de la lista. Esto es similar a empujar a la parte superior de la pila.

El .pop() El método devuelve el último elemento de la lista, y esto es similar a la extracción de la parte superior de la pila: para eliminar el último elemento agregado.

stack-list-similitud

Ahora ya sabe cómo implementar las operaciones push y pop en una lista de Python, emulando la pila.

Como siguiente paso, respondamos la pregunta: ¿cómo diferenciar entre paréntesis de apertura y cierre?

Bueno, puedes usar un diccionario de Python, con los corchetes de apertura '{', '[', '(' como el claves del diccionario y los corchetes de cierre correspondientes '}', ']', ')' como los valores. Puedes usar el .keys() para acceder a claves individuales en el diccionario.

Usemos todo lo que hemos aprendido para escribir la definición de la is_valid() función.

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 incluyendo:

  • 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 utilizar help(is_valid) or 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 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 en un parámetro, test_str que es la cadena de paréntesis a validar. Vuelve True or False dependiendo de si la cuerda o no test_str es válida.
  • Aquí, stack es la lista de Python que emula la pila.
  • Y par_dict es el diccionario de Python, con corchetes de apertura como el claves y corchetes de cierre como el correspondiente valores.
  • Mientras recorremos la cadena, si nos encontramos con alguna condición que haga que la cadena de paréntesis no sea válida, la función devuelve False y salidas.
  • Después de recorrer todos los caracteres de la cadena, stack == [] comprueba si stack is vacío. 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 método para resolver el problema usando el montón como la estructura de datos de elección.
  • Luego aprendió cómo validar una combinación de paréntesis usando un diccionario de Python: con corchetes de apertura, el 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 Editor de Python en línea de Geekflare. ¡Siéntete libre de revisar esta guía si necesitas ayuda!

Echa un vistazo a más Tutoriales de Python. ¡Feliz codificación!

Gracias a nuestros patrocinadores
Más lecturas interesantes sobre el desarrollo
Impulse su negocio
Algunas de las herramientas y servicios para ayudar a que su negocio crezca.
  • Invicti utiliza Proof-Based Scanning™ para verificar automáticamente las vulnerabilidades identificadas y generar resultados procesables en cuestión de horas.
    Prueba Invicti
  • Web scraping, proxy residencial, administrador de proxy, desbloqueador web, rastreador de motores de búsqueda y todo lo que necesita para recopilar datos web.
    Prueba Brightdata
  • Semrush es una solución de marketing digital todo en uno con más de 50 herramientas en SEO, redes sociales y marketing de contenido.
    Prueba Semrush
  • Intruder es un escáner de vulnerabilidades en línea que encuentra debilidades de ciberseguridad en su infraestructura, para evitar costosas filtraciones de datos.
    Trata Intruder