On Jul 14, 1:10 pm, Duncan Booth <duncan.bo...@invalid.invalid> wrote:
> John Machin <sjmac...@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. :]
--
http://mail.python.org/mailman/listinfo/python-list
