4
\$\begingroup\$
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 :)

\$\endgroup\$
  • \$\begingroup\$ Code to check code... \$\endgroup\$ – FreezePhoenix May 10 '18 at 18:27
  • \$\begingroup\$ There isn't any need. But I will add what I added even though it's kinda lame. \$\endgroup\$ – MAA May 10 '18 at 18:32
5
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Initializing (initting ?) the stack with the length of the string is brilliant. I wasn't comfortable with the 100 magic number. \$\endgroup\$ – MAA May 10 '18 at 19:07
  • \$\begingroup\$ Yeah I'm not supporting other characters on purpose. I didn't even think of the problem of adding other characters. But this is an interesting idea actually. I will add it surely. \$\endgroup\$ – MAA May 10 '18 at 19:08
  • \$\begingroup\$ I didn't like how the "tuple([top_item, char]) not in zip(opening_brackets, closing_brackets):" looked either. I will name this opening_closing and put the variable in the beginning of the function. No need to zip everytime there's a closing character :). Thank you for this. \$\endgroup\$ – MAA May 10 '18 at 19:10
  • \$\begingroup\$ I'm leaving try clause then. I didn't know other people shared my idea that it's ugly (despite the necessity) :). As for the nitpicks, it's exactly the kind of details I am always looking for. Good variable is super important to me and is_balanced is a beautiful and apt variable name. As for the comments, I'm used to putting one line comments at the end of the line. I'm definitely changing that too. Much appreciated Topin. Thank you for your time. \$\endgroup\$ – MAA May 10 '18 at 19:13
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 1. You are right. I was practicing implementing stacks using a linked list. 2. Excellent point. \$\endgroup\$ – MAA May 11 '18 at 12:17
  • \$\begingroup\$ 3. That's my coding style. I don't like returning values from inside a block. I'd rather have a single point of exit from a function. \$\endgroup\$ – MAA May 11 '18 at 12:18
  • \$\begingroup\$ 4. This is just brilliant. This improves this line from linear to constant, right? If so, then it's a brilliant idea. Even if it doesn't, it's much more readable than the previous one. \$\endgroup\$ – MAA May 11 '18 at 12:19
  • \$\begingroup\$ 5. You are right again. I just added the puny tests because I was asked. But they aren't real tests \$\endgroup\$ – MAA May 11 '18 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.