phpstudy集成环境

 首页 > 请问正则如何匹配多层成对的括号？

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

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

形如这种，我可以做到匹配2,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("((()))((()))");

最后贴个图

再贴个我分享的代码：

我认为这个问题的关键在于你必须遍历一遍这个字符串，在每次 ')' 出现时检查是否有空余的 '(' 与之对应。
那么我们可以在遍历的时候维护一个空余的左括号计数来解决这个问题。
一个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);
}

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

#!/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>

尝试用Java写了下，自己都不满意。

public class Parentheses {

    public static void main(String[] args) {
        Parentheses p = new Parentheses();
        String str1 = "()"; // => returns true
        String str2 = ")(()))"; // => returns false
        String str3 = "("; // => returns false
        String str4 = "(())((()())())"; // => returns true
        System.out.println(p.test(str1));
        System.out.println(p.test(str2));
        System.out.println(p.test(str3));
        System.out.println(p.test(str4));
    }
    public boolean test(String str) {
        Stack<String> stack = new Stack<String>();
        boolean pauseAtMiddle = false;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if(')' == ch) {
                if (stack.isEmpty()) {
                    pauseAtMiddle = true;
                    break;
                }
                stack.pop();
            } else if ('(' == ch) {
                stack.push(String.valueOf(ch));
            } else {
                System.out.println("not equal");
                continue;
            }
        }
        if(pauseAtMiddle || !stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

不能。

因为多层嵌套的括号是上下文无关文法，正则表达式只能匹配正则语言。

这个恰好不属于正则语言，可以证明。

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

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

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

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

if(strlen($str) == 0){
   echo "match";
} else {
   echo "no match";
}
str && str.replace(/\(\)/g, '') === '';

这个，正则太麻烦，循环替换 '()' 不就好了？

function checkKuohao(str){
    return str.indexOf('()') > -1 
        ? checkKuohao( str.replace('()', '') )
        : str === '';
}

如果括号中间可能有其他字符串的，可以修改一下上面的 replace 第一个参数，匹配一个括号就方便了嘛。

正则是会一点，但是看这个估计很难实现吧，实际上解决问题就可以了，不一定要用正则的，下面这种方法肯定可以，希望楼主采纳。
思路：用0+0的方式填充括号里面的内容，最后用eval执行，如果执行成功则左右括号是一对一，否则失败。

        var abc = "(())((()())())";
        var a = abc.replace(/\)/g,"+)").replace(/\)\(/g,")+(").replace(/\(\+/g,"(0+").replace(/\+\)/g,"+0)");
        var flag;
        try{
            var b = eval(a);
            flag = true;
        }catch (e){
            flag = false;
        }
        console.log(flag);

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

乔姆斯基文法

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

维护一个计数器，如果是左括号加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;
}

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

单纯的正则匹配实现不了, 但在JS里通过正则计算出 左/右括号 出现的次数, 就可以判断出括号的出现是否成对出现.

附代码:

var a = [
    "()",
    ")(()))",
    "(",
    "(())((()())())",
    "(()))("//增加 左/右括号 个数相同, 但出现的位置不匹配的测试用例
];


function ck(v){
    var c =  0;

    try{
        v.replace(/[()]/g, function(a){
            c += a === '(' ? 1 : -1;//当出现 左括号时 +1, 当出现右括号时 -1

            if(c < 0){//当出现右括号的个数超过左括号的个数时, 抛出异常, 不再继续下去
                throw 'no match';
            }
        });
    }catch(e){}

    return c === 0;//只有 左/右括号 成对 出现时, c的值对为0, 所以以此为检测条件
}


for(var i=0, j=a.length; i<j; i++){
    console.log(a[i], ck(a[i]));
}

运行结果:

【热门文章】
【热门文章】