Hackerrank Stacks: Balanced Brackets

This HackerRank problem is an interview classic. I have got in input a string containing only brackets, I have to ensure they are correctly balanced. It is very easy if you get you should use a stack to process them. Here I implement a solution in Python, that is interesting because we should make use here a couple of pythonic constructions.

Besides the provided samples, I added a missing important element to my unit test.
def test_provided_1(self):
    self.assertEqual(True, solution('{[()]}'))

def test_provided_2(self):
    self.assertEqual(False, solution('{[(])}'))

def test_provided_3(self):
    self.assertEqual(True, solution('{{[[(())]]}}'))

def test_too_close(self):
    self.assertEqual(False, solution('}}'))
In the last one I have only closing brackets, that's obviously a False. I feel that explicitly setting a test on this case helps to get sooner to the solution.

The idea is pushing the opening brackets on the stack and popping an element when we are examining a closing bracket. If there is no matching bracket in the stack or, worse, the stack is empty, the sequence has to be rejected.

Here is my implementation:
def solution(data):
    matches = { '(': ')', '[': ']', '{': '}' }  # 1

    stack = []  # 2
    for c in data:  # 3
        if c in matches.keys():  # 4
            stack.append(c)
        elif not stack or c != matches[stack.pop()]:  # 5
            return False
    return True if not stack else False  # 6
1. I use a dictionary to store the opening brackets as keys and the closing ones as values. That helps keeping the code compact.
2. A plain list works a as a stack.
3. Looping on the characters in the input data. Notice that there is no error handling whatsoever. This is a typical interview code, robustness would be added on demand.
4. First use of the dict in (1), I compare the character against its keys to check if it is an opening bracket. If so, I push it in the stack.
5. Otherwise, I expect it to be a closing bracket. Before popping from the stack, I should ensure it is not empty, then I use the element in the stack as key for the dict in (1) to retrieve the matching bracket, and I compare it against the actual character.
6. I get to the end of the input data without detecting any mismatch. So I return true. But only if the stack is empty, i.e., all the opening brackets have been consumed.

Solution accepted by HakerRank, test case and python script pushed to GitHub.

No comments:

Post a Comment