Balanced Brackets

Let us define a simple recursive language:

balanced = '()' | '(', balanced, ')' | balanced, balanced;

The theorems (valid clauses) of our language are made up only of the parentheses. We will call a string 'balanced' if and only if it can be expressed in our language. A friendlier definition of a balanced string is as follows:

• () is a balanced string
• Putting a balanced string inside a pair of opening and closing parentheses forms a balanced string
• Concatenating two balanced strings forms a balanced string

Here are some examples:

Balanced

()
(())
()()
(()())
((()(()))()(()()))
((())(()))((())(()))

Not balanced

(
)
((
))
)(
(()
())
(()()(())

The task is to write a program which determines whether a given string is balanced. Additionally, the algorithm must reflect the language's definition as closely as possible. To reflect this goal I'm going to propose an arbitrary restriction: the algorithm should not involve any change in state. The only exception is the string being tested, which may change. Essentially what this means is that you can't use any variables which change their value. The algorithm will also almost certainly be recursive -- which makes sense because the language is defined recursively as well.

---

This took me a frustratingly long time. I rewrote the code several times over, each time slightly changing my algorithm to make it cleaner and more logical.

My function takes two parameters: a 'string' to test' (which is actually a list of that string, string) and a character which, when found at the same recursive depth, will signify that the string is balanced (expected).

The first thing in the function is a loop for handling cases where there are two or more balanced strings sitting at the same recursive depth.

I get the first element of the string (while at the same time removing it -- str.pop has that side effect) and store it in the variable first. I then do three tests:

• If first is an opening parenthesis, I check if the string following it is balanced by recursively calling the function on the rest of string. I also tell it to stop when it reaches a ) character on the same recursive depth. If it tells me that it's not balanced, I stop and return False (if the substring isn't balanced then the whole string isn't balanced).
• If first == expecting, this string (possibly a substring) is balanced because we've reached the closing character on the same recursive level as the opening one and so everything in between must have been balanced.
• If anything else has happened, the string isn't balanced and we return False.

The loop can only quit normally (without getting out via a return statement) in two ways:

• The string ended prematurely. In this case, we will still be expecting something, so the expression 'not expecting' will return False. Since the string ended prematurely the string isn't balanced, so we return False correctly.
• The string ended at the top recursive level as it should. We aren't expecting anything, so it will return True.

def balanced(string, expecting=False):
    while string:
        first = string.pop(0)
        if first == '(':
            if not balanced(string, ')'):
                return False
        elif first == expecting:
            return True
        else:
            return False
    return not expecting

And my testing:

assert balanced(list('((()))'))
assert balanced(list('()'))
assert balanced(list('()()'))
assert balanced(list('(())((()))'))
assert balanced(list('()(()()(())()((())()))'))
assert balanced(list('(((((((()))())())())()))'))
assert balanced(list('((()(())())(())()(()()))'))
assert not balanced(list(')('))
assert not balanced(list('(('))
assert not balanced(list('()))'))
assert not balanced(list('(((()))'))
assert not balanced(list(')))'))
assert not balanced(list('(()'))
assert not balanced(list('(()()()'))

Drawing the Koch Curve in Turtle

I love this fractal because it's so simple! I barely need to obfuscate the code and its definition still fits in 3 fairly neat lines. It's simple enough that I won't even bother giving an explanation so as not to insult your intelligence. If you're having trouble understanding the t.forward line, I explain that construction in my explanation for the Dragon Curve Fractal in Turtle (my first post).

import turtle
t = turtle.Pen()

def koch(dist):
    for angle in (60, -120, 60, 0):
        (t.forward if dist <= 10 else koch)(dist / 3.0)  # 10 is the break case. 3.0 is the line:subline ratio
        t.left(angle)

koch(400)