我正在尝试创建一个正则表达式来确定字符串（任何长度）是否与正则表达式模式匹配，使得字符串中 0 的数量是偶数，而字符串中 1 的数量是偶数。谁能帮我确定一个正则表达式语句，我可以尝试用它来检查这个模式的字符串吗？
问问题
10727 次
8 回答
8
所以完全重新制定了我的答案以反映所有的变化：
此正则表达式将匹配所有只有零和一且数量相等的字符串
^(?=1*(?:01*01*)*$)(?=0*(?:10*10*)*$).*$
我在这里使用积极的前瞻性断言。前瞻断言的最大优点是，它检查完整的字符串，但不匹配它，所以两个前瞻都从一开始就检查字符串，但是对于不同的断言。
(?=1*(?:01*01*)*$)确实检查等量的 0（包括 0）(?=0*(?:10*10*)*$)确实检查等量的 1（包括 0）.*然后确实匹配字符串
这些前瞻检查：
(?=
1* # match 0 or more 1
(?: # open a non capturing group
0 # match one 0
1* # match 0 or more 1
0 # match one 0
1* # match 0 or more 1
)
* # repeat this pattern at least once
$ # till the end of the string
)
于 2012-04-18T07:39:51.703 回答
5
所以，我想出了一个解决问题的办法：
(11+00+(10+01)(11+00)\*(10+01))\*
于 2012-04-26T17:26:53.980 回答
4
对于偶数组 0，您可以使用以下正则表达式来确保 0 的数量是偶数。
^(1*01*01*)*$
但是，我认为问题是既有偶数个 0，也有偶数个 1。由于可以为该问题构造一个非确定性有限自动机 (NFA)，因此解决方案是正则的，并且可以使用正则表达式表示。NFA 通过下面的机器表示，S1 是启动/退出状态。
S1 ---1----->S2
|^ <--1----- |^
|| ||
00 00
|| ||
v| v|
S3----1----->S4
<---1------
从那里开始，有一种方法可以将 NFA 转换为正则表达式，但距离我的计算课程已经有一段时间了。下面有一些注释似乎有助于解释将 NFA 转换为正则表达式所需的步骤。
http://www.cs.uiuc.edu/class/sp09/cs373/lectures/lect_08.pdf
于 2012-04-18T07:40:39.333 回答
1
重新更新
试试这个： [查看这个演示：http ://regexr.com?30m7c ]
^(00|11|0011|0110|1100|1001)+$
暗示 ：
偶数可以被 2 整除，因此 - 在二进制中 - 它们总是以零结尾 ( 0)
于 2012-04-18T07:18:20.633 回答
1
不是正则表达式（这很可能是不可能的，虽然我无法证明：通过泵引理的矛盾证明失败），但“正确”的解决方案是一起避免复杂和低效的正则表达式并使用一些东西像（在 Python 中）：
def even01(string):
return string.count("1") % 2 == 0 and string.count("0") % 2 == 0
或者如果字符串必须只包含1s 和0s：
import re
def even01(string):
return not re.search("[^01]",string) and \
string.count("1") % 2 == 0 and string.count("0") % 2 == 0
于 2012-04-18T07:56:26.817 回答
1
^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$
如果我没有忽略任何事情，这将匹配任何位字符串，其中 0 的数量为偶数且 1 的数量为偶数，仅使用基本的正则表达式运算符 ( *, ^, $)。如果像这样写的话，看它是如何工作的会稍微容易一些：
^(0((1(00)*1)*0
|1(11|00)*01)
|1((0(11)*0)*1
|0(11|00)*10))*$
下面的测试代码应该说明正确性——我们将模式匹配的结果与一个函数进行比较，该函数告诉我们一个字符串是否有偶数个 0 和 1。测试所有长度为 16 的位串。
import re
balanced = lambda s: s.count('0') % 2 == 0 and s.count('1') % 2 == 0
pat = re.compile('^(0((1(00)*1)*0|1(11|00)*01)|1((0(11)*0)*1|0(11|00)*10))*$')
size = 16
num = 2**size
for i in xrange(num):
binstr = bin(i)[2:].zfill(size)
b, m = balanced(binstr), bool(pat.match(binstr))
if b != m:
print "balanced('%s') = %d, pat.match('%s') = %d" % (binstr, b, binstr, m)
break
elif i != 0 and i % (num / 10) == 0:
# Python 2's `/` operator performs integer division
print "%d percent done..." % (100 * i / num + 1)
于 2014-05-09T18:47:19.550 回答
0
如果你试图在同一个句子中解决（以 ^ 开头，以 $ 结尾），你就陷入了大麻烦。:-)
您可以确保您有偶数个 0（使用^(1*01*01*)*$，如@david-z 所述）或者您可以确保您有偶数个 1：
^(1*01*01*)*$|^(0*10*10*)*$
它也适用于长度较小的字符串，例如“00”或“101”，都是有效的字符串。
于 2013-08-31T23:01:19.233 回答
0
我在业余时间也一直在研究前瞻和回顾，使用前瞻可以解决问题，同时考虑单个 1 和/或单个 0。所以，表达式也应该适用于 11,1111,111111,... 也适用于 00,0000,000000,....
^(((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*)|([1]{2})*|([0]{2})*)$
适用于所有情况。因此，如果字符串仅包含 1 或仅 0：
([1]{2})*|([0]{2})*
如果它包含 0 和 1 的混合，则正向前瞻将处理该问题。
((?=(?:1*01*01*)*$)(?=(?:0*10*10*)*$).*
将它们结合起来，它考虑了所有具有偶数个 0 和 1 的字符串。
于 2018-07-23T14:15:22.647 回答