Pages

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.