re question - finiding matching ()

Dan Bishop danb_83 at yahoo.com
Mon Jan 19 00:08:48 CET 2004


Jeff Epler <jepler at unpythonic.net> wrote in message news:<mailman.475.1074449209.12720.python-list at python.org>...
> Regular Expressions cannot perform the simple task of matching an
> arbitrary number of parentheses.  You could write an expression that
> will work as long as the nesting isn't more than N levels, but the
> expression quickly becomes very painful.
> 
> Instead, you can use some method to split the string into parts: one
> part for "(", one for ")" and one for any other sequence of characters:
...
> Now, start scanning and counting parens, until you get back to 0

That's the way I'd recommend.  However, it doesn't generalize to cases
where there are multiple types of parentheses.  For that situation,
you can use:

LEFT_PARENS =  '([{'
RIGHT_PARENS = ')]}'
PAREN_MATCHES = dict(zip(RIGHT_PARENS, LEFT_PARENS))

def balancedParens(tokens):
   parenStack = []
   for token in tokens:
      if token in LEFT_PARENS:
         parenStack.append(token)
      elif token in RIGHT_PARENS:
         if parenStack:
            correspondingLeftParen = parenStack.pop()
            if PAREN_MATCHES[token] != correspondingLeftParen:
               return False
         else:
            return False
   return True

(There's probably a simpler way, but I can't think of one right now.)



More information about the Python-list mailing list