二进制数的最短正则表达式，偶数为0或奇数为1

Question

写一个包含偶数个0或奇数个1的表达式

我把它归结为：

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

其中第一部分表示偶数0，第二部分表示奇数1

但是，应该有一个我没有看到的简化解决方案。有小费吗？

Answer 1

奇数1s部分：0*1(0|10*1)*

Even-0s部分取决于：

1. 空字符串是正确的：(1|01*0)*
2. No-0s是偶数0：(1|01*0)+
3. 必须至少有两个0：1*(01*01*)+（如在OP中）

旧答案：在案例1和案例2下更正

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

---

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

Answer 2

利用偶数长度字符串始终满足您的约束这一事实：

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

Answer 3

定义“最短”。如果您正在寻找最短的评估时间（即最快），请确保您不使用捕获组。

here's an example in javascript

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

显示比使用捕获组的表达式快20％但会给出相同的答案

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

Answer 4

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

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

Answer 5

用最少的符号，

1*(01*01*)*