Programa de Python para verificar paréntesis equilibrados en una expresión (buena formación) usando Stack

Dada una string de expresión exp, escriba un programa para examinar si los pares y los órdenes de “{“, “}”, “(“, “)”, “[“, “]” son correctos en exp.

Ejemplo

Entrada : exp = “[()]{}{[()()]()}” 
Salida : Balanceada

Entrada : exp = “[(])” 
Salida : No balanceada 

check-for-balanced-parentheses-in-an-expression

Algoritmo: 

  • Declara una pila de caracteres S.
  • Ahora recorra la string de expresión exp. 
    1. Si el carácter actual es un corchete de inicio ( ‘(‘ o ‘{‘ o ‘[‘ ) entonces empújelo para apilar.
    2. Si el carácter actual es un corchete de cierre ( ‘)’ o ‘}’ o ‘]’ ), entonces salte de la pila y si el carácter reventado es el corchete de inicio correspondiente, entonces bien, de lo contrario, los corchetes no están equilibrados.
  • Después de completar el recorrido, si queda algún soporte inicial en la pila, entonces «no está equilibrado»

La imagen de abajo es una ejecución en seco del enfoque anterior:

A continuación se muestra la implementación del enfoque anterior:

Python3

# Python3 program to check for
# balanced brackets.
  
# function to check if
# brackets are balanced
  
  
def areBracketsBalanced(expr):
    stack = []
  
    # Traversing the Expression
    for char in expr:
        if char in ["(", "{", "["]:
  
            # Push the element in the stack
            stack.append(char)
        else:
  
            # IF current character is not opening
            # bracket, then it must be closing.
            # So stack cannot be empty at this point.
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == '(':
                if char != ")":
                    return False
            if current_char == '{':
                if char != "}":
                    return False
            if current_char == '[':
                if char != "]":
                    return False
  
    # Check Empty Stack
    if stack:
        return False
    return True
  
  
# Driver Code
if __name__ == "__main__":
    expr = "{()}[]"
  
    # Function call
    if areBracketsBalanced(expr):
        print("Balanced")
    else:
        print("Not Balanced")
  
# This code is contributed by AnkitRai01 and improved
# by Raju Pitta
Producción

Balanced

Complejidad de Tiempo: O(n) 
Espacio Auxiliar: O(n) para pila. 

¡Consulte el artículo completo sobre Verificación de paréntesis equilibrados en una expresión (bien formado) usando Stack para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *