need some regular expression help
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
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