基于二进制字符串中0中1的差异进行匹配的正则表达式
基于二进制字符串中0中1的差异进行匹配的正则表达式
提问于 2011-12-13 07:00:02
所以，现在是期末考试的时候了，我在一次考试中遇到了这个问题：
给出一个表示diff(x)的正则表达式，其中：
- 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回答 2
Stack Overflow用户
回答已采纳
发布于 2012-01-24 22:09:00
应该不可能构建所需的正则表达式。如果是，那么您将拥有一个有限状态自动机，它必须实现一个无界计数器，以便区分输入、0^n1^n111和0^n1^n1111。显然，这是不可能实现的，至少在理论上是不可能实现的(但是，如果x的任何前缀中1和0的数量之差由一个常量限定，则可以实现)。
这在实践中可能无关紧要，因为实际上每个常见的正则表达式引擎都比正则表达式识别器更强大，但它可能与考试问题的上下文相关。
Stack Overflow用户
发布于 2011-12-13 08:13:18
不确定您正在处理的正则表达式引擎，您需要一个具有一些递归支持的引擎，例如.NET (平衡组)或PCRE (递归)。以下内容在.NET中有效且有效：
^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8482168
复制相关文章
相似问题
腾讯云开发者
