need some regular expression help

Roy Smith roy at panix.com
Sun Oct 8 04:30:06 CEST 2006


In article <1160256609.555007.83170 at e3g2000cwe.googlegroups.com>,
 "Chris" <chrispatton at gmail.com> wrote:

> I need a pattern that  matches a string that has the same number of '('
> as ')':
> findall( compile('...'), '42^((2x+2)sin(x)) + (log(2)/log(5))' ) = [
> '((2x+2)sin(x))', '(log(2)/log(5))' ]
> Can anybody help me out?
> 
> Thanks for any help!

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.



More information about the Python-list mailing list