Checking for balanced brackets in Python

Question

I'm solving HackerRank "Stacks: Balanced Brackets" in Python.

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is considered to be balanced if the following conditions are met:

It contains no unmatched brackets. The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets. Given strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, print YES on a new line; otherwise, print NO on a new line.

My code:

def is_matched(expression):
    if len(expression) % 2 != 0:
        return False

    opening = ("(", "[", "{")
    closing = (")", "]", "}")
    mapping = {opening[0]:closing[0],
               opening[1]:closing[1],
               opening[2]:closing[2]}

    if expression[0] in closing:
        return False

    if expression[-1] in opening:
        return False

    closing_queue = []
    for letter in expression:
        if letter in opening:
            closing_queue.append(mapping[letter])
        elif letter in closing:
            if not closing_queue:
                return False

            if closing_queue[-1] == letter:
                closing_queue.pop()
            else:
                return False

    return True

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

What could be improved here? What can be done to make my code more idiomatic (pythonic code)?

Is my implementation bad? Why is it?

Answer 1

Review

Your implementation is quite good, but ofcourse there are always some things that can be improved upon.

1. Use a if __name__ == '__main__' guard, see what they do.
2. opening closing and mapping could be done a bit simpler
   • You may use list over the values, to create a list,
   • And you may zip those in a dictionary with the zip keyword.
3. If you need to add alot of corner cases, your algorithm is likely off somewhere else.
4. Consider adding Testcases, Docstrings, or both in the form of Doctest. To make it easier to Test your algorithm.

Alternative code

def is_matched(expression):
    """
    Finds out how balanced an expression is.
    With a string containing only brackets.

    >>> is_matched('[]()()(((([])))')
    False
    >>> is_matched('[](){{{[]}}}')
    True
    """
    opening = tuple('({[')
    closing = tuple(')}]')
    mapping = dict(zip(opening, closing))
    queue = []

    for letter in expression:
        if letter in opening:
            queue.append(mapping[letter])
        elif letter in closing:
            if not queue or letter != queue.pop():
                return False
    return not queue

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Answer 2

• What if you enter something that isn't a bracket? Currently you ignore that, maybe you would want to error.
• You don't need to make opening and closing. You can just use mapping.

def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif letter not in mapping.values():
            raise ValueError('Unknown letter {letter}'.format(letter=letter))
        elif not (queue and letter == queue.pop()):
            return False
    return not queue

---

If however you didn't want to ignore it or error, you could just remove the check, and have the code return False:

def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif not (queue and letter == queue.pop()):
            return False
    return not queue

Answer 3

Another thing to fix is the misleading name of the list variable. Items go in and out in LIFO order, making this a stack and not a queue.

Answer 4

The other answers have already covered what can be improved in your script so I will not repeat any of that. Just wanted to add an alternative I found interesting.

An elimination-based approach:

def f(my_string):
    brackets = ['()', '{}', '[]']
    while any(x in my_string for x in brackets):
        for br in brackets:
            my_string = my_string.replace(br, '')
    return not my_string

In every iteration the innermost brackets get eliminated (replaced with empty string). If we end up with an empty string, our initial one was balanced; otherwise, not.

---

Examples and notes:

• Best case: s = '[](){}{}()[]' -> reduces to nothing in one while iteration.
• Worst case: s = '({[[{()}]]})' -> same length string requires 6 iterations (destroyed inside out)

You could add some short-circuiting for quickly catching cases of lengthy strings that have an uneven number of opening and closing brackets so that you don't waste your time eliminating...

Answer 5

One of the most frequent remarks on this site also applies here: make sure your code has comments to explain not just what it is doing, but what the reasoning is behind the code the comment is relevant towards.. The next person who needs to maintain your code will thank you for it, and if you ever have to look at your code again in half a year or so, you're going to be thankful you took the effort right now.

Answer 6

I was testing these algorithms, and it works well, but in some cases, they will fail. I would treat it as a string, using a stack, because it could works for a compiler, and could be more than parentheses, brackets and keys.

Test these cases, and if it works in all cases, you are doing well:

string = "[]{}()[][][]"
print "Should be true"
print str(is_matched(string))

string = "([()][][{}])"
print "Should be true"
print str(is_matched(string))

string = "[(])"
print "Should be false"
print str(is_matched(string))

string = "[([])()({})]"
print "Should be true"
print str(is_matched(string))

string = "[(,,),(,,[])]"
print "Should be true but it fails"
print str(is_matched(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(is_matched(string))

string = "]"
print "Should be false"
print str(is_matched(string))

string = "["
print "Should be false"
print str(is_matched(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(is_matched(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(is_matched(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(is_matched(string))

This is my working solution, that works for all cases:

def pairs_stack(string, pairs = {'[': ']', '{': '}', '(': ')'}):

    opening = pairs.keys()

    closing = pairs.values()

    match = list()

    for s in string:
        if s in opening:
            match.insert(0, s)
        elif s in closing:
            if len(match) == 0:
                return False
            if match[0] == opening[closing.index(s)]:
                match.pop(0)
            else:
                return False

    if len(match) == 0:
        return True

    return False

Test it:

import time

millis = float(time.time() * 1000)

string = "[]{}()[][][]"
print "Should be true"
print str(pairs_stack(string))

string = "([()][][{}])"
print "Should be true"
print str(pairs_stack(string))

string = "[(])"
print "Should be false"
print str(pairs_stack(string))

string = "[([])()({})]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,),(,,[])]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(pairs_stack(string))

string = "]"
print "Should be false"
print str(pairs_stack(string))

string = "["
print "Should be false"
print str(pairs_stack(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(pairs_stack(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(pairs_stack(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(pairs_stack(string))

millis = float(time.time() * 1000) - millis
print "Result " + str(millis)