javascript - 请问正则如何匹配多层成对的括号？

Question

"()" => returns true
")(()))" => returns false
"(" => returns false
"(())((()())())" => returns true

形如这种，我可以做到匹配2,3层的没问题，但是层数多了就不知道该怎么办了

Answer 1

如果你要通过正则表达式来完成这个匹配比较困难。但是如果你纯粹时想看看括号是不是左右成对匹配，我想你可以用进出栈的方式进行判断，这比正则来的简单快捷。

Answer 2

维护一个计数器，如果是左括号加1，右括号减一，最后判断计数器是否等于0。

function match(str) {
    var n = 0;
    for (s of str) {
        if (s === '(') {
            n++;
        } 
        if (s === ')') {
            if (n === 0) {
                return false;
            }
            n--;
        }
    }
    return n === 0;
}

Answer 3

这种括号匹配必须要求正则支持嵌套或者递归阿之类的东西

我有个简单的想法，就是用正则把所有匹配的括号都替换掉。。。

下面是用perl6 实现的，如果看不懂理解一下想法就好了。。。

#!/usr/bin/env perl6
 
use v6;
 
my \stdin = $*IN;
 
my Int $count = +stdin.get();
 
for ^$count {
    my Str $str = stdin.get();
 
    while $str.chars > 0 {
        last unless $str ~~ s:g/[ \[ \] || \( \) ]+//; ## 去掉所有匹配的括号
    }
 
    say $str.chars ?? "No" !! "Yes"; ##如果 还存在不能去除的字符，说明匹配失败 。。
}

嵌套是这样子的。。

#!/usr/bin/env perl6

grammar Bracket { ## 语法类型  *匹配0或以上 +匹配1或以上
    rule TOP {
        <pair>* 
    }
    token pair { # 匹配 <bl><br> 或者 是 <bl><pair>+<br>
        <bl><br> |
        <bl><pair>+<br>
    }
    token bl {
        <[ \( \[ ]> # 匹配 '(' 或者  '['
    }
    token br {
        <[ \) \] ]> # 匹配 ')' 或者 ']'
    }
}

## 测试语句 匹配上就打印匹配得到的语法树 匹配不到就是Nil
say Bracket.parse("()");
say Bracket.parse('(()');
say Bracket.parse("(((((())))))");
say Bracket.parse("((()))((()))");

最后贴个图

再贴个我分享的代码：

• Link: http://www.oschina.net/code/snippet_2531803_52338

Answer 4

为什么我记得括号匹配是2型文法，正则表达式是3型文法，所以这个是不可能的呢……

乔姆斯基文法

Answer 5

str && str.replace(/\(\)/g, '') === '';

Answer 6

如果你用 .NET 平台，可以用平衡组来匹配这种嵌套的结构，某些支持任意层嵌套的正则引擎应该也可以，不过这种语法不一定是标准的正则语法。

Answer 7

1.先检测是不是左括号先出现
2.分别统计左右括号的个数，判断左右括号数目是否相等

以上方法有缺陷，下面使用逐级替换来实现

$str = "((()))";

while(strrpos($str, '()')){
    $str = str_replace($str, '()', '');
}

if(strlen($str) == 0){
   echo "match";
} else {
   echo "no match";
}

Answer 8

http://stackoverflow.com/a/524624/2586541

Answer 9

我认为这个问题的关键在于你必须遍历一遍这个字符串，在每次 ')' 出现时检查是否有空余的 '(' 与之对应。
那么我们可以在遍历的时候维护一个空余的左括号计数来解决这个问题。
一个c++的示例:

#include <cstdio>
#include <string>

bool isValid(const std::string& str) {
    if (str.empty())
        return false;

    int left = 0;

    for (auto itr = str.begin(); itr != str.end(); itr++) {
        if (*itr == '(') {
            left++;
        } else if(*itr == ')') {
            left--;
            if (left < 0) 
                return false;
        } else {
            return false;
        }
    }
    return (left == 0);
}

Answer 10

#!/usr/bin/env perl

my $levelN;
$levelN = qr/\(([^()] | (??{$levelN}))*\)/x;

my @list = (
    '()',
    ')(()))',
    '(((((((())))))))',
    '(())((()())())',
    '(()))()',
    '()()'
);
foreach my $text (@list) {
    if ($text =~ m/^($levelN)+$/x) {
        print "found matche: $text\n";
    }
}

perl的动态正则可以实现，javascript好像也支持动态正则，具体可以查一下

参见：<精通正则表达式:用动态正则表达式结构匹配嵌套结构 P328>