如何确定一个数是否是正则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是很简单的。
- 为了testing
n
素数,首先生成一个长度为n
的String
(用相同的char
填充) - 正则expression式将一个长度为
\1
的String
(如k
)捕获到\1
,并尝试将\1+
与String
的其余部分匹配- 如果匹配,那么
n
是k
的正确倍数,因此n
不是素数。 - 如果没有匹配,那么就不存在将
n
分开的k
,因此n
是素数
- 如果匹配,那么
如何
.?|(..+?)\1+
匹配素数?
其实它不是! 它匹配长度不是素数的String
!
-
.?
:交替的第一部分匹配长度为0
或1
String
(NOT按定义) -
(..+?)\1+
:交替的第二部分,上面解释的正则expression式的变体匹配长度为n
的String
,该长度是长度为k >= 2
的String
的“倍数”(即,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+");
同样,给定一个长度为n
的String
,填充相同的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,…)。 非素数将匹配这个。 如果不匹配,那就是素数。
这里解释。