need some regular expression help

Tim Chase python.list at tim.thechases.com
Sun Oct 8 05:12:34 CEST 2006


> Why does it need to be a regex?  There is a very simple and well-known 
> algorithm which does what you want.
> 
> Start with i=0.  Walk the string one character at a time, incrementing i 
> each time you see a '(', and decrementing it each time you see a ')'.  At 
> the end of the string, the count should be back to 0.  If at any time 
> during the process, the count goes negative, you've got mis-matched 
> parentheses.
> 
> The algorithm runs in O(n), same as a regex.
> 
> Regex is a wonderful tool, but it's not the answer to all problems.

Following Roy's suggestion, one could use something like:

 >>> s = '42^((2x+2)sin(x)) + (log(2)/log(5))'
 >>> d = {'(':1, ')':-1}
 >>> sum(d.get(c, 0) for c in s)
0


If you get a sum() > 0, then you have too many "(", and if you 
have sum() < 0, you have too many ")" characters.  A sum() of 0 
means there's the same number of parens.  It still doesn't solve 
the aforementioned problem of things like ')))((('  which is 
balanced, but psychotic. :)

-tkc







More information about the Python-list mailing list