Python code for testing well parenthesized expression

[Duncan Booth]

John Machin <sjmachin at lexicon.net> wrote:

> Try an iterative version of checking that () [] and {}
> are balanced and nested appropriately.

Here's how I might approach the more general case:

def balanced(s, parens=("()",)):
    '''
    Example:
    >>> balanced('aAAA(b[bb(c]c))')
    True
    >>> balanced('aAAA(b[bb(c]c))', parens=("()", "[]"))
    False
    '''
    s = re.sub("[^%s]+" % re.escape("".join(parens)), "", s)
    for i in range(len(s)/2):
        for p in parens:
            s = s.replace(p, "")
    return not s

For short strings this is obviously slower than your 'iterative' function, 
but the run time mostly depends on the number of pairs of parentheses 
rather than the total length of the string, so for example it starts 
winning on a string with 2 pairs of parentheses about 75 characters long.