所以,到了期末考试的时间,我在一次旧考试中遇到了这个问题:
给出一个表示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
所以,到了期末考试的时间,我在一次旧考试中遇到了这个问题:
给出一个表示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
应该不可能根据需要构建正则表达式。如果是,您将有一个有限状态自动机,必须实现一个无界计数器,以便区分输入0^n1^n111
和0^n1^n1111
. 显然这是无法实现的,至少在理论上是这样(但是,如果任何前缀 of 中 1 和 0 的数量之差x
受常数限制,则可以实现)。
这在实践中可能无关紧要,因为几乎每个常见的正则表达式引擎都比正则表达式识别器更强大,但它可能与考试题的上下文相关。
不确定您要处理的正则表达式引擎,您需要一个具有递归支持的引擎,例如 .NET(平衡组)或 PCRE(递归)。以下是有效的并且适用于 .NET:
^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))