Balanced Parentheses Kata

Here's a quick solution to the balanced parentheses kata. The problem statement is:

Write a program to determine if the the parentheses (),
the brackets [], and the braces {}, in a string are balanced.

For example:

{{)(}} is not balanced because ) comes before (

({)} is not balanced because ) is not balanced between {}
     and similarly the { is not balanced between ()

[({})] is balanced

{}([]) is balanced

{()}[[{}]] is balanced

In a recent dojo we did some investigation of this, trying to find the best way to model the inner set of parentheses, maybe how to split the string and compare front and back halves, how to count the number of opening and closing but it struck me that we can model it very well by using a stack metaphor. When we open a parenthesis we push it onto the stack and when we close one we should have seen a matching open otherwise we consider it unbalanced. We know we have a balance at the end of the function if the stack is empty - that is, we have popped as many closing parentheses as we have pushed opening ones.

Code

First pass looked like this with lots of repeated code in brace comparisons:

def balanced(text):

    if len(text) % 2 != 0: return False
    
    stack = []
    
    for c in text:
        if c == '{' or c == '(' or c == '[':
            stack.append(c)
        elif c == '}' or c == ')' or c == ']':
            last = stack.pop()
            if c == '}' and last != '{':
                return False
            elif c == ')' and last != '(':
                return False
            elif c == ']' and last != '[':
                return False
    
    balances = len(stack) == 0
    
    return balances
    

We can also neatly match up opening and closing pairs by using a dictionary.

def balanced(text):
    stack = []
    pairs = { '{' :  '}',  '[' : ']', '(' : ')' }

    for paren in text:
        if paren in pairs.keys():
            stack.append(paren)
        else:
            
            if len(stack) == 0:
                return False
                
            last_opening_paren = stack.pop()
            expected_closing_paren = pairs[last_opening_paren]
            
            if paren != expected_closing_paren:
                return False
    
    return len(stack) == 0
    

If we find a closing character, we look at the previous paren and look up what we think should be the matching closing character and compare it to the one we have just read. If they don't match, that's an unbalanced case.

Unit Tests

from balance_kata import *
import unittest


class Test_BalanceParensKata(unittest.TestCase):
    
    def test_empty_strings_do_balance(self):
        self.assertTrue(balanced(''))
        
    def test_single_curly_braces_balance(self):
        self.assertTrue(balanced('{}'))

    def test_single_round_braces_balance(self):
        self.assertTrue(balanced('()'))

    def test_single_square_braces_balance(self):
        self.assertTrue(balanced('[]'))

    def test_multi_nested_braces_balance(self):
        self.assertTrue(balanced('[({})]'))

    def test_multi_opening_braces_donot_balance(self):
        self.assertFalse(balanced('[{'))

    def test_multi_closing_braces_donot_balance(self):
        self.assertFalse(balanced(')]}'))

    def test_interleaved_braces_donot_balance(self):
        self.assertFalse(balanced('({)}'))

    def test_multi_serial_braces_balance(self):
        self.assertTrue(balanced('{}()'))

    def test_multi_serial_nested_braces_balance(self):
        self.assertTrue(balanced('{()}[[{}]]'))


if __name__ == '__main__':
    unittest.main()