regex - 基于二进制字符串中 1 和 0 的差异匹配的正则表达式

Question

所以，到了期末考试的时间，我在一次旧考试中遇到了这个问题：

给出一个表示diff(x)where 的正则表达式：

- diff(x) is the number of 1's in x minus the number of 0's in x
- 1 <= diff(x) <= 3

例如

 diff(10110100111) = 7-4 = 3
 diff(11100011) = 5-3 = 2
 diff(10011) = 3-2 = 1

Answer 1

应该不可能根据需要构建正则表达式。如果是，您将有一个有限状态自动机，必须实现一个无界计数器，以便区分输入0^n1^n111和0^n1^n1111. 显然这是无法实现的，至少在理论上是这样（但是，如果任何前缀 of 中 1 和 0 的数量之差x受常数限制，则可以实现）。

这在实践中可能无关紧要，因为几乎每个常见的正则表达式引擎都比正则表达式识别器更强大，但它可能与考试题的上下文相关。

Answer 2

不确定您要处理的正则表达式引擎，您需要一个具有递归支持的引擎，例如 .NET（平衡组）或 PCRE（递归）。以下是有效的并且适用于 .NET：

^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))