Calcular con Python si un string está balanceado en su uso de parentesis, llaves y corchetes usando pilas (balance brackets with stacks in Python).

07/22/2017 | Author: Eduardo Enriquez

Calcular  si un string tiene la misma cantidad de parentesis, corchetes o llaves de apertura y cierre. Esto es si está balanceado.

Creo que una buena solucion es tener a mano por un lado un string con todos las llaves que sirven de apertura (open_brackets) y otro string con los de cierre (close_brackets). Y después tener una pila (stack) para ir llenandola con cada llave que encontramos. PERO la cuestión está en saber que, si vamos a agregar una llave de cierre, tiene que haber previamente una llave de apertura. Y ademas que sea del mismo tipo que usamos. Por esto al final usamos e index de la de cierre porque como los dos string tienen el mismo orden, el partentis esta en la posicion 0 tanto para cierre como para apertura.

def isBalanced(string):
    stack = []
    open_brackets = "({["
    close_brackets = ")}]"

    for character in string:
        if character in open_brackets:
            stack.append(character)
        elif character in close_brackets:
            if len(stack) == 0:
                return False
            else:
                stackTop = stack.pop()
                balancingBracket = open_brackets[close_brackets.index(character)]
                if stackTop != balancingBracket:
                    return False

    return not len(stack)

Para tener una solución más global con casos de pruebas pueden optar por la siguiente opcion:

def is_balanced(brackets, open_brackets="({[", close_brackets=")}]"):
    stack = []
    for bracket in brackets:
        if bracket in open_brackets:
            stack.append(bracket)
        elif len(stack) == 0:
            return False
        elif bracket in close_brackets:
            stacked = stack.pop()
            closed_bracket_position = close_brackets.index(bracket)
            open_bracket = open_brackets[closed_bracket_position]
            if stacked != open_bracket:
                return False

    return not len(stack)


def braces(values):
    response = []
    for string in values:
        if is_balanced(string):
            response.append(True)
        else:
            response.append(False)

    return response


samples1 = "{}[]()"
samples2 = "{[}]}"
sample3 = "{[}]}]]]]"
samples = [samples1, samples2, sample3]

print(braces(samples))

 


Tags