Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Parens Matching

Reply
Thread Tools

Parens Matching

 
 
Ken Kast
Guest
Posts: n/a
 
      02-16-2007
Does anyone have a regular expression pattern that would include a test for
balanced parens of arbitrary nestedness?


 
Reply With Quote
 
 
 
 
IchBin
Guest
Posts: n/a
 
      02-16-2007
Ken Kast wrote:
> Does anyone have a regular expression pattern that would include a test for
> balanced parens of arbitrary nestedness?


Is arbitrary 'nestedness' some new type of epistemological terminology?

Sorry, just could not stop myself.

--
Thanks in Advance... http://weconsultants.prophp.org
IchBin, Pocono Lake, Pa, USA http://ichbinquotations.awardspace.com
__________________________________________________ ____________________
'If there is one, Knowledge is the "Fountain of Youth"'
-William E. Taylor, Regular Guy (1952-)
 
Reply With Quote
 
 
 
 
Ken Kast
Guest
Posts: n/a
 
      02-16-2007
Nope. Something I made up in order to make the message not so dry.

"IchBin" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Ken Kast wrote:
>> Does anyone have a regular expression pattern that would include a test
>> for balanced parens of arbitrary nestedness?

>
> Is arbitrary 'nestedness' some new type of epistemological terminology?
>
> Sorry, just could not stop myself.
>
> --
> Thanks in Advance... http://weconsultants.prophp.org
> IchBin, Pocono Lake, Pa, USA http://ichbinquotations.awardspace.com
> __________________________________________________ ____________________
> 'If there is one, Knowledge is the "Fountain of Youth"'
> -William E. Taylor, Regular Guy (1952-)



 
Reply With Quote
 
Michael
Guest
Posts: n/a
 
      02-16-2007
On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
> Does anyone have a regular expression pattern that would include a test for
> balanced parens of arbitrary nestedness?


No. No one does.

There's a well known proof in Computer Science theory that it is not
possible to create a regular expression for balanced parentheses.

Look up "the pumping lemma" for details.

Michael

 
Reply With Quote
 
Mark Jeffcoat
Guest
Posts: n/a
 
      02-16-2007
"Michael" <(E-Mail Removed)> writes:

> On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
>> Does anyone have a regular expression pattern that would include a test for
>> balanced parens of arbitrary nestedness?

>
> No. No one does.
>
> There's a well known proof in Computer Science theory that it is not
> possible to create a regular expression for balanced parentheses.
>


Michael is quite right. Of course, that proof is silent
on the subject of creating a regular expression that accepts
balanced strings with at most Long.MAX_VALUE open parens.
(And really, most texts will have fewer than half that many.)

While you're waiting for the program you wrote to write that
regular expression to finish, you can pass the time with a
counter that increments on '(', and decrements on ')'.

--
Mark Jeffcoat
Austin, TX
 
Reply With Quote
 
Tim Slattery
Guest
Posts: n/a
 
      02-16-2007
"Michael" <(E-Mail Removed)> wrote:

>On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
>> Does anyone have a regular expression pattern that would include a test for
>> balanced parens of arbitrary nestedness?

>
>No. No one does.
>
>There's a well known proof in Computer Science theory that it is not
>possible to create a regular expression for balanced parentheses.


OTOH, it would be pretty simple to write a loop that cycles through a
string and keeps track of left and right parens. Add 1 to the counter
when you find a left paren, subtract one for a right paren. If the
counter ever goes negative, throw an error. If it's not zero at the
end of the string, throw an error.

--
Tim Slattery
http://www.velocityreviews.com/forums/(E-Mail Removed)
http://members.cox.net/slatteryt
 
Reply With Quote
 
Michael
Guest
Posts: n/a
 
      02-16-2007
> >There's a well known proof in Computer Science theory that it is not
> >possible to create a regular expression for balanced parentheses.

>
> OTOH, it would be pretty simple to write a loop that cycles through a
> string and keeps track of left and right parens. Add 1 to the counter
> when you find a left paren, subtract one for a right paren. If the
> counter ever goes negative, throw an error. If it's not zero at the
> end of the string, throw an error.


I guess I should have spelled it out further - you can't match
balanced parentheses *with a regular expression.* Of course, there
are other ways to do it. Either write the kind or program above, or
write a recursive decent parser, (or use a regular expression that
only matches up to N balanced parentheses) etc. Basically, balanced
parentheses aren't a regular grammar, they're a context free grammar,
so you need a more powerful tool. In particular, they're a grammar
somthing like this:
Expression -> nothing | ( Expression )

Sorry if I caused more confusion that I removed. It was late.

Michael

 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      02-17-2007
On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
> Does anyone have a regular expression pattern that would include a test for
> balanced parens of arbitrary nestedness?


Two ways:

public class NestedParens {
public static void main(String[] args) {
String[] strings = {
"Test case 1",
"(Test case 2)",
"((Test) case ) 3",
")test case 4 (",
};
for (String string: strings) {
System.out.println(string +
" is " + (isBalancedRe(string)
?
"Balanced" : "Mis-matched"));
}

for (String string: strings) {
System.out.println(string +
" is " + (isBalancedCount(string)
?
"Balanced" : "Mis-matched"));
}
}

public static boolean isBalancedRe(String string) {
String last;
do {
last = string;
string = string.replaceAll("\\([^()]*\\)", "");
} while (!last.equals(string));
return !string.matches(".*[()].*");
}

private static boolean isBalancedCount(String string) {
int parens = 0;
for (char c : string.toCharArray()) {
switch (c) {
case ')':
if (--parens < 0) {
return false;
}
break;
case '(':
++parens;
}
}
return parens == 0;
}
}

 
Reply With Quote
 
Alex Hunsley
Guest
Posts: n/a
 
      02-17-2007
Michael wrote:
> On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
>> Does anyone have a regular expression pattern that would include a test for
>> balanced parens of arbitrary nestedness?

>
> No. No one does.
>
> There's a well known proof in Computer Science theory that it is not
> possible to create a regular expression for balanced parentheses.
>
> Look up "the pumping lemma" for details.


That thang always made me think of either pumping lemons or pumping
lemmings.

The matched parenthesis problem can be done with a non-deterministic
state machine, but not with a deterministic one.... hence no regular
expression can do it.
 
Reply With Quote
 
Alex Hunsley
Guest
Posts: n/a
 
      02-17-2007
Tim Slattery wrote:
> "Michael" <(E-Mail Removed)> wrote:
>
>> On Feb 15, 7:34 pm, "Ken Kast" <(E-Mail Removed)> wrote:
>>> Does anyone have a regular expression pattern that would include a test for
>>> balanced parens of arbitrary nestedness?

>> No. No one does.
>>
>> There's a well known proof in Computer Science theory that it is not
>> possible to create a regular expression for balanced parentheses.

>
> OTOH, it would be pretty simple to write a loop that cycles through a
> string and keeps track of left and right parens. Add 1 to the counter
> when you find a left paren, subtract one for a right paren. If the
> counter ever goes negative, throw an error. If it's not zero at the
> end of the string, throw an error.


Although even this isn't correct, in theory... due to the finite memory
of the computer, it is possible to give it a sequence that should pass
(the brackets match), but won't pass, because the computer runs out of
memory. Ok, a little silly, but...


>
> --
> Tim Slattery
> (E-Mail Removed)
> http://members.cox.net/slatteryt

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
regex extension to handle matching parens? ivo welch Ruby 5 01-24-2009 04:35 PM
How to avoid "f.close" (no parens) bug? Stephen Ferg Python 12 02-13-2004 06:40 AM
RE: How to avoid "f.close" (no parens) bug? Batista, Facundo Python 2 02-11-2004 09:28 PM
RE: How to avoid "f.close" (no parens) bug? Batista, Facundo Python 2 02-11-2004 07:54 PM
matching balanced parens ivo welch Perl Misc 3 12-27-2003 06:32 PM



Advertisments