3

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

给出一个表示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
4

2 回答 2

2

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

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

于 2012-01-24T14:09:00.267 回答
1

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

^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))
于 2011-12-13T00:13:17.887 回答