Avatar

Kittens Website



Balanced brackets in Python

Written by:

adelina

in PYTHON

algorithms
python
stack
data structures
I have solved a challenge online about balanced brackets, I liked it and I would like to share my solution.

You can find the problem here and try to solve it by yourself.

Follows my solution and then a concise explanation.


def isBalanced(s):
    """ Checks if s contains balanced brackets.

    :returns: 'Yes' if s is balanced otherwise 'NO'
    :rtype: str
    """
    parentheses = {
        '{': 1,
        '[': 2,
        '(': 3,
        '}': -1,
        ']': -2,
        ')': -3
        } 
    
    stack = []

    for elem in s:
        elem = parentheses[elem]
        if elem > 0:
            stack.append(elem)
        else:
            try:
                valore = stack.pop()
            except:
                return 'NO'
            if valore + elem == 0:
                pass
            else:
                return 'NO'
    if len(stack) == 0:
        return 'YES'
    else:
        return 'NO'

Let’s explain the logic of this function. First of all I have used a dictionary structure to map parentheses to integers, just to avoid working with strings.

The method isBalanced takes a string s of open and closed parentheses that match the ones in the dictionary parentheses. There is an array variable stack where an open parentheses is added, while a closed one is removed. There is a try-except because if the parentheses are not matched then the string in input in not balanced and so a NO message is printed. The line if valore + elem == 0 is required because there may be the case in which there is an open round bracket and a closed brace, so in this case we should also return No. A Yes message is returned when the stack is empty and no unmatching open and closed parentheses are found.