具有偶数个0或奇数个1的二进制数字的最短正则表达式

Question

写一个表达式，其中包含偶数个0或奇数个1

我得到的是:

1*(01*01*)* + 0*10*(10*10*)*

第一部分表示0的数量为偶数，第二部分表示1的数量为奇数。

然而，据说有一种简化的解决方案，但我没有看到。 有什么提示吗？

- user3085290

---

作业啊？哈哈笑！ - jondinham

我在regexpal.com上尝试了这个正则表达式，似乎可以工作：^(1(11)*|(00)+)$ - bdean20

我刚刚从头开始写了一个正则表达式，得到了与你的正则表达式完全相同长度（95% 相似）的结果。我故意未先阅读你的表达式，因此怀疑可能已经没有更短的表达式了。 - OGHaza

请检查我的更新答案。0*1(0|10*1)*是奇数个1的部分的更短正则表达式。 - Julián Urbano

@user3085290，您是想要“偶数个0和奇数个1”还是“偶数个0或奇数个1”？ - The Guy with The Hat

Answer 1

奇数位为：0*1(0|10*1)*

偶数位的0取决于：

1. 空字符串是正确的：(1|01*0)*
2. 没有0也是偶数个0：(1|01*0)+
3. 必须至少有两个0：1*(01*01*)+（与原帖相同）

旧答案：在情况1和2下是正确的

(1*(01*0)*)+ | 0*1(0*(10*1)*)*

---

感谢 @OGHaza 提供的有用评论。

- Julián Urbano

---

具有奇数个1且未匹配的字符串示例。 - OGHaza

看起来它与空字符串不匹配（零个“0”仍然是偶数）。不过很容易解决：将任何一个或两个“+”更改为“*”。 - DPenner1

@DPenner 是的，我有意让它强制非空。 - Julián Urbano

你从 OP 的正则表达式中删掉了 4 个字符，我认为你已经做到了极致；）+1 - OGHaza

@GrijeshChauhan，这些至少会强制出现一个0（在括号内）。再次强调，第二部分和第三部分是多余的，对吧？（让我们删除旧评论，以免变得太长） - Julián Urbano

Answer 2

利用一个事实，即偶数长度的字符串始终符合您的约束条件：

^(([01]{2})*|1*(01*01*)*)$

- Ruud Helderman

---

这个使用了和我的正则表达式一样多的符号，但我认为这个关于偶数长度字符串的非常好的捕获值得这个赏金。请注意，此正则表达式需要 no 0s-is-even-0s 情况。 - Julián Urbano

如果将1*(01*01*)*替换为(1|01*0)*（就像@JuliánUrbano的解决方案中那样），会更简短一些。但是没错，非常聪明，+1！ - Volatility

更重要的是……最短的执行时间！ - gillyspy

Answer 3

“最短”是什么意思？如果你寻求最短的评估时间（即最快），那么请确保不使用捕获组。

这里有一个 JavaScript 的示例

^(?:1*(?:01*0)*)+|0*1(?:0*(?:10*1)*)*$

这段话的翻译是：“这个表达式比使用捕获组的表达式快20％，但会给你相同的答案。”

^(1*(01*0)*)+|0*1(0*(10*1)*)*$

- gillyspy

---

我的意思是最短的符号。毕竟，非捕获组只是依赖于语言的语法糖。 - Julián Urbano

是的，我认为我们知道你想要什么了@JuliánUrbano。所以我的问题是给楼主的。你不是楼主吧？但对于你，Julian...我很好奇在哪些实际场景下，你（特指你而非一般的“你”）会更喜欢表达最短的长度而不是最短的评估时间？ - gillyspy

赏金只是为了好玩，看看是否有更短的东西。 - Julián Urbano

你的评论在我保存问题之前就已经发出来了，所以为了澄清一下：这样做没有实际目的，只是为了好玩吗？另外，我们能否确认您和原帖作者使用“更短”这个词的含义是相同的？还有，到底是谁在给我点踩呢？是否有什么地方我的回答/评论与我们提供的信息不相关？ - gillyspy

Answer 4

我找到的最简单的解决方案是：

1+0(0+1)((1+0)(1+0))*

- Mehran

Answer 5

用最少的符号

1*(01*01*)*

- Moses Kirathe

Answer 6

这个表达式怎么样：

(1(11)*+(00)*)

- khalid J-A