为了账号安全,请及时绑定邮箱和手机立即绑定

如何将a^nb^n与Java正则表达式匹配?

/ 猿问

如何将a^nb^n与Java正则表达式匹配?

慕工程0101907 2019-07-12 18:46:09

如何将a^nb^n与Java正则表达式匹配?

这是一系列教育准则文章的第二部分。它展示了如何使用查找头和嵌套引用来匹配非正则语言a。nbn..嵌套引用首先在以下内容中引入:这个正则表达式是如何找到三角数的?

一个典型的非-正规语言是:

L = { anbn: n > 0 }

这是所有非空字符串的语言,由若干个a之后是相同数量的b该语言中字符串的示例如下abaabbaaabbb.

此语言可以显示为非常规语言。泵引理..它实际上是一个原型上下文无关语言,它可以由上下文无关语法 S → aSb | ab.

尽管如此,现代regex实现清楚地认识到的不仅仅是普通语言。也就是说,从形式语言理论的定义来看,它们并不是“规则”的。PCRE和Perl支持递归regex,而.NET支持平衡组定义。更少的“花哨”特性,例如反向引用匹配,意味着正则表达式是不正常的。

但是这些“基本”功能到底有多强大呢?我们能认出L例如,使用Java regex?我们是否可以将查找器和嵌套引用组合在一起,并有一个可以与之协同工作的模式呢?String.matches来匹配字符串,如abaabbaaabbb等等?

参考文献

相关问题


查看完整描述

3 回答

?
MYYA


答案是,不用说,是!当然,您可以编写一个Java regex模式来匹配anbn..它使用一个积极的前瞻性断言,一个嵌套的引用用于“计数”。


这个答案将引导读者阅读,而不是立即给出答案。过程得到它。随着解的缓慢构造,给出了各种提示。在这方面,希望这个答案包含的不仅仅是另一个整洁的regex模式。希望读者还将学习如何“在regex中思考”,以及如何将各种结构和谐地组合在一起,以便在将来能够自己派生出更多的模式。


开发解决方案所用的语言将是PHP,因为它简洁。一旦最终确定了模式,最后的测试将在Java中完成。


步骤1:展望断言

让我们从一个简单的问题开始:我们想要匹配a+在字符串的开头,但前提是它紧跟在b+..我们可以用^到锚因为我们只想匹配a+没有b+,我们可以用前瞻断言(?=…).


下面是我们使用一个简单测试工具的模式:


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);

输出是(如ideone.com所见):


aaa 0

aaab 1 aaa

aaaxb 0

xaaab 0

b 0

abbb 1 a

这正是我们想要的输出:我们匹配a+,只有当它位于字符串的开头,并且它的后面紧跟着b+.


教课:您可以在“旁观者”中使用模式来进行断言。


步骤2:以向前看的方式捕获(和f r e-s p a c i n g模式)

现在让我们说,即使我们不想b+作为比赛的一部分,我们确实想俘获同样,由于我们预计有一个更复杂的模式,让我们使用x改性剂自由间距这样我们就可以让正则表达式更易读了。


在前面的PHP片段的基础上,我们现在有了以下模式:


$r2 = '/ ^ a+ (?= (b+) ) /x';

#             │   └──┘ │

#             │     1  │

#             └────────┘

#              lookahead


testAll($r2, $tests);

输出现在是(如ideone.com所见):


aaa 0

aaab 1 aaa|b

aaaxb 0

xaaab 0

b 0

abbb 1 a|bbb

请注意,例如。aaa|b是.的结果join-了解每一组被捕获的内容'|'..在这种情况下,组0(即模式匹配的内容)捕获。aaa,第一组被俘b.


教课:你可以在一个环顾四周的地方捕捉到。你可以使用自由间距来提高可读性.


步骤3:将前瞻性重构为“循环”

在我们引入我们的计数机制之前,我们需要对我们的模式做一次修改。当前,前瞻性不在+重复“循环”。到目前为止还好,因为我们只是想断言b+跟随我们a+但是我们真的最后要做的是为每个人断言a我们在“循环”中匹配,有一个对应的b一起去吧。


现在我们不要担心计数机制,只需按照以下步骤进行重构:


第一次重构a+到(?: a )+(请注意,(?:…)是一个非捕获组)

然后在这个非捕获组中移动前瞻。

请注意,我们现在必须“跳过”a*在我们“看到”之前b+,因此相应地修改模式。

因此,我们现在有以下几点:


$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';

#          │     │      └──┘ │ │

#          │     │        1  │ │

#          │     └───────────┘ │

#          │       lookahead   │

#          └───────────────────┘

#           non-capturing group

输出与以前相同(如ideone.com所见),所以在这方面没有任何变化。重要的是,现在我们的断言是每一次迭代.的.+“循环”对于我们当前的模式,这是不必要的,但接下来我们将使用自引用使第1组“计数”。


教课:您可以在非捕获组中捕获。环顾四周是可以重复的。


第四步:这是我们开始计数的步骤。

下面是我们要做的事情:我们将重写第一组,这样:


的第一次迭代结束时,+,当第一次a是匹配的,它应该捕获b

在第二次迭代结束时,当另一个a是匹配的,它应该捕获bb

在第三次迭代结束时,它应该捕获bbb

...

在n-第四次迭代,第一组应该捕获bn

如果没有足够的b要捕获到第1组,断言就会失败。

第一组,现在(b+),将不得不重写为(\1 b)..也就是说,我们试图“添加”一个b在上一次迭代中捕获了哪些组1。


这里有一个小问题,因为这个模式缺少了“基本案例”,即它可以在没有自引用的情况下进行匹配。因为组1启动“未初始化”,所以需要一个基本的大小写;它还没有捕获任何内容(甚至没有一个空字符串),所以自引用尝试总是失败的。


有很多种方法可以解决这个问题,但是现在让我们来做一个自引用匹配。任选,即.\1?..这可能是完美的,也可能不是完美的,但让我们看看它能起什么作用,如果有什么问题,当我们到达它的时候,我们会穿过那座桥。同时,我们还将在测试用例中添加更多的测试用例。


$tests = array(

  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'

);


$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';

#          │     │      └─────┘ | │

#          │     │         1    | │

#          │     └──────────────┘ │

#          │         lookahead    │

#          └──────────────────────┘

#             non-capturing group

输出现在是(如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....

哈哈!看来我们现在离解决方案很近了!我们设法让第一组使用自我引用“计数”!但是等等.。第二个和最后一个测试用例出了问题!没有足够的bS,不知怎么算错了!我们将在下一步研究为什么会发生这种情况。


教课:一种“初始化”自引用组的方法是使自引用匹配可选。


步骤4.5:了解出了什么问题

问题是,由于我们使自引用匹配可选,“计数器”可以“重置”回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这一次)。


教课*提防回溯。regex引擎将执行尽可能多的回溯,直到给定模式匹配为止。这可能会影响绩效(即灾难性回溯)和/或正确性。


第五步:自救!

现在,“修复”应该是显而易见的:将可选的重复与占有性量词也就是说,而不是简单地?,使用?+相反(请记住,量化为占有式的重复不会倒退,即使这种“合作”可能会导致与总体模式的匹配)。


在非常非正式的条件下,这就是?+, ?和??说:


?+

(可选)“它不必在那里,”

(占有欲)“但如果它在那里,你必须接受它,而不是放手!”

?

(可选)“它不必在那里,”

(贪婪)“但如果是的话,你现在可以接受,”

(回溯)“但你以后可能会被要求放手!”

??

(可选)“它不必在那里,”

(不情愿)“即使是这样,你也不必现在就接受它,”

(回溯)“但是你以后可能会被要求接受的!”

在我们的设计中,\1不会第一次出现,但它会总在那之后的任何时候,我们总想匹配一下。因此,\1?+就能实现我们想要的。


$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';

#          │     │      └──────┘ │ │

#          │     │          1    │ │

#          │     └───────────────┘ │

#          │         lookahead     │

#          └───────────────────────┘

#             non-capturing group

现在输出是:如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!!!

哇!问题解决了!我们现在正确地计数,就像我们想要的那样!


教课学习贪婪、不情愿和占有性重复之间的区别。可选的-占有可以是一个强大的组合。


第6步:最后修饰

所以我们现在得到的是一个匹配的模式a一而再、再而三地a是匹配的,有一个对应的b在第一组中捕获。+在不再存在时终止a,或者如果断言失败是因为没有对应的b为了a.


要完成这项工作,我们只需附加到我们的模式。\1 $..这现在是对第1组匹配的内容的反向引用,后面是行锚的末尾。锚确保没有额外的b在字符串中,换句话说,实际上我们有anbn.


下面是最后确定的模式,还有其他测试用例,包括一个长度为10,000个字符的测试用例:


$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,以及a5000b5000..它需要只能在ideone.com上运行0.06s.


步骤7:Java测试

因此,该模式在PHP中工作,但最终目标是编写一个在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);

}

该模式如预期的那样工作(如ideone.com所见).


现在我们得出结论.。

需要说的是a*在展望未来,确实是“主要的”+循环“,两者都允许回溯。读者被鼓励确认为什么这在正确性方面不是一个问题,为什么同时使这两个所有格都能起作用(尽管也许将强制性和非强制性的所有量词混合在同一个模式中可能会导致误解)。


还应该说,虽然它很整洁,但是有一个正则表达式可以匹配anbn这并不总是实践中的“最佳”解决方案。一个更好的解决方案就是简单的匹配^(a+)(b+)$,然后比较宿主编程语言中第1组和第2组捕获的字符串的长度。


在PHP中,它可能如下所示(如ideone.com所示):


function is_anbn($s) {

   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&

      (strlen($groups[1]) == strlen($groups[2]));

}

本文的目的是不要让读者相信regex几乎可以做任何事情;它显然做不到,即使是它能做的事情,如果它带来了一个更简单的解决方案,至少应该考虑部分委托给宿主语言。


如上面所提到的,这篇文章必须加上标签。[regex]对于堆栈溢出来说,它可能不仅仅是这样。当然,学习断言、嵌套引用、拥有量词等是有价值的,但更重要的一课也许是一个人可以尝试解决问题的创造性过程、当你受到各种约束时所需要的决心和辛勤工作,以及构建工作解决方案的各个部分的系统组合,等等。


奖励材料!PCRE递归模式!

由于我们确实提到了PHP,需要指出的是,PCRE支持递归模式和子程序。因此,以下模式适用于preg_match (如ideone.com所见):


$rRecursive = '/ ^ (a (?1)? b) $ /x';

目前,Java的regex不支持递归模式。


更多的奖励材料!匹配anbncn !!

所以我们已经看到了如何匹配anbn这是不定期的,但仍然是无上下文的,但我们也能匹配吗?anbncn,哪一个甚至不是没有上下文的?


答案当然是,是!鼓励读者自己解决这一问题,但解决方案如下(与在ideone.com上用Java实现).


查看完整回答
反对 回复 2019-07-12
?
HUH函数

鉴于没有提到支持递归模式的PCRE,我只想指出描述所涉语言的最简单和最有效的PCRE示例:

/^(a(?1)?b)$/


查看完整回答
反对 回复 2019-07-12
?
慕慕0277861

正如问题中所提到的-在.NET平衡组中,类型的模式anbncndn…Zn可以很容易地匹配

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))$

例如:http://www.ideone.com/usuOE


编辑:

对于具有递归模式的广义语言也有一个PCRE模式,但是需要一个前瞻性。我不认为这是上述的直接翻译。

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)$

例如:http://www.ideone.com/9gUwF


查看完整回答
反对 回复 2019-07-12

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信