473,287 Members | 1,708 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,287 software developers and data experts.

need some regular expression help

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!

Oct 7 '06 #1
14 2219

Chris 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?
This is not possible with regular expressions - they can't "remember"
how many parens they already encountered.

You will need a real parser for this - pyparsing seems to be the most
popular choice today, I personally like spark. I'm sure you find an
example-grammar that will parse simple arithmetical expressions like
the one above.

Diez

Oct 7 '06 #2
Chris 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?
No, there is so such pattern. You will have to code up a function.

Consider what your spec really is: '42^((2x+2)sin(x)) +
(log(2)/log(5))' has the same number of left and right parentheses; so
does the zero-length string; so does ') + (' -- perhaps you need to add
'and starts with a "("'

Consider what you are going to do with input like this:

print '(' + some_text + ')'

Maybe you need to do some lexical analysis and work at the level of
tokens rather than individual characters.

Which then raises the usual question: you have a perception that
regular expressions are the solution -- to what problem??

HTH,
John

Oct 7 '06 #3
On 7 Oct 2006 15:00:29 -0700, Diez B. Roggisch <de***@web.dewrote:
>
Chris 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?

This is not possible with regular expressions - they can't "remember"
how many parens they already encountered.
Remember that regular expressions are used to represent regular
grammars. Most regex engines actually aren't regular in that they
support fancy things like look-behind/ahead and capture groups...IIRC,
these cannot be part of a true regular expression library.

With that said, the quote-unquote regexes in Lua have a special
feature that supports balanced expressions. I believe Python has a
PCRE lib somewhere; you may be able to use the experimental ??{ }
construct in that case.

-- Theerasak
Oct 8 '06 #4
In article <11*********************@e3g2000cwe.googlegroups.c om>,
"Chris" <ch*********@gmail.comwrote:
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.
Oct 8 '06 #5
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


Oct 8 '06 #6

hanumizzle wrote:
On 7 Oct 2006 15:00:29 -0700, Diez B. Roggisch <de***@web.dewrote:

Chris 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?
This is not possible with regular expressions - they can't "remember"
how many parens they already encountered.

Remember that regular expressions are used to represent regular
grammars. Most regex engines actually aren't regular in that they
support fancy things like look-behind/ahead and capture groups...IIRC,
these cannot be part of a true regular expression library.
Certainly true, and it always gives me a hard time because I don't know
to which extend a regular expression nowadays might do the job because
of these extensions. It was so much easier back in the old times....
With that said, the quote-unquote regexes in Lua have a special
feature that supports balanced expressions. I believe Python has a
PCRE lib somewhere; you may be able to use the experimental ??{ }
construct in that case.
Even if it has - I'm not sure if it really does you good, for several
reasons:

- regexes - even enhanced ones - don't build trees. But that is what
you ultimately want
from an expression like sin(log(x))

- even if they are more powerful these days, the theory of context
free grammars still applies.
so if what you need isn't LL(k) but LR(k), how do you specify that
to the regex engine?

- the regexes are useful because of their compact notations, parsers
allow for better structured outcome
Diez

Oct 8 '06 #7
On 8 Oct 2006 01:49:50 -0700, Diez B. Roggisch <de***@web.dewrote:
Even if it has - I'm not sure if it really does you good, for several
reasons:

- regexes - even enhanced ones - don't build trees. But that is what
you ultimately want
from an expression like sin(log(x))

- even if they are more powerful these days, the theory of context
free grammars still applies.
so if what you need isn't LL(k) but LR(k), how do you specify that
to the regex engine?

- the regexes are useful because of their compact notations, parsers
allow for better structured outcome
Just wait for Perl 6 :D

-- Theerasak
Oct 8 '06 #8
Tim Chase:
It still doesn't solve the aforementioned problem
of things like ')))(((' which is balanced, but psychotic. :)
This may solve the problem:

def balanced(txt):
d = {'(':1, ')':-1}
tot = 0
for c in txt:
tot += d.get(c, 0)
if tot < 0:
return False
return tot == 0

print balanced("42^((2x+2)sin(x)) + (log(2)/log(5))") # True
print balanced("42^((2x+2)sin(x) + (log(2)/log(5))") # False
print balanced("42^((2x+2)sin(x))) + (log(2)/log(5))") # False
print balanced(")))(((") # False

A possibile alternative for Py 2.5. The dict solution looks better, but
this may be faster:

def balanced2(txt):
tot = 0
for c in txt:
tot += 1 if c=="(" else (-1 if c==")" else 0)
if tot < 0:
return False
return tot == 0

Bye,
bearophile

Oct 8 '06 #9
be************@lycos.com wrote:
The dict solution looks better, but this may be faster:
it's slightly faster, but both your alternatives are about 10x slower
than a straightforward:

def balanced(txt):
return txt.count("(") == txt.count(")")

</F>

Oct 8 '06 #10
Thus spoke Diez B. Roggisch (on 2006-10-08 10:49):
Certainly true, and it always gives me a hard time because I don't know
to which extend a regular expression nowadays might do the job because
of these extensions. It was so much easier back in the old times....
Right, in perl, this would be a no-brainer,
its documented all over the place, like:

my $re;

$re = qr{
(?:
(?[^\\()]+ | \\. )
|
\( (??{ $re }) \)
)*
}xs;

where you have a 'delayed execution'
of the

(??{ $re })

which in the end makes the whole a thing
recursive one, it gets expanded and
executed if the match finds its way
to it.

Above regex will match balanced parens,
as in:

my $good = 'a + (b / (c - 2)) * (d ^ (e+f)) ';
my $bad1 = 'a + (b / (c - 2) * (d ^ (e+f)) ';
my $bad2 = 'a + (b / (c - 2)) * (d) ^ (e+f) )';

if you do:

print "ok \n" if $good =~ /^$re$/;
print "ok \n" if $bad1 =~ /^$re$/;
print "ok \n" if $bad2 =~ /^$re$/;
This in some depth documented e.g. in
http://japhy.perlmonk.org/articles/tpj/2004-summer.html
(topic: Recursive Regexes)

Regards

M.
Oct 8 '06 #11
Mirco Wahab schrieb:
Thus spoke Diez B. Roggisch (on 2006-10-08 10:49):
>Certainly true, and it always gives me a hard time because I don't know
to which extend a regular expression nowadays might do the job because
of these extensions. It was so much easier back in the old times....

Right, in perl, this would be a no-brainer,
its documented all over the place, like:

my $re;

$re = qr{
(?:
(?[^\\()]+ | \\. )
|
\( (??{ $re }) \)
)*
}xs;

where you have a 'delayed execution'
of the

(??{ $re })

which in the end makes the whole a thing
recursive one, it gets expanded and
executed if the match finds its way
to it.

Above regex will match balanced parens,
as in:

my $good = 'a + (b / (c - 2)) * (d ^ (e+f)) ';
my $bad1 = 'a + (b / (c - 2) * (d ^ (e+f)) ';
my $bad2 = 'a + (b / (c - 2)) * (d) ^ (e+f) )';

if you do:

print "ok \n" if $good =~ /^$re$/;
print "ok \n" if $bad1 =~ /^$re$/;
print "ok \n" if $bad2 =~ /^$re$/;
This in some depth documented e.g. in
http://japhy.perlmonk.org/articles/tpj/2004-summer.html
(topic: Recursive Regexes)
That clearly is a recursive grammar rule, and thus it can't be regular
anymore :) But first of all, I find it ugly - the clean separation of
lexical and syntactical analysis is better here, IMHO - and secondly,
what are the properties of that parsing? Is it LL(k), LR(k), backtracking?

Diez
Oct 8 '06 #12
Fredrik Lundh wrote:
it's slightly faster, but both your alternatives are about 10x slower
than a straightforward:
def balanced(txt):
return txt.count("(") == txt.count(")")
I know, but if you read my post again you see that I have shown those
solutions to mark ")))(((" as bad expressions. Just counting the parens
isn't enough.

Bye,
bearophile

Oct 8 '06 #13
"Diez B. Roggisch" <de***@web.dewrote:
Certainly true, and it always gives me a hard time because I don't know
to which extend a regular expression nowadays might do the job because
of these extensions. It was so much easier back in the old times....
What old times? I've been working with regex for mumble years and there's
always been the problem that every implementation supports a slightly
different syntax. Even back in the "good old days", grep, awk, sed, and ed
all had slightly different flavors.
Oct 8 '06 #14
On 10/8/06, Roy Smith <ro*@panix.comwrote:
"Diez B. Roggisch" <de***@web.dewrote:
Certainly true, and it always gives me a hard time because I don't know
to which extend a regular expression nowadays might do the job because
of these extensions. It was so much easier back in the old times....

What old times? I've been working with regex for mumble years and there's
always been the problem that every implementation supports a slightly
different syntax. Even back in the "good old days", grep, awk, sed, and ed
all had slightly different flavors.
Which grep? Which awk? :)

-- Theerasak
Oct 8 '06 #15

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Neri | last post by:
Some document processing program I write has to deal with documents that have headers and footers that are unnecessary for the main processing part. Therefore, I'm using a regular expression to go...
2
by: hillcountry74 | last post by:
Hi, I'm stuck with this regular expression from past 2 days. Desperately need help. I need a regular expression that will allow all characters except these *:~<>' This is my code in...
3
by: Joe | last post by:
Hi, I have been using a regular expression that I don’t uite understand to filter the valid email address. My regular expression is as follows: <asp:RegularExpressionValidator...
18
by: Q. John Chen | last post by:
I have Vidation Controls First One: Simple exluce certain special characters: say no a or b or c in the string: * Second One: I required date be entered in "MM/DD/YYYY" format: //+4 How...
7
by: Billa | last post by:
Hi, I am replaceing a big string using different regular expressions (see some example at the end of the message). The problem is whenever I apply a "replace" it makes a new copy of string and I...
9
by: Pete Davis | last post by:
I'm using regular expressions to extract some data and some links from some web pages. I download the page and then I want to get a list of certain links. For building regular expressions, I use...
3
by: Lucky | last post by:
hi guys, i'm practising regular expression. i've got one string and i want it to split in groups. i was trying to make one regular expression but i didn't successed. please help me guys. i'm...
25
by: Mike | last post by:
I have a regular expression (^(.+)(?=\s*).*\1 ) that results in matches. I would like to get what the actual regular expression is. In other words, when I apply ^(.+)(?=\s*).*\1 to " HEART...
6
by: deepak_kamath_n | last post by:
Hello, I am relatively new to the world of regex and require some help in forming a regular expression to achieve the following: I have an input stream similar to: Slot: slot1 Description:...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.