RegExp question: Find unmatched right bracket

rk******@earthlink.net writes:

Is there a regular expression to find the first unmatched right bracket
in a string, if there is one? For example,

No. It's a fundamental limit to the power of regular expressions that
they cannot decide whether brackets are matched or not. They can't
even decide whether a string contains the same number of opening
and closing brackets.
/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #5

rk******@earthlink.net writes:

Is there a regular expression to find the first unmatched right bracket
in a string, if there is one?

Btw, a simple way of solving the problem would be:
---
function firstNonMatched(string) {
for(var i = 0,cnt=0; i < string.length; i++) {
switch(string.charAt(i)) {
case '(': cnt++; break;
case ')': cnt--; if (cnt < 0) {return i;}; break;
}
return -1;
}
---
/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #6

Dr John Stockton

JRS: In article <11**********************@o13g2000cwo.googlegroups .com>
, dated Fri, 22 Apr 2005 09:41:57, seen in news:comp.lang.javascript,
rk******@earthlink.net posted :

Is there a regular expression to find the first unmatched right bracket
in a string, if there is one? For example,

"(1*(2+3))))".search(/regexp/) == 9

Don't know.

The simple method is to read it character by character, counting :

function Scan(S) { var C, J, N = 0
for (J=0 ; J < S.length ; J++) { C = S.charAt(J)
if (C == "(") N++
if (C == ")") N--
if (N < 0) return J
}
}

Scan("(1*(2+3))))")

It can easily be modified to seek [ ] and { } pairs in the same scan;
and, with a little more effort, /* */ ones.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

Jul 23 '05 #7

rklei...@earthlink.net wrote:

Is there a regular expression to find the first unmatched right bracket in a string, if there is one? For example,

"(1*(2+3))))".search(/regexp/) == 9

Thanks in advance.

With JavaScripts regular expression capabilities you can't do it in
general like in later versions of Perl but there is a limited way to
check nested parenthesis balance without explicit counting in script
code. This pattern is hardcoded for nestings of up to four levels and
works for sample strings like yours but some QA maybe in order to
evaluated its limitations.

var rx = /$(?:[^()]|\((?:[^()]|\((?:[^()]|\([^()]*$)*\))*\))*\)/g;
var str = "(1*(2+3))))"
if ( (rx.exec( str ))[0].length == str.length ) alert ("balanced");
else alert("unbalanced");

Jul 23 '05 #8

Lasse Reichstein Nielsen wrote:

rk******@earthlink.net writes:
Is there a regular expression to find the first unmatched right bracket
in a string, if there is one? For example,

No. It's a fundamental limit to the power of regular expressions that
they cannot decide whether brackets are matched or not. They can't
even decide whether a string contains the same number of opening
and closing brackets.

But with PHP it is possible (using recursive matching described near the
bottom of the page from the Pattern Syntax link at http://php.net/pcre).
The code below uses a single regular expression to determine whether
parentheses match, or if not where the first unmatched right paren
is, or failing that the position of the last unmatched left paren
(this latter is the only reason for the preg_match_all instead of
just preg_match. If not needed set $leftToo=false).

Csaba Gabor from Vienna

<?php
// set $leftToo=true to report position of an unmatched '('
$leftToo = true;

$re = '/$((?>[^()]+)|(?R))*$/'; // recursive regular expression
$expR = "x()(()((1*(2+))3))a))(k)"; // some test cases
$expOK = "x()(()((1*(2+)3)()a))";
$expL = "x(y)(z)((k)(()((1*(2+)3()a))";
$expRL = "bill(wanted(what(we)did)a))(not(have sad)";

// Actual test case: we surround it with parens
$exp = "($expR)";

$matchFunc = "preg_match" . ($leftToo ? "_all" : "");
// do test here
call_user_func ($matchFunc, $re, $exp, &$aMatch, PREG_OFFSET_CAPTURE);
if ($leftToo) $aMatch = $aMatch[0]; // preg_match_all => extra level

// show results
print "Expression: " . substr($exp,1,-1) . "\n<br>";
if (($s0=&$aMatch[0][0])==$exp) print "all parens match";
else if (!$aMatch[0][1])
print "unmatched right paren at pos " . (strlen($s0)-2);
else print "unmatched left paren" .
(!$leftToo ? "" : " at pos " .
($aMatch[sizeof($aMatch)-1][1]-1));
?>

Jul 23 '05 #9

Csaba Gabor <cs***@z6.com> writes:

[recognizing matched parentheses]

But with PHP it is possible (using recursive matching described near the
bottom of the page from the Pattern Syntax link at http://php.net/pcre).

Fascinating. However, the feature is now so powerful that maybe it
shouldn't be called "regular expressions". It is capable of recognizing
non-regular languages, and probably all context free languages.

Alas, it's probably a lost cause for a computer science purist to have
them rename it "Context Free Expression" :) And it would not be
enough, since backwards matching even allows some languages that are
not context free.

Ah, back in the days when Regular Expresseions were really regular,
they could be compiled into finite automata, and you didn't need to
worry about stack depth. Those days are obviously long gone. Regular
expressions have become Swiss Army chainsaws of text matching :)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #10

Dr John Stockton

JRS: In article <wt**********@hotpop.com>, dated Fri, 22 Apr 2005
19:51:35, seen in news:comp.lang.javascript, Lasse Reichstein Nielsen
<lr*@hotpop.com> posted :

rk******@earthlink.net writes:
Is there a regular expression to find the first unmatched right bracket
in a string, if there is one? For example,

No. It's a fundamental limit to the power of regular expressions that
they cannot decide whether brackets are matched or not. They can't
even decide whether a string contains the same number of opening
and closing brackets.

I take it that you mean that one unaided application of a single RegExp
cannot do it.
For equal numbers of each, by removing each type,
S = "(()))"
Ans = S.replace(/$/g, "").length == S.replace(/$/g, "").length

And
while (S != (S=S.replace(/$[^\($]*\)/g, ""))) {}
Balanced = !S.replace( /[^]/g, "")
checks that each opener has a following closer, with no spare closers.

IIRC, though, that is not the most efficient way to tell whether a
..replace() has made a difference.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

Jul 23 '05 #11

Dr John Stockton wrote:

JRS: In article <wt**********@hotpop.com>, dated Fri, 22 Apr 2005
19:51:35, seen in news:comp.lang.javascript, Lasse Reichstein Nielsen
<lr*@hotpop.com> posted :
rk******@earthlink.net writes:
Is there a regular expression to find the first unmatched right bracket in a string, if there is one? For example,
No. It's a fundamental limit to the power of regular expressions thatthey cannot decide whether brackets are matched or not. They can't
even decide whether a string contains the same number of opening
and closing brackets.

I take it that you mean that one unaided application of a single

RegExp cannot do it.
For equal numbers of each, by removing each type,
S = "(()))"
Ans = S.replace(/$/g, "").length == S.replace(/$/g, "").length
And
while (S != (S=S.replace(/$[^\($]*\)/g, ""))) {}
Balanced = !S.replace( /[^]/g, "")
checks that each opener has a following closer, with no spare closers.
IIRC, though, that is not the most efficient way to tell whether a
.replace() has made a difference.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 © <URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript <URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources. <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ

items, links.

Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd. Do you know of a quick even/odd
test?

Jul 23 '05 #12

Richard Cornford

Mark Szlazak wrote:
<snip>

Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd.
')))('.replace(/[^()]/, '').length ; //even

- but:-

a = testString.replace(/[^(]/g, '');
b = testString.replace(/[^)]/g, '');
if(a.length != b.lenght){
// Parenthesise cannot match.
}else{
// There are the same numbers of each type of parenthesise.
// but that does not mean that nesting or sequence of
// parenthesise are "correct". var testString = '))((';
}
Do you know of a quick even/odd test?

if(n % 2){
// odd number (or non-integer)
}else{
// even number
}

Richard.

Jul 23 '05 #13

Randy Webb

Richard Cornford wrote:

Mark Szlazak wrote:
<snip>
Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd.

')))('.replace(/[^()]/, '').length ; //even

- but:-

a = testString.replace(/[^(]/g, '');
b = testString.replace(/[^)]/g, '');
if(a.length != b.lenght){

b.length??

:)

--
Randy

Jul 23 '05 #14

Mick White

Mark Szlazak wrote:
[snip]

Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd. Do you know of a quick even/odd
test?

isEven=num & 1;

Mick

Jul 23 '05 #15

fox

Mick White wrote:

Mark Szlazak wrote:
[snip]

Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd. Do you know of a quick even/odd
test?

isEven=num & 1;

ahem... isEven = ~num & 1;
isOdd = num & 1;

(i know it was a minor oversight...)
Mick

Jul 23 '05 #16

fox

Richard Cornford wrote:

Mark Szlazak wrote:
<snip>
Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd.

')))('.replace(/[^()]/, '').length ; //even

- but:-

a = testString.replace(/[^(]/g, '');
b = testString.replace(/[^)]/g, '');
if(a.length != b.lenght){
// Parenthesise cannot match.
}else{
// There are the same numbers of each type of parenthesise.
// but that does not mean that nesting or sequence of
// parenthesise are "correct". var testString = '))((';
}

[THANK YOU for pointing that out!!!]

no matter how you slice it -- this is a two pass test... one pass *must*
remove all legitimately balanced parens:

var hold = origStr;

/*this is destructive -- so in a real setting, origStr needs 2 copies:
copy and hold*/

while(hold !=(origStr = origStr.replace(/($[^\($]*\))/g,"")))
hold = origStr;

then test the remainder for orphan parens:

var left = (origStr.match(/$/g) || []).length;
var right = (origStr.match(/$/g) || []).length;

/* match returns 'null' if no matches -- so || with empty array for
length 0*/

var balance = left - right;

if balance is zero -- the string actually matches
less than zero -- stray left parens
greater than zero -- stray right parens

in the case of )( -- left and right are 1 but balance is zero, so the
test of "true" balance becomes:

var truebalance = !balance && !left && !right; (or any variation on this
test...like: !(balance | left | right) ... it has to be bitwise OR
because +/- anding cancel)

the var balance can be used to locate the first unbalanced paren --
if < 0 then iterate through an unaltered copy of the original string
using indexOf("(", startindex) and if > 0, iterate using lastIndexOf().
here's my offering: http://fxmahoney.com/demo/balancedParensObj.htm --
it seemed logical to prototype the method to the String object...it
returns an array of information about the string: balanced, index into
the string of first "offending" paren (or -1), left/right context if
unbalanced, a "display" string (red text shows "error range"), and the
results of the successive reduction regex, i.e., the leftovers (could be
useful...) [as I write, I'm thinking it should return the
leftContext/rightContext from RegExp which could be used to more quickly
isolate the offending parens...i'll work on it later]

source code on page is filtered through a php colorizing script -- view
source for the actual code (in case of discrepencies.)

the default string is unbalanced -- also try out:
this is an )absurd( use of parens... plus any other combination you can
think of... i don't claim this an authoritative solution by any stretch,
but so far, it seems to work in every case (i've tried)...

fox

Do you know of a quick even/odd test?

if(n % 2){
// odd number (or non-integer)
}else{
// even number
}

Richard.

Jul 23 '05 #17

Of course! I need more coffee before posting ;-)

Jul 23 '05 #18

fox

fox wrote:

Richard Cornford wrote:
Mark Szlazak wrote:
<snip>
Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd.
')))('.replace(/[^()]/, '').length ; //even

- but:-

a = testString.replace(/[^(]/g, '');
b = testString.replace(/[^)]/g, '');
if(a.length != b.lenght){
// Parenthesise cannot match.
}else{
// There are the same numbers of each type of parenthesise.
// but that does not mean that nesting or sequence of
// parenthesise are "correct". var testString = '))((';
}

[THANK YOU for pointing that out!!!]

no matter how you slice it -- this is a two pass test... one pass *must*
remove all legitimately balanced parens:

var hold = origStr;

/*this is destructive -- so in a real setting, origStr needs 2 copies:
copy and hold*/

while(hold !=(origStr = origStr.replace(/($[^\($]*\))/g,"")))
hold = origStr;

then test the remainder for orphan parens:

var left = (origStr.match(/$/g) || []).length;
var right = (origStr.match(/$/g) || []).length;

/* match returns 'null' if no matches -- so || with empty array for
length 0*/

var balance = left - right;

Sorry -- that's right - left...
if balance is zero -- the string actually matches
less than zero -- stray left parens
greater than zero -- stray right parens

in the case of )( -- left and right are 1 but balance is zero, so the
test of "true" balance becomes:

var truebalance = !balance && !left && !right; (or any variation on this
test...like: !(balance | left | right) ... it has to be bitwise OR
because +/- anding cancel)

the var balance can be used to locate the first unbalanced paren --
if < 0 then iterate through an unaltered copy of the original string
using indexOf("(", startindex) and if > 0, iterate using lastIndexOf().
here's my offering: http://fxmahoney.com/demo/balancedParensObj.htm --
it seemed logical to prototype the method to the String object...it
returns an array of information about the string: balanced, index into
the string of first "offending" paren (or -1), left/right context if
unbalanced, a "display" string (red text shows "error range"), and the
results of the successive reduction regex, i.e., the leftovers (could be
useful...) [as I write, I'm thinking it should return the
leftContext/rightContext from RegExp which could be used to more quickly
isolate the offending parens...i'll work on it later]

source code on page is filtered through a php colorizing script -- view
source for the actual code (in case of discrepencies.)

the default string is unbalanced -- also try out:
this is an )absurd( use of parens... plus any other combination you can
think of... i don't claim this an authoritative solution by any stretch,
but so far, it seems to work in every case (i've tried)...

fox

Do you know of a quick even/odd test?

if(n % 2){
// odd number (or non-integer)
}else{
// even number
}

Richard.

Jul 23 '05 #19

fox

then test the remainder for orphan parens:

var left = (origStr.match(/$/g) || []).length;
var right = (origStr.match(/$/g) || []).length;

/* match returns 'null' if no matches -- so || with empty array for
length 0*/

var balance = left - right;

Sorry -- that's supposed to be right - left...

Jul 23 '05 #20

Lasse Reichstein Nielsen wrote earlier:

No. It's a fundamental limit to the power of regular expressions that
they cannot decide whether brackets are matched or not. They can't
even decide whether a string contains the same number of opening
and closing brackets.
Lasse Reichstein Nielsen also wrote: Csaba Gabor <cs***@z6.com> writes:
[recognizing matched parentheses]
But with PHP it is possible (using recursive matching described near the
bottom of the page from the Pattern Syntax link at http://php.net/pcre).

Ah, back in the days when Regular Expresseions were really regular,
they could be compiled into finite automata, and you didn't need to
worry about stack depth. Those days are obviously long gone. Regular
expressions have become Swiss Army chainsaws of text matching :)

I hate to interrupt your reverie with the past and bemoaning the lost
days of youth and those happy memories of Aho, Hopcraft, and Ullman,
but I just had a thought about the other half of your problem: how to
decide with a SINGLE (PHP) reg exp whether a string contains the same
number of opening and closing parens:
$exp = "How's ()my) driving(";
$re = '/$((?>[^()]+)|(?R))*$/'; // same recursive reg exp

$L2 = ceil(strlen($exp)/2);
preg_match($re, $test = // test whether # of '(' == # of ')'
str_repeat("(",$L2) . $exp . str_repeat(")", $L2), $aMatch);

print $aMatch[0]==$test ? "paren count matches" :
"parens unbalanced";
Csaba Gabor
Note that floor (in place of ceil) doesn't work on "x" nor ")x("

Jul 23 '05 #21

Csaba Gabor wrote:

but I just had a thought about the other half of your problem: how to
decide with a SINGLE (PHP) reg exp whether a string contains the same
number of opening and closing parens: .... $L2 = ceil(strlen($exp)/2);
preg_match($re, $test = // test whether # of '(' == # of ')'
str_repeat("(",$L2) . $exp . str_repeat(")", $L2), $aMatch);

print $aMatch[0]==$test ? "paren count matches" :
"parens unbalanced";

Oops, that bottom part should change to account for heavily
imbalanced strings:

$exp = "))x)()))"; // or "))x)" won't match
$re = '/$((?>[^()]+)|(?R))*$/'; // same recursive reg exp

$L2 = ceil(strlen($exp)/2);
if (preg_match($re, $test = // test whether # of '(' == # of ')'
str_repeat("(",$L2) . $exp . str_repeat(")", $L2), $aMatch)
&& $aMatch[0]==$test)
print "Paren count matches";
else print "Parens unbalanced";
Csaba

Jul 23 '05 #22

rk******@earthlink.net wrote:

Is there a regular expression to find the first unmatched right bracket in a string, if there is one? For example,

"(1*(2+3))))".search(/regexp/) == 9

Thanks in advance.

This fixes my previous post. Still has the limitation of being
hardcoded for the number of levels of nesting. You could always make
the regex larger to cover more possible situations. Anyway it's the
best I can do with a single regular expression used only once.

var m, rx = /$(?:[^()]|\((?:[^()]|\((?:[^()]|\([^()]*$)*\))*\))*\)/g;
var str = "((1*((2+3))))";

if (m = str.match(rx)) {
if (m[0].length == str.length) alert ("balanced");
else alert("unbalanced or over nesting limit");
}
else alert("no match");

Jul 23 '05 #23

Dr John Stockton

JRS: In article <11**********************@l41g2000cwc.googlegroups .com>
, dated Sun, 24 Apr 2005 07:24:19, seen in news:comp.lang.javascript,
Mark Szlazak <ms******@aol.com> posted :

Following your lead John, one maybe able to check for balance by
replace all non () characters with blanks and then seeing if the
remaining string length is even or odd. Do you know of a quick even/odd
test?

Please read the newsgroup FAQ on formatting of responses.

What is a blank? It can only be a space, in which case the method is
useless. If they are replaced with nothing, then the evenness condition
is necessary but not sufficient. !S.length&1 determines evenness;
oddness is slightly easier. However, the basic approach is only capable
of detecting some cases of imbalance : the essence is to match pairs.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

Jul 23 '05 #24

Csaba Gabor <cs***@z6.com> writes:

I hate to interrupt your reverie with the past and bemoaning the lost
days of youth and those happy memories of Aho, Hopcraft, and Ullman,
*snif*
but I just had a thought about the other half of your problem: how to
decide with a SINGLE (PHP) reg exp whether a string contains the same
number of opening and closing parens:

Why settle for the same number. If you have recursive regular
expressions, you can do everything a one-terminal context free grammar
can do, including checking that the parentheses match! The traditional
grammar for matching parentheses is:

S ::= (S)S | <empty>

If I understand the Perl regexp syntax correctly, that would correspond to

$re = '/|$(?R)$(?R)/';

Or, with other chars in between:

$re2 = '/[^()]*(|$(?R)$(?R))/';

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #25

Mark Szlazak wrote:

rk******@earthlink.net wrote:
Is there a regular expression to find the first unmatched right bracket
in a string, if there is one? For example,

"(1*(2+3))))".search(/regexp/) == 9

Thanks in advance.

This fixes my previous post. Still has the limitation of being
hardcoded for the number of levels of nesting. You could always make
the regex larger to cover more possible situations. Anyway it's the
best I can do with a single regular expression used only once.

var m, rx =

/$(?:[^()]|\((?:[^()]|\((?:[^()]|\([^()]*$)*\))*\))*\)/g; var str = "((1*((2+3))))";

if (m = str.match(rx)) {
if (m[0].length == str.length) alert ("balanced");
else alert("unbalanced or over nesting limit");
}
else alert("no match");

Just a thought. It maybe possible to capture a subexpression that acts
as a flag for reaching the "nesting limit." For instance, capturing an
optional fifth opening parenthesis (\(?) in the regex for four levels
of nesting might work. ... Then again, it might not!

Jul 23 '05 #26