检查字符串中括号是否不匹配的正则表达式?

21
在PHP脚本中,我应该使用什么正则表达式来检查字符串中不匹配的括号? 我想要允许的内容包括:
  • This is (ok)
  • This (is) (ok)

我想要防止的内容:

  • This is )bad(
  • This is also (bad
  • This is (bad (too)

谢谢!

更新:你们都很棒。尝试使用正则表达式解决这个问题似乎比应该的更棘手,这些第二层次的答案是使stackoverflow美丽的原因之一。感谢提供链接和伪代码。我不确定该把答案给谁,所以我向那些我无法接受答案的人道歉。


你需要任意嵌套的括号,还是你确定任何输入字符串中最多只有固定层次(比如说5层深度)的嵌套可能性? - jfs
字符串长度限制在约300个字符左右。虽然可以连续输入300个字符,但这很可能是用户输入造成的。 - twk
8个回答

27

正则表达式不是解决这个问题的正确工具。手动扫描字符串。

伪代码:

depth = 0
for character in some_string:
    depth += character == '('
    depth -= character == ')'
    if depth < 0:
       break

if depth != 0:
   print "unmatched parentheses"

23

您可以使用正则表达式进行此操作 - PHP使用的PCRE允许递归模式。PHP手册提供了一个示例,几乎与您想要的一样:

\(((?>[^()]+)|(?R))*\)

这个正则表达式匹配任何以圆括号开始和结束的正确括号子字符串。如果您想确保整个字符串是平衡的,并允许像“wiggedy(wiggedy)(wiggedy(wack))”这样的字符串,这就是我想出的:

^((?:[^()]|\((?1)\))*+)$

下面是一个比较易懂的正则表达式模式解释:

^             字符串开头
(             开始"平衡子字符串"组(将被递归调用)
  (?:         开始“最小平衡子字符串”组
    [^()]     最小平衡子字符串是非括号字符
    |         或者
    \((?1)\)  包含一个平衡子字符串的一组括号
  )           结束“最小平衡子字符串”组
  *           我们的平衡子字符串是最小平衡子字符串的最大序列
  +           一旦我们匹配到最大序列就不回溯
)             结束“平衡子字符串”模式
$             字符串结尾

这类正则表达式涉及的效率和正确性方面需要注意。


+1. Perl也可以通过(??{ code })扩展实现。许多(大多数?)现代语言的“正则表达式”引擎严格来说比正则语言/DFAs更强大。 - Brian Carper
Perl有相同的(?R)子组。但这个功能以及(??{code})都是高度实验性的,文档说明它们的确切副作用可能会在版本之间发生变化。因此,在生产代码中,不要尝试在有限自动机(PCRE)中使用黑客技巧。 - Chris Lutz
Chris,你有“高度实验性”警告的参考资料吗?PCRE手册在http://www.pcre.org/pcre.txt上没有提到这一点。 - Bennett McElwee
这是一个非常危险的特性。使用递归标记既可能导致灾难性的回溯(导致PCRE崩溃),也可能导致过量的内存消耗(终止脚本执行),尤其是在使用捕获组时。对于像这样简单的情况,最好根本不使用正则表达式! - Ben Blank
2
这个在正则表达式中是真实的。没有使用递归可能很容易发生灾难性回溯。正则表达式最好的一点是其极大的能力和灵活性。正则表达式最糟糕的一点是其极大的能力和灵活性。 - Bennett McElwee
显示剩余3条评论

8

递归和计数在某些语言的正则表达式引擎中是可用的功能,比如 Perl 和 PHP。请参见 Bennett McElwee 的答案。Perl 在 CPAN 中有一个 Regexp::Common::balanced 模块可实现此功能。 - Brian Carper
@Brian,这更多是一个语义争论,但在正则表达式可以进行递归的时候,它实际上不再是一个正则表达式了。它是一个上下文无关文法。我意识到这对大多数人来说实际上毫无意义,而递归正则表达式正在迅速成为必备功能。 - JaredPar
你说得没错,但我认为在回答OP的问题时,重要的是要指出无论PHP称之为“正则表达式”,它实际上可以做到他所要求的。 (希望它们仍然被称为“正则表达式”一段时间,因为cfgex听起来不太好听。 :) - Brian Carper
@Brian,我其实没有意识到PHP的正则表达式具有递归功能(通常使用.Net版本)。cregex很糟糕。我喜欢modregex,但那会让Perl的人感到困惑。也许可以用rrregex(递归准备好的正则表达式)。不过你得用一个“Tony the tiger frosted flakes”声音来说它。 - JaredPar

3

你的示例中没有包含任何嵌套括号... 如果你不关心嵌套,那么可以使用以下表达式:

^[^()]*(?:\([^()]*\)[^()]*)*$

这将匹配您的“允许”列表中的所有字符串,并失败于您的“防止”列表中的字符串。但是,它也会失败于任何带有嵌套括号的字符串。例如,“this (is (not) ok)”。
正如其他人已经指出的那样,如果需要处理嵌套,则正则表达式不是正确的工具。

3

同意使用正则表达式无法实现这一点。不过,您可以尝试以下方法:

<?php

$testStrings = array( 'This is (ok)', 'This (is) (ok)', 'This is )bad(', 'This is also (bad', 'This is (bad (too)' );

foreach( $testStrings as $string ) {
    $passed = hasMatchedParentheses( $string ) ? 'passed' : 'did not pass';
    echo "The string $string $passed the check for matching parenthesis.\n";
}

function hasMatchedParentheses( $string ) {
    $counter = 0;
    $length = strlen( $string );
    for( $i = 0; $i < $length; $i ++ ) {
        $char = $string[ $i ];
        if( $char == '(' ) {
            $counter ++;
        } elseif( $char == ')' ) {
            $counter --;
        }
        if( $counter < 0 ) {
            return false;
        }
    }
    return $counter == 0;
}

?>

2

扩展JaredPar的答案,不使用正则表达式也可以很容易地解决,只需编写一个检查字符串中每个字符并增加/减少计数器的函数。如果找到“(”,则将其增加,如果找到“)”,则将其减少。如果计数器小于0,则可以中断,该字符串无效。当您处理整个字符串时,如果计数器不为0,则存在未匹配的开括号。


1

为什么正则表达式无法实现括号匹配

其他答案都是正确的,但我想强调一下理论计算机科学的重要性...这是一个知道理论可以带来实际优势的例子。

正则表达式对应于确定有限状态自动机(DFA),但括号匹配需要上下文无关文法,可以通过有限状态自动机(PDA)实现,但不能通过DFA实现。

因此,我们知道答案是否定的,而不必担心我们可能会忽略某些东西。所以,你可以对以上答案感到自信,并且不必担心作者在给出答案时是否忽略了某些东西。

几乎所有编译器书籍都会谈到这个问题,以下是一个简要概述:

http://books.google.com/books?id=4LMtA2wOsPcC&pg=PA94&lpg=PA94&dq=push-down+finite+automata&source=bl&ots=NisYwNO1r0&sig=ajaSHFXwpPOWG8IfbcfKoqzS5Wk&hl=en&ei=m26cSdf6DZGYsAPB-6SsAg&sa=X&oi=book_result&resnum=6&ct=result


这并不完全正确。正则表达式在PHP和许多其他上下文中使用时,实际上并不是严格意义上的正则表达式。它们添加了许多功能,使它们更有用,并将其扩展到真正的正则表达式无法完成的领域。这就是为什么这个问题是可以解决的原因。 - Bennett McElwee
哦,是什么功能?你有一个可以在“((()))”、“()()()”、“((”或“()))”上运行的示例吗? - Mark Harrison
递归子模式功能。请查看我对这个问题的答案,它可以正确处理您提供的四个示例。 - Bennett McElwee

0

不使用正则表达式的 PHP 编程:

function analyse($input){
    $len = strlen($input);
    $depth = 0;
    for ($i = 0; $i < $len; $i++) {
        $depth += $input[$i] == '(';
        $depth -= $input[$i] == ')';
        if ($depth < 0) break;
    }
    if ($depth != 0) return false;
        else return true;
}
$check_nestled = analyse('(5 * 2) + ((2 + 2) - 4)');
if($check_nestled){
    // do stuff, everything is ok
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接