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