RegExp question: Find unmatched right bracket

[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...

 

[Csaba Gabor]

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.

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("

 

[Csaba Gabor]

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

 

[Mark Szlazak]

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");

 

[Lasse Reichstein Nielsen]

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

 

[Mark Szlazak]

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!

 

[Csaba Gabor]

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>

Can't beat that for compact

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

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

Or, with other chars in between:

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

The problem with these expressions is that (the recursive part) will
match anything (as opposed to the longest possible match) so why
should the expression bother doing any work? It will always return
the empty string as a match (or a variant thereof, for $re2)!

On the other hand if you anchor it with ^ and $, then the recursive
part is destroyed.

In the examples I gave, with
$re = '/\(((?>[^()]+)|(?R))*\)/';

the 'anchoring' is accomplished in the pattern by
1) a pair of external parens, to test for balanced parens
2) or lots of external balanced parens, to test for equal numbers of parens

so that a size check of the matched expression is necessary at the end.
It would be great if your approach could be shored up, however.

Csaba