Check if brackets are balanced

Question

class EmptyStackError(Exception):
    def __init__(self):
        super().__init__('Stack is empty. Invalid operation')

class FullStackError(Exception):
    def __init__(self):
        super().__init__('Stack is full. Cannot push')

---

class Stack:
    """ Stack with a specified size """
    def __init__(self, size):
        self.head = None
        self.size = size
        self.current_size = 0

    def push(self, data):
        """ Push data to the top of the stack """
        if self.current_size == self.size:
            raise FullStackError
        node = Node(data)
        if not self.head:
            self.head = node
        else:
            node.next_node = self.head
            self.head = node
        self.current_size += 1

    def pop(self):
        """ Remove data from the top of the stack and return it """
        if not self.head:
            raise EmptyStackError
        data = self.head.data
        self.head = self.head.next_node
        self.current_size -= 1
        return data

    def peek(self):
        """ Take a look at the current item at the top of stack, but do not return it"""
        if not self.head:
            raise EmptyStackError
        data = self.head.data
        return data

    def get_size(self):
        """ Return the current size of the stack """
        return self.current_size  

---

opening_brackets = '([{'
closing_brackets = ')]}'

def check_balance(input_string: str) -> bool:
    answer = True
    stack = Stack(100)
    for char in input_string:
        if char in opening_brackets:
            stack.push(char)
        else:
            try:
                top_item = stack.peek()
            except EmptyStackError as e:
                answer = False # if it's with closing brackets, it's not balanced
                break
            if tuple([top_item, char]) not in zip(opening_brackets, closing_brackets):
                answer = False
                break
            else:
                stack.pop()
    if stack.get_size() != 0:  # there shouldn't be any items remaining in the stack if it's balanced
        answer = False
    return answer


""" Testing """
strings = ['', '[({})]', '[', '}']
[True, True, False, False] == list(map(check_balance, strings))

I have a stack implementation (along with the EmptyStackError). I didn't want to add to make easier visually, but it might be relevant. I'm finding the code lacking in grace and elegance. Any way to improve on this code? Any bug I cannot see?

Note: I've added the try clause (which I tend to find not that easy on the eyes) to fix a bug when starting with a closing bracket, I get an EmptyStackError which is internal to the stack implementation.

Note: I'm using jupyter lab if that's relevant in any way :)

Answer 1

You should init your Stack with the length of your string. This way, you'd be sure never to hit the FullStackError.

Also, it seems to be on purpose but you don't support other characters in your string? I'd expect "(asdasd)" to return true.

This line : tuple([top_item, char]) not in zip(opening_brackets, closing_brackets): is maybe a little hard to understand at first glance. I'd suggest creating a variable for zip(opening_brackets, closing_brackets). It wouldn't change much but it'd give you an opportunity to have a more meaningful name.

From experience, I'd say that code that parses strings is never elegant and even though it's a generally accepted fact that try/catch(except) are ugly, they are most necessary and I think you should keep it this way.

Two slight nitpicks :

1. I'd rename answer to isBalanced
2. You should put your comments on separated lines for readability.

Answer 2

1. Review

1. In Python, the built-in list data type is suitable for use as a stack: you can push elements onto the stack using the list's append method, pop them using the pop method, and peek at the top of the stack by looking up the last element. All of these operations run in amortized constant time.

2. There's no docstring for check_balance.

3. Instead of setting answer = False and breaking out of the loop, it is simpler to return False immediately. This avoids the need for the variable answer.

4. In this line:

   if tuple([top_item, char]) not in zip(opening_brackets, closing_brackets):
   

   the code iterates through all pairs of opening and closing parentheses in order to see if char is the corresponding close parenthesis to top_item. But there is only one corresponding close parenthesis to top_item, so we shouldn't need to iterate here. What we need instead is a data structure that tells us the corresponding close parenthesis for each open parenthesis:

   # Dictionary mapping open parenthesis to corresponding close parenthesis.
   PAREN = dict('() [] {}'.split())
   

   and then we can test char against the corresponding close parenthesis:

   if char != PAREN[top_item]:
   

5. The test cases don't do anything if the results are not correct. Normally we arrange for test cases to raise an exception if the test fails. This could be done using the assert statement:

   assert check_balance('()[(){}]{}')
   assert not check_balance('([([([])])]}')
   

   or using the features of the unittest module.

2. Revised code

# Dictionary mapping open parenthesis to corresponding close parenthesis.
PAREN = dict('() [] {}'.split())

def check_balance(input_string: str) -> bool:
    "Return True if input_string consists of balanced parentheses."
    stack = []
    for char in input_string:
        if char in PAREN:
            stack.append(char)
        elif not stack or char != PAREN[stack.pop()]:
            return False
    return not stack