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

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 válidoate una cadena dada.

¿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 simple, rizado y square 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 desempeñará un papel fundamental. vamos revVea los conceptos básicos de una pila en la siguiente sección.

La estructura de datos de la pila Revisitado

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.

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 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.

Tutorial de ejemplos de cadenas de paréntesis válidos

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 third carácter en la cadena) es un corchete de cierre, por lo que debe sacarlo de 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.

#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 third personaje ] es un cierre square soporte, y debería 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.

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

• Los dos primeros personajes {( son corchetes de apertura, así que empújelos hacia la pila.
• El third el 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! ✅

📌 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!

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

Programa de Python para verificar paréntesis válidos

En Python, puedes usar la lista para emularate un montón.

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.

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 diferenciarate entre corchetes 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:

• un corto description 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 cuál es la cadena entre paréntesis para ser válidaated. Vuelve True or False dependiendo de si la cuerda o no test_str es válida.
• Aquí, stack es la lista de Python que emulatees 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.

Para Concluir

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 aprendiste a validarate 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.
• finalally, definiste la función de Python para verificar si una cadena de paréntesis determinada es válida.

Como siguiente paso, intente codificar el problema en GeekflareEl editor de Python en línea. Siéntase libre de rev¡Consulta esta guía si necesitas ayuda!

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