如何确定一个数是否是正则expression式的一个主要元素?

我在RosettaCode上find了以下Java代码示例:

public static boolean prime(int n) { return !new String(new char[n]).matches(".?|(..+?)\\1+"); } 
  • 我不特别了解Java,但了解这个片段的所有方面,除了正则expression式本身
  • 当你在内置的PHP函数中find正则expression式时,我有基本的高级正则expression式知识

如何.?|(..+?)\\1+匹配素数?

你说你理解这个部分,但只是强调,生成的string的长度等于提供的数量。 所以当且仅当n == 3 ,string有三个字符。

 .? 

正则expression式的第一部分是“任何字符,零次或一次”。 所以基本上,是否有零个或一个字符 – 或者,根据我上面提到的, n == 0 || n == 1 n == 0 || n == 1 。 如果我们有匹配,那么返回否定的那个。 这对应于零和一不是素数的事实。

 (..+?)\\1+ 

正则expression式的第二部分有点棘手,依赖于群组和反向引用。 一个组是括号内的任何内容,然后将被正则expression式引擎捕获并存储以供以后使用。 反向引用是稍后在相同的正则expression式中使用的匹配组。

该组捕获1个字符,然后捕获1个或更多的任何字符。 (+字符是指一个或多个字符,而不是前面的字符或组,所以这不是“两个或四个或六个字符”,而是“两个或三个”。+ +是+,但它会尽量匹配尽可能less的字符,如果可能,+通常会尝试吞噬整个string,这在这种情况下是不好的,因为它阻止了反向引用部分的工作。

下一部分是反向引用:同一组字符(两个或更多),再次出现。 所述反向引用出现一次或多次。

所以。 捕获的组对应于捕获的自然数字(从2开始)。 所述组然后出现一些自然次数(也从2起)。 如果有一个匹配,这意味着有可能find两个大于或等于2的数字匹配n长度string的乘积…意味着你有一个复合n。 所以再次回到成功匹配的否定:n不是素数。

如果不能find匹配,那么你不能拿出你的两个自然数大于或等于2的乘积,而且你有一个不匹配和一个素数,所以再次返回否定的比赛结果。

你现在看到了吗? 这是令人难以置信的棘手的问题(而且计算起来也很昂贵!),但是一旦你得到它,它也同样简单。 🙂

我可以详细说明是否还有其他问题,比如说正则expression式parsing是如何工作的。 但是我现在试图保持这个答案简单(或者尽可能简单)。

我将解释素数testing之外的正则expression式部分:下面的正则expression式,给定一个由重复String t组成的String t ,findt

  System.out.println( "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1") ); // prints "Mamamia" 

它的工作方式是正则expression式将(.*)捕获到\1 ,然后看看它是否有\1+ 。 使用^$确保匹配必须是整个string。

所以,在某种程度上,我们得到了String s ,它是String t一个“倍数”,正则expression式会find这样的t (尽可能最长,因为\1是贪婪的)。

一旦你明白为什么这个正则expression式起作用,那么(现在忽略OP的正则expression式中的第一个替代)解释了它如何用于素性testing是很简单的。

  • 为了testingn素数,首先生成一个长度为nString (用相同的char填充)
  • 正则expression式将一个长度为\1String (如k )捕获到\1 ,并尝试将\1+String的其余部分匹配
    • 如果匹配,那么nk的正确倍数,因此n不是素数。
    • 如果没有匹配,那么就不存在将n分开的k ,因此n是素数

如何.?|(..+?)\1+匹配素数?

其实它不是! 它匹配长度不是素数的String

  • .? :交替的第一部分匹配长度为01 String (NOT按定义)
  • (..+?)\1+ :交替的第二部分,上面解释的正则expression式的变体匹配长度为nString ,该长度是长度为k >= 2String的“倍数”(即, n是复合,不是素数)。
    • 请注意,勉强修饰符? 实际上并不需要正确性,但是可以通过首先尝试较小的k加快处理速度

注意! return语句中的boolean互补运算符:它否定matches 。 这是正则expression式匹配时, n是素数! 这是一个双重否定的逻辑,所以难怪这是一种混乱!


简单化

这是一个简单的代码重写,使其更具可读性:

 public static boolean isPrime(int n) { String lengthN = new String(new char[n]); boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+"); return !isNotPrimeN; } 

上面基本上和原始的Java代码一样,但是分解成多个语句,赋值给局部variables,使逻辑更容易理解。

我们还可以使用有限重复来简化正则expression式,如下所示:

 boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+"); 

同样,给定一个长度为nString ,填充相同的char

  • .{0,1}检查是否n = 0,1 ,不是素数
  • (.{2,})\1+检查n是否是k >= 2的合适倍数,不是素数

除了勉强的修饰词?\1 (为了清楚起见省略),上面的正则expression式与原来的相同。


更有趣的正则expression式

以下正则expression式使用类似的技术; 它应该是教育性的:

 System.out.println( "OhMyGod=MyMyMyOhGodOhGodOhGod" .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!") ); // prints "Oh! My! God!" 

也可以看看

  • 正则expression式:谁是贪婪的

很好的正则expression式技巧(虽然非常低效)… 🙂

正则expression式定义非素数如下:

当且仅当N <= 1或N可被K> 1整除时,N不是素数。

它不是将N的简单数字表示传递给正则expression式引擎,而是将其input一个由重复字符组成的长度为 N的序列。 分解的第一部分检查N = 0或N = 1,第二部分使用反向引用查找除数K> 1。 它强制正则expression式引擎find一些非空的子序列,可以重复至less两次,以形成序列。 如果存在这样的子序列,则意味着其长度除以N,因此N不是素数。

 /^1?$|^(11+?)\1+$/ 

应用于转换后的数字为1(1 = 1,2 = 11,3 = 111,…)。 非素数将匹配这个。 如果不匹配,那就是素数。

这里解释。