"()" => returns true
")(()))" => returns false
"(" => returns false
"(())((()())())" => returns true
形如这种,我可以做到匹配2,3层的没问题,但是层数多了就不知道该怎么办了
PHPz2017-04-11 12:59:31
如果你要通过正则表达式来完成这个匹配比较困难。但是如果你纯粹时想看看括号是不是左右成对匹配,我想你可以用进出栈的方式进行判断,这比正则来的简单快捷。
PHPz2017-04-11 12:59:31
维护一个计数器,如果是左括号加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;
}
巴扎黑2017-04-11 12:59:31
这种括号匹配必须要求正则支持嵌套或者递归阿之类的东西
我有个简单的想法,就是用正则把所有匹配的括号都替换掉。。。
下面是用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
PHP中文网2017-04-11 12:59:31
1.先检测是不是左括号先出现
2.分别统计左右括号的个数,判断左右括号数目是否相等
以上方法有缺陷,下面使用逐级替换来实现
$str = "((()))";
while(strrpos($str, '()')){
$str = str_replace($str, '()', '');
}
if(strlen($str) == 0){
echo "match";
} else {
echo "no match";
}
怪我咯2017-04-11 12:59:31
我认为这个问题的关键在于你必须遍历一遍这个字符串,在每次 ')' 出现时检查是否有空余的 '(' 与之对应。
那么我们可以在遍历的时候维护一个空余的左括号计数来解决这个问题。
一个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);
}
阿神2017-04-11 12:59:31
#!/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>