Bracket balance checker in Python

Question

Implement a feature for a text editor to find errors in the usage of brackets in the code.

Input: sorted(list(zip(a, b))

Output: False

Input: ([{}, {}])

Output: True

Here's my implementation in Python:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """Push item in stack."""
        self.items.append(item)

    def top(self):
        """Return top of the stack."""
        if self.items:
            return self.items[-1]
        raise Exception('Stack empty.')

    def pop(self):
        """Remove and return top of the stack."""
        if self.items:
            return self.items.pop()
        raise Exception('Stack empty.')

    def is_empty(self):
        """Return True if stack is empty."""
        return len(self.items) == 0

    def __len__(self):
        """Return stack length."""
        return len(self.items)

    def __str__(self):
        """Print stack."""
        print(list(reversed(self.items)))


def check_balance(code):
    """Return True if brackets are balanced, False otherwise."""
    valid = {']': '[', ')': '(', '}': '{'}
    lefts = Stack()
    for char in code:
        if char in '[({':
            lefts.push(char)
        if char in '])}' and lefts.is_empty():
            return False
        if char in '])}' and not lefts.is_empty():
            if lefts.top() != valid[char]:
                return False
            lefts.pop()
    if not lefts:
        return True
    return False


if __name__ == '__main__':
    print(check_balance('[(((((({{}}))))))]'))
    print(check_balance('print(list(reversed(self.items))'))
    print(check_balance(' print(list(reversed(self.items))[]'))
    print(check_balance('print(list(reversed(self.items)))'))
    print(check_balance('print(list[(]reversed(self.items))'))
    print(check_balance('print(list(reversed(self.items[0)]))'))
    print(check_balance('print(list(reversed(self.items[7])))'))

Answer 1

The overall implementation looks great, good job.

---

def is_empty(self):
    """Return True if stack is empty."""
    return len(self.items) == 0

Since you end up using this as a truthy check, it is actually not needed as you've implemented len. A truth check will look for bool, and then fallback to checking if len returns 0. You can remove this if it isn't needed directly for the assignment and remove calls to it.

---

def __str__(self):
    """Print stack."""
    print(list(reversed(self.items)))

str should return a string version of the instance, not print it. It's a quick fix.

def __str__(self):
    return str(list(reversed(self.items))))

or if you want something custom, this is the place to do it.

def __str__(self):
    return "[ " + " | ".join(str(item) for item in reversed(s.items))

---

valid = {']': '[', ')': '(', '}': '{'}

I don't think this is a good name. I would prefer a name like correspondingBracket or oppositeParenthesis. I would also change up the formatting so it is a little simpler for a human to parse. This may be overkill.

oppositeBracket = {
    ']': '[',
    ')': '(',
    '}': '{'
}

---

for char in code:
    if char in '[({':
        lefts.push(char)
    if char in '])}' and lefts.is_empty():
        return False
    if char in '])}' and not lefts.is_empty():
        if lefts.top() != valid[char]:
            return False
        lefts.pop()

The logic here is sensible, but a little over-complicated. Let's replace

if A and B:
    doX()
if A and not B:
    doY()

with

if A:
    if B:
        doX()
    else:
        doY()

While this results in more indented code, there is less of it, and we don't repeat redundant checks. The code directly after matching the above pattern is then

for char in code:
    if char in '[({':
        lefts.push(char)
    if char in '])}':
        if lefts.is_empty():
            return False
        else:
            if lefts.top() != valid[char]:
                return False
        lefts.pop()

which we can make a little nicer with some elif statements to reduce the indentation and removing the is_empty

for char in code:
    if char in '[({':
        lefts.push(char)
    elif char in '])}':
        if not lefts:  # No matching opening brace
            return False
        elif lefts.top() != valid[char]:  # Wrong opening brace match
            return False
        lefts.pop()

This code is rather close to the other answer now, can you see the further changes they have made to get their suggested code?

---

if not lefts:
    return True
return False

Some people prefer this check and return style since you can add new checks quickly and it won't show other lines in the diff. I don't think any new checks will be added so I think

return not lefts  # Nothing left on the stack means all braces found their match

---

print(check_balance('[(((((({{}}))))))]'))
...

This is good for quick unit tests. As a next step use asserts. Right now the output of the testcases need to be manually inspected. I might have no idea if I'm expecting a True or False result back from the function. If in 6 months and after several code changes I ran some tests and gave you the result

False
True
False
False
True

could you tell which testcases passed? What if each testcase was 100 characters long? Do you want to re-figure it out each time? Using unittest the testcases might look something like

assertTrue(check_balance('[(((((({{}}))))))]'))
assertTrue(check_balance('print(list(reversed(self.items)))'))
assertTrue(check_balance('print(list(reversed(self.items[7])))'))
assertFalse(check_balance('print(list(reversed(self.items))'))
assertFalse(check_balance('print(list(reversed(self.items))[]'))
assertFalse(check_balance('print(list[(]reversed(self.items))'))
assertFalse(check_balance('print(list(reversed(self.items[0)]))'))

Unfortunately this is rather tedious, so lets make it into a loop

true_cases = (
    '[(((((({{}}))))))]',
    'print(list(reversed(self.items)))',
    'print(list(reversed(self.items[7])))',
)
for testcase in true_cases:
    assertTrue(check_balance(testcase))

and the same idea for false cases. Beyond this, add some simple testcases like '()[]{}' and some potential edge cases like '' or '}{'. It is much easier to debug why a 2 character input is failing than a 20 character input.

---

Some extra things to think about

1. What exception should a pop on an empty Stack return? Currently it is a generic exception. Can it be more specify. I would look at similar data structures that have pop in python like list, queue, and dict to see what they do.
2. What work do you need to do to add more brackets to check? For example, angled brackets <>.
3. A follow up problem is can you check all brackets are matched where the corresponding brackets are { with }, [ with ], and # with #. The last pair is tricky since it is the same symbol for the opening and closing bracket. For example testcases I would declare '{##}' and '####' to be balanced, but '#' and '#{}##' to not be balanced. If this seems like an academic problem, consider quote symbols and how they are matched.

Answer 2

Looks pretty good.

A couple comments:

Unless this is an assignment to make or use a Stack, a Python list would suffice.

The code checks if a char is in '[{(', then checks if it is in ']})' and the stack is empty, then checks if it is in ']})' (again) and checks if the top of the stack is the matching bracket. All characters go through all those checks.

In general, it is good to make the common case fast and less cases can be slower.

def check_balance(code):
    """Return True if brackets are balanced, False otherwise.
    """

    valid = {']': '[', ')': '(', '}': '{'}

    lefts = []

    for char in code:
        # common case
        if char not in '[](){}':
            continue

        if char in '[({':
            lefts.append(char)

        elif not lefts or lefts.pop() != valid[char]:
            return False

    return lefts == []