Python code for testing well parenthesized expression

[Simon Forman]

On Jul 14, 1:10 pm, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> John Machin <sjmac... 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.


def balanced(s, pairs=('()', '[]', '{}')):
    opening = {}
    closing = {}
    for open_, close in pairs:
        opening[open_] = closing[close] = object()

    stack = []

    for char in s:

        marker = opening.get(char)
        if marker:
            stack.append(marker)
            continue

        marker = closing.get(char)
        if marker:
            try:
                if stack.pop() is not marker:
                    return False
            except IndexError:
                return False

    # All markers should be popped.
    return not stack


Can parse sequences other than strings. :]