答案是,不用说,
对!
一
n
b
n
. 它对断言使用正向前瞻,对“计数”使用嵌套引用。
这个答案不是立即给出模式,而是引导读者通过
过程
推导它的方法。随着解的慢慢构造,给出了各种提示。在这方面,希望这个答案不仅仅包含另一个整洁的正则表达式模式。希望读者也能学会如何“在regex中思考”,以及如何将各种构造和谐地组合在一起,以便将来能够自己派生出更多的模式。
开发解决方案所使用的语言将是PHP,因为它的简洁性。模式完成后的最终测试将在Java中完成。
a+
在字符串的开头,但前提是后面紧跟着
b+
^
到
anchor
a+
没有
b类+
,我们可以使用
lookahead
(?=â¦)
.
下面是一个简单的测试工具:
function testAll($r, $tests) {
foreach ($tests as $test) {
$isMatch = preg_match($r, $test, $groups);
$groupsJoined = join('|', $groups);
print("$test $isMatch $groupsJoined\n");
}
}
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
$r1 = '/^a+(?=b+)/';
# ââââââ
# lookahead
testAll($r1, $tests);
输出为(
as seen on ideone.com
):
aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a
这正是我们想要的输出:我们匹配
,仅当它位于字符串的开头,并且仅当它后面紧跟着
b类+
.
教训
:您可以使用lookarounds中的模式来进行断言。
尽管我们不想
b类+
capture
把它放进第一组。另外,由于我们预期会有一个更复杂的模式,让我们使用
x
的修饰符
free-spacing
所以我们可以让正则表达式更具可读性。
在前面的PHP代码段的基础上,我们现在有以下模式:
$r2 = '/ ^ a+ (?= (b+) ) /x';
# â ââââ â
# â 1 â
# ââââââââââ
# lookahead
testAll($r2, $tests);
现在输出为(
as seen on ideone.com
aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb
注意,例如。
aaa|b
是由于
join
-每一组用什么捕捉
'|'
aaa
b
.
教训
:您可以在环视仪内捕获。可以使用自由间距来增强可读性。
第3步:将前瞻重构为“循环”
在引入计数机制之前,我们需要对模式做一个修改。目前,展望是在
+
重复“循环”。到目前为止这还不错,因为我们只是想断言
b类+
跟随我们的
a+
但是我们
真正地
a
我们在“循环”中匹配,有一个对应的
b
与之配套。
-
第一次重构
到
(?: a )+
(?:â¦)
是非捕获组)
-
-
请注意,我们现在必须“跳过”
a*
在我们“看到”之前
,因此相应地修改模式
$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
# â â ââââ â â
# â â 1 â â
# â âââââââââââââ â
# â lookahead â
# âââââââââââââââââââââ
# non-capturing group
输出和以前一样(
as seen on ideone.com
),所以这方面没有变化。重要的是,现在我们在
每次迭代
的
+
“循环”。在我们当前的模式下,这是没有必要的,但是接下来我们将使用自引用为我们“计算”第1组。
教训
第四步:这是我们开始计数的步骤
-
在第一次迭代的末尾
,当第一个
一
是匹配的,它应该捕获
b
-
在第二次迭代结束时
是匹配的,它应该捕获
bb
-
bbb
-
...
-
n
-在第次迭代中,第1组应该捕获
n
-
b
要捕获到组1中,断言就失败了
第一组,现在是
(b+)
(\1 b)
b
到上一次迭代中捕获的组1。
有很多方法可以解决这个问题,但现在让我们只做自我参照匹配
optional
\1?
. 这也许能很好地工作,也许不能很好地工作,但让我们看看它能做些什么,如果有任何问题,那么当我们到达它的时候,我们将穿过那座桥。另外,我们将在测试过程中添加更多的测试用例。
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
# â â âââââââ | â
# â â 1 | â
# â ââââââââââââââââ â
# â lookahead â
# ââââââââââââââââââââââââ
# non-capturing group
现在输出为(
as seen on ideone.com
):
aaa 0
aaab 1 aaa|b # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b # yes!
aabb 1 aa|bb # YES!!
aaabbbbb 1 aaa|bbb # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....
哈哈!看来我们真的很接近解决方案了!我们设法让第一组“计数”使用自我参考!但是等等。。。第二个和最后一个测试用例有问题!!还不够
b
教训
:一种“初始化”自引用组的方法是使自引用匹配可选。
第四步:了解出了什么问题
问题是,由于我们将自引用匹配设置为可选,所以当没有足够的匹配时,“counter”可以“重置”回0
b
让我们仔细检查在我们的模式的每一次迭代中发生了什么
aaaaabbb
作为输入。
a a a a a b b b
â
# Initial state: Group 1 is "uninitialized".
_
a a a a a b b b
â
# 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
# so it matched and captured just b
___
a a a a a b b b
â
# 2nd iteration: Group 1 matched \1b and captured bb
_____
a a a a a b b b
â
# 3rd iteration: Group 1 matched \1b and captured bbb
_
a a a a a b b b
â
# 4th iteration: Group 1 could still match \1, but not \1b,
# (!!!) so it matched and captured just b
___
a a a a a b b b
â
# 5th iteration: Group 1 matched \1b and captured bb
#
# No more a, + "loop" terminates
哈哈!在第四次迭代中,我们仍然可以匹配
\1
\1b
! 因为我们允许自引用匹配是可选的
\1?
,引擎回溯并选择“不感谢”选项,这样我们就可以匹配并捕获
b
但是请注意,除了在第一次迭代中,您始终可以只匹配自引用
\1
bbb公司
bbb公司
,但可能有,也可能没有
bbbb
教训
catastrophic backtracking
)和/或正确性。
“修复”现在应该是显而易见的:将可选的重复与
possessive
?
,使用
?+
相反(请记住,被量化为所有格的重复不会回溯,即使这种“合作”可能导致整体模式的匹配)。
?+
,
和
??
说:
?+
??
在我们的设置中,
不会第一次出现,但会的
在那之后的任何时间,我们
总是
\1?+
会完成我们想要的。
$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
# â â ââââââââ â â
# â â 1 â â
# â âââââââââââââââââ â
# â lookahead â
# âââââââââââââââââââââââââ
# non-capturing group
现在输出是(
as seen on ideone.com
):
aaa 0
aaab 1 a|b # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb # Hurrahh!!!
教训
:了解贪婪、不情愿和占有式重复之间的区别。可选所有格可以是一个强大的组合。
第六步:收尾
所以我们现在有一个匹配的模式
一
重复,每一次
一
这是匹配的,有一个对应的
b
+
当没有更多时终止
一
,或者由于没有相应的
一
.
\1 $
. 现在,这是对第1组匹配内容的反向引用,后面是行结束锚定。锚确保没有任何额外的
b
在字符串中;换句话说,事实上我们
b
.
以下是最终确定的模式,以及其他测试用例,包括一个10000个字符长的测试用例:
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
'', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
str_repeat('a', 5000).str_repeat('b', 5000)
);
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
# â â ââââââââ â â
# â â 1 â â
# â âââââââââââââââââ â
# â lookahead â
# âââââââââââââââââââââââââ
# non-capturing group
它找到4个匹配项:
ab
aabb
,
aaabbb
一
5000
. 它需要
only 0.06s to run on ideone.com
第7步:Java测试
public static void main(String[] args) {
String aNbN = "(?x) (?: a (?= a* (\\1?+ b)) )+ \\1";
String[] tests = {
"", // false
"ab", // true
"abb", // false
"aab", // false
"aabb", // true
"abab", // false
"abc", // false
repeat('a', 5000) + repeat('b', 4999), // false
repeat('a', 5000) + repeat('b', 5000), // true
repeat('a', 5000) + repeat('b', 5001), // false
};
for (String test : tests) {
System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN));
}
}
static String repeat(char ch, int n) {
return new String(new char[n]).replace('\0', ch);
}
模式按预期工作(
as seen on ideone.com
现在我们得出结论。。。
需要说明的是
a*
展望未来,实际上是
+
还应该说,虽然它很整洁,但是有一个正则表达式模式可以匹配
一
b
n
在实践中,这并不总是“最佳”解决方案。更好的解决方案是简单地匹配
^(a+)(b+)$
在PHP中,它可能是这样的(
as seen in ideone.com
function is_anbn($s) {
return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
(strlen($groups[1]) == strlen($groups[2]));
}
本文的目的是
为了让读者相信regex几乎可以做任何事情;它显然做不到,甚至对于它可以做的事情,如果能够得到一个更简单的解决方案,至少应该考虑对宿主语言的部分委托。
[regex]
对于stackoverflow来说,可能不止这些。当然,学习断言、嵌套引用、所有格量词等是有价值的,但这里更大的教训也许是一个人可以尝试解决问题的创造性过程,当你受到各种约束时,往往需要的决心和努力,以及来自不同部分的系统组合制定有效的解决方案等。
奖励材料!PCRE递归模式!
既然我们提出了PHP,就需要说PCRE支持递归模式和子例程。因此,以下模式适用于
preg_match
(
as seen on ideone.com
):
$rRecursive = '/ ^ (a (?1)? b) $ /x';
目前Java的regex不支持递归模式。
更多的奖励材料!匹配
一
n
b
n
c
!!
一
n
b
n
这是不规则的,但仍然是上下文无关的,但我们也可以匹配吗
一
b
n
c
n
,这甚至不是上下文无关的?
答案当然是,
对!
我们鼓励读者自己尝试解决这个问题,但下面提供了解决方案(附带
implementation in Java on ideone.com
^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $
