RegExp question: Find unmatched right bracket

[rkleiner@earthlink.net]

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

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

Thanks in advance.

[Dietmar Meier]

Re: RegExp question: Find unmatched right bracket

rkleiner@earthl ink.net wrote:
[color=blue]
> Is there a regular expression to find the first unmatched right
> bracket in a string, if there is one?[/color]

I don't think so. I would replace every matching pair of brackets
with two other characters and then use indexOf(")"):

var sText = "(1*(2+3))) )";
while (sText != (sText = sText.replace(/\(([^()]*)\)/, "_$1_")));
alert(sText.ind exOf(")"));

ciao, dhgm

[Dietmar Meier]

Re: RegExp question: Find unmatched right bracket

Dietmar Meier wrote:
[color=blue]
> while (sText != (sText = sText.replace(/\(([^()]*)\)/, "_$1_")));[/color]

Adding a "g" flag to the RegExp of cause would speed that up in
some cases:

[Dietmar Meier]

Re: RegExp question: Find unmatched right bracket

Dietmar Meier wrote:
[color=blue]
> while (sText != (sText = sText.replace(/\(([^()]*)\)/, "_$1_")));[/color]

Adding a "g" flag to the Regular Expression of cause would speed
that up in some cases:

while (sText != (sText = sText.replace(/\(([^()]*)\)/g, "_$1_")));

ciao, dhgm

[Lasse Reichstein Nielsen]

Re: RegExp question: Find unmatched right bracket

rkleiner@earthl ink.net writes:
[color=blue]
> Is there a regular expression to find the first unmatched right bracket
> in a string, if there is one? For example,[/color]

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 - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Lasse Reichstein Nielsen]

Re: RegExp question: Find unmatched right bracket

rkleiner@earthl ink.net writes:
[color=blue]
> Is there a regular expression to find the first unmatched right bracket
> in a string, if there is one?[/color]

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.c harAt(i)) {
case '(': cnt++; break;
case ')': cnt--; if (cnt < 0) {return i;}; break;
}
return -1;
}
---
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Dr John Stockton]

Re: RegExp question: Find unmatched right bracket

JRS: In article <1114188117.129 381.183830@o13g 2000cwo.googleg roups.com>
, dated Fri, 22 Apr 2005 09:41:57, seen in news:comp.lang. javascript,
rkleiner@earthl ink.net posted :[color=blue]
>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[/color]

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.c om/faq/> JL/RC: FAQ of news:comp.lang. javascript
<URL:http://www.merlyn.demo n.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

[Mark Szlazak]

Re: RegExp question: Find unmatched right bracket


rklei...@earthl ink.net wrote:[color=blue]
> Is there a regular expression to find the first unmatched right[/color]
bracket[color=blue]
> in a string, if there is one? For example,
>
> "(1*(2+3))))".s earch(/regexp/) == 9
>
> Thanks in advance.[/color]

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("unbalanc ed");

[Csaba Gabor]

Re: RegExp question: Find unmatched right bracket

Lasse Reichstein Nielsen wrote:[color=blue]
> rkleiner@earthl ink.net writes:
>[color=green]
>>Is there a regular expression to find the first unmatched right bracket
>>in a string, if there is one? For example,[/color]
>
> 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.[/color]

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(wh at(we)did)a))(n ot(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_CAP TURE);
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));
?>

[Lasse Reichstein Nielsen]

Re: RegExp question: Find unmatched right bracket

Csaba Gabor <csaba@z6.com > writes:

[recognizing matched parentheses][color=blue]
> 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).[/color]

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 - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Dr John Stockton]

Re: RegExp question: Find unmatched right bracket

JRS: In article <wtqu1yzc.fsf@h otpop.com>, dated Fri, 22 Apr 2005
19:51:35, seen in news:comp.lang. javascript, Lasse Reichstein Nielsen
<lrn@hotpop.com > posted :[color=blue]
>rkleiner@earth link.net writes:
>[color=green]
>> Is there a regular expression to find the first unmatched right bracket
>> in a string, if there is one? For example,[/color]
>
>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.[/color]


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.c om/faq/> JL/RC: FAQ of news:comp.lang. javascript
<URL:http://www.merlyn.demo n.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

[Mark Szlazak]

Re: RegExp question: Find unmatched right bracket


Dr John Stockton wrote:[color=blue]
> JRS: In article <wtqu1yzc.fsf@h otpop.com>, dated Fri, 22 Apr 2005
> 19:51:35, seen in news:comp.lang. javascript, Lasse Reichstein Nielsen
> <lrn@hotpop.com > posted :[color=green]
> >rkleiner@earth link.net writes:
> >[color=darkred]
> >> Is there a regular expression to find the first unmatched right[/color][/color][/color]
bracket[color=blue][color=green][color=darkred]
> >> in a string, if there is one? For example,[/color]
> >
> >No. It's a fundamental limit to the power of regular expressions[/color][/color]
that[color=blue][color=green]
> >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.[/color]
>
>
> I take it that you mean that one unaided application of a single[/color]
RegExp[color=blue]
> cannot do it.
>
>
> For equal numbers of each, by removing each type,
> S = "(()))"
> Ans = S.replace(/\(/g, "").length == S.replace(/\)/g,[/color]
"").length[color=blue]
>
> And
> while (S != (S=S.replace(/\([^\(\)]*\)/g, ""))) {}
> Balanced = !S.replace( /[^\(\)]/g, "")
> checks that each opener has a following closer, with no spare[/color]
closers.[color=blue]
>
> 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[/color]
IE 4 ©[color=blue]
> <URL:http://www.jibbering.c om/faq/> JL/RC: FAQ of[/color]
news:comp.lang. javascript[color=blue]
> <URL:http://www.merlyn.demo n.co.uk/js-index.htm> jscr maths, dates,[/color]
sources.[color=blue]
> <URL:http://www.merlyn.demo n.co.uk/> TP/BP/Delphi/jscr/&c, FAQ[/color]
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?

[Richard Cornford]

Re: RegExp question: Find unmatched right bracket

Mark Szlazak wrote:
<snip>[color=blue]
> 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.[/color]

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

- but:-

a = testString.repl ace(/[^(]/g, '');
b = testString.repl ace(/[^)]/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 = '))((';
}
[color=blue]
> Do you know of a quick even/odd test?[/color]

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

Richard.

[Randy Webb]

Re: RegExp question: Find unmatched right bracket

Richard Cornford wrote:[color=blue]
> Mark Szlazak wrote:
> <snip>
>[color=green]
>>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.[/color]
>
>
> ')))('.replace(/[^()]/, '').length ; //even
>
> - but:-
>
> a = testString.repl ace(/[^(]/g, '');
> b = testString.repl ace(/[^)]/g, '');
> if(a.length != b.lenght){[/color]

b.length??

:)

--
Randy

[Mick White]

Re: RegExp question: Find unmatched right bracket

Mark Szlazak wrote:
[snip][color=blue]
>
> 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?
>[/color]

isEven=num & 1;

Mick