regex - 使用PCRE正则表达式匹配两个二进制数的正确加法

Question

是否可以匹配(?<a>[01]+)\s*\+\s*(?<b>[01]+)\s*=\s*(?<c>[01]+)形式的加法，其中a + b == c(如二进制加法)必须成立？

这些应该匹配:

0 + 0 = 0
0 + 1 = 1
1 + 10 = 11
10 + 111 = 1001
001 + 010 = 0011
1111 + 1 = 10000
1111 + 10 = 10010

这些不应该匹配:

0 + 0 = 10
1 + 1 = 0
111 + 1 = 000
1 + 111 = 000
1010 + 110 = 1000
110 + 1010 = 1000

Answer 1

TL; DR :是的，的确有可能(与Jx标志一起使用):

(?(DEFINE)
(?<add> \s*\+\s* )
(?<eq> \s*=\s* )
(?<carry> (?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) )
(?<digitadd> (?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) )
(?<recursedigit>
  (?&add) 0*+ (?:\d*(?:0|1(?<r1>)))? (?(ro)|(?=(?<cr>1)?))\k<r> (?&eq) \d*(?&digitadd)\k<f>\b
| (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recursedigit)
)
(?<checkdigit> (?:0|1(?<l1>)) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit) )
(?<carryoverflow>
  (?<x>\d+) 0 (?<y> \k<r> (?&eq) 0*\k<x>1 | 1(?&y)0 )
| (?<z> 1\k<r> (?&eq) 0*10 | 1(?&z)0 )
)
(?<recurseoverflow>
  (?&add) 0*+ (?(rlast) \k<r> (?&eq) 0*+(?(ro)(?:1(?=0))?|1)\k<f>\b
                | (?:(?<remaining>\d+)(?=0\d* (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) 0*\k<remaining>\k<f>\b
                   | (?&carryoverflow)\k<f>\b))
| (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|(?=(?:\d\k<r>(?&eq)(?<rlast>))?)\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b)
  \d(?&recurseoverflow)
)
(?<s>
  (| 0*? (?<arg>[01]+) (?&add) 0+ | 0+ (?&add) 0*? (?<arg>[01]+)) (?&eq) (*PRUNE) 0* \k<arg>
| 0*+
  (?=(?<iteratedigits> (?=(?&checkdigit))\d (?:\b|(?&iteratedigits)) ))
  (?=[01]+ (?&add) [01]+ (?&eq) [01]+ \b)
  (?<r>) (?<f>) (?&recurseoverflow)
)
)
\b(?&s)\b

现场演示:https://regex101.com/r/yD1kL7/26

[更新:由于存在bug in PCRE，因此该代码仅适用于PCRE JIT处于 Activity 状态的所有情况；感谢Qwerp-Derp的noticing;没有JIT例如100 + 101 = 1001不匹配。]

那真是个怪异的正则表达式。因此，让我们逐步构建它以了解发生了什么。

提示:为了便于记忆并按照说明进行操作，让我解释一下一个或两位数字捕获组名称的名称(除了前两个都是标志[参见下文]):

r => right; it contains the part of the right operand right to a given offset
f => final; it contains the part of the final operand (the result) right to a given offset
cl => carry left; the preceding digit of the left operand was 1
cr => carry right; the preceding digit of the right operand was 1
l1 => left (is) 1; the current digit of the left operand is 1
r1 => right (is) 1; the current digit of the right operand is 1
ro => right overflow; the right operand is shorter than the current offset
rlast => right last; the right operand is at most as long as the current offset

为了使可读性更高的+和=带有可能的前导和尾随空格，有两个捕获组(?<add> \s*\+\s*)和(?<eq> \s*=\s*)。

我们正在执行添加。由于是正则表达式，因此我们需要一次验证每个数字。因此，请看一下其背后的数学:

检查一位数字的加法

current digit = left operand digit + right operand digit + carry of last addition

我们怎么知道进位？

我们可以简单地查看最后一位:

carry =    left operand digit == 1 && right operand digit == 1
        || (left operand digit == 1 || right operand digit == 1) && result digit == 0

此逻辑由捕获组carry提供，定义如下:

(?<carry> (?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) )

cl是最后一个左操作数位是否为1，cr是最后一个右操作数位是否为1； \d0用于检查结果中的最后一位是否为0。

注意:(?(cl) ... | ...)是一个条件构造，用于检查是否已定义捕获组。由于捕获组的作用域是递归的每个级别，因此它很容易用作设置 bool(boolean) 标志(可以在任何地方使用(?<cl>)设置)的机制，以后可以有条件地对其进行操作。

那么实际的加法很简单:

is_one = ((left operand digit == 1) ^ (right operand digit == 1)) ^ carry

由digitadd捕获组表示(使用a ^ b == (a && !b) || (!a && b)，使用l1表示左操作数的位数是否等于1，而r1等于右位数:

(?<digitadd> (?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) )

检查给定偏移量的加法

现在，在给定的cr，cl，l1和r1的情况下，我们可以通过简单地在该偏移量处调用(?&digitadd)来验证结果数字是否正确。

...以该偏移量。找到下一个偏移量是下一个挑战。

基本的问题是，给定三个字符串之间有一个已知的分隔符，如何找到从右侧开始的正确偏移量。

例如1***+****0***=****1***(分隔符在这里是+和=，而*表示任意数字)。

甚至更根本地:1***+****0***=1。

可以与以下内容匹配:

(?<fundamentalrecursedigit>
  \+ \d*(?:1(?<r1>)|0)\k<r> = (?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) ) \b
| (?=\d* + \d*(?<r>\d\k<r>) =) \d (?&fundamentalrecursedigit)
)
(?<fundamentalcheckdigit>
  # Note: (?<r>) is necessary to initialize the capturing group to an empty string
  (?:1(?<l1>)|0) (?<r>) (?&fundamentalrecursedigit)
)

(非常感谢nhahdth对此问题的solution，在此做了一些修改以适合示例)

首先，我们在当前偏移量处存储有关位数的信息((?:1(?<l1>)|0)-设置当前位数为1时的标志(即可以使用(?(flag) ... | ...)进行检查的捕获组)l1。

然后，我们使用(?=\d* + \d*(?<r>\d\k<r>) =) \d (?&fundamentalrecursedigit)递归地在搜索到的右操作数的偏移量的右侧构建字符串，该字符串在每个递归级别上前进一位数(在左操作数上)，并在右操作数的右侧部分再加上一位: (?<r> \d \k<r>)重新定义r捕获组，并将另一个数字添加到已经存在的捕获中(用\k<r>引用)。

因此，只要递归，只要在左操作数上有数字，并且每个递归级别将精确的一位数字添加到r捕获组中，该捕获组将包含与左操作数上的数字一样多的字符。

现在，在递归结束时(即到达分隔符+时)，我们可以通过\d*(?:1(?<r1>)|0)\k<r>直接转到正确的偏移量，因为搜索到的数字现在正好是捕获组r匹配的数字。

现在也有条件地设置了r1标志，我们可以使用简单的条件语句(?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0)来检查结果是否正确。

鉴于此，将其扩展到1***+****0***=****1***是微不足道的:

(?<fundamentalrecursedigit>
  \+ \d*(?:1(?<r1>)|0)\k<r> = \d*(?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) )\k<f> \b
| (?=\d* + \d*(?<r>\d\k<r>) = \d*(?<f>\d\k<f>)\b) \d (?&fundamentalrecursedigit)
)
(?<fundamentalcheckdigit>
  (?:1(?<l1>)|0) (?<r>) (?<f>) (?&fundamentalrecursedigit)
)

通过使用完全相同的技巧，还可以在f捕获组中收集结果的正确部分，并在此捕获组f与之匹配之前访问偏移量。

让我们添加对进位的支持，这实际上只是通过左操作数和右操作数的当前位之后的cr设置cl和(?=(?<cr/cl>1)?)标志是否下一位为1:

(?<carryrecursedigit>
  \+ \d* (?:1(?<r1>)|0) (?=(?<cr>1)?) \k<r> = \d* (?&digitadd) \k<f> \b
| (?=\d* + \d*(?<r>\d\k<r>) = \d*(?<f>\d\k<f>)\b) \d (?&carryrecursedigit)
)
(?<carrycheckdigit>
  (?:1(?<l1>)|0) (?=(?<cl>1)?) (?<r>) (?<f>) (?&carryrecursedigit)
)

检查相等长度的输入

现在，如果我们要用足够的零填充所有输入，就可以在这里完成:

\b
(?=(?<iteratedigits> (?=(?&carrycheckdigit)) \d (?:\b|(?&iteratedigits)) ))
[01]+ (?&add) [01]+ (?&eq) [01]+
\b

即，对左操作数的每个数字递归地断言可以执行加法，然后成功。

但是显然，我们还没有完成。关于什么:

左操作数长于右操作数？

右操作数长于左操作数？

左操作数与右操作数一样长或更长，并且结果的最高有效位数为进位(即需要前导1)吗？

处理左操作数要长于右操作数

那是非常琐碎的，只要在我们完全捕获了它之后就停止尝试将数字添加到r捕获组，设置一个标志(此处为ro)以使其不再适合携带，并使数字开头的r可选(通过(?:\d* (?:1(?<r1>)|0))? ):

(?<recursedigit>
  \+ (?:\d* (?:1(?<r1>)|0))? (?(ro)|(?=(?<cr>1)?)) \k<r> = \d* (?&digitadd) \k<f> \b
| (?=\d* + (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) = \d*(?<f>\d\k<f>)\b) \d (?&recursedigit)
)
(?<checkdigit>
  (?:1(?<l1>)|0) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit)
)

现在，它正在处理正确的操作数，就好像它是零填充的一样。现在，永远不会在此之后设置r1和cr。这就是我们所需要的。

在这里可能很容易混淆，为什么我们在超过正确的运算符长度时就可以立即设置ro标志，而立即忽略进位。原因是checkdigit已经在当前位置占用了第一位数字，因此实际上我们已经比右操作数的末尾多了一位数字。

右操作数恰好比左操作数长

现在，这有点困难。我们不能将其填入recursedigit中，因为只要左侧操作数中有数字，它就会进行迭代。因此，我们需要为此单独进行匹配。

现在有几种情况需要考虑:

左操作数的最高有效位加起来有一个进位

没有携带。

对于前一种情况，我们要匹配10 + 110 = 1000，11 + 101 = 1000;对于后一种情况，我们要匹配1 + 10 = 11或1 + 1000 = 1001。

为了简化我们的任务，我们现在暂时忽略前导零。那么我们知道最高有效位是1。现在只有在以下情况下才没有进位:

右操作数中当前偏移量的数字(即左操作数的最高有效位的偏移量)为0

，并且前一个偏移量没有进位，这意味着结果中当前位数为1。

这转化为以下断言:

\d+(?=0)\k<r> (?&eq) \d*(?=1)\k<f>\b

在这种情况下，我们可以使用\d+捕获第一个(?<remaining>\d+)并要求它在\k<f>的前面(结果当前偏移量右侧的部分):

(?<remaining>\d+)\k<r> (?&eq) \k<remaining>\k<f>\b

否则，如果有一个进位，我们需要增加右操作数的左部分:

(?<carryoverflow>
  (?<x>\d+) 0 (?<y> \k<r> (?&eq) \k<x>1 | 1(?&y)0 )
| (?<z> 1\k<r> (?&eq) 10 | 1(?&z)0 )
)

并将其用作:

(?&carryoverflow)\k<f>\b

该carryoverflow捕获组的工作方式是，复制右操作数的左侧部分，在该位置找到最后一个零，然后将比该零低有效的所有零替换为零，并用零替换零。如果该部分中没有零，则将它们全部替换为零，然后添加前导1。

或用较少的语言来表达(n是任意的，以便适合):

  (?<x>\d+) 0 1^n \k<r> (?&eq) \k<x> 1 0^n \k<f>\b
| 1^n \k<r> (?&eq) 1 0^n \k<f>\b

因此，让我们应用常规技术来找出操作数右侧的部分:

(?<recurselongleft>
  (?&add) (?:(?<remaining>\d+)(?=(?=0)\k<r> (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) \k<remaining>\k<f>\b
            | (?&carryoverflow)\k<f>\b)
| (?=\d* (?&add) \d*(?<r>\d\k<r>) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurselongleft)
)

请注意，我在第一个分支中的(*PRUNE)之后添加了一个(?&eq)，以避免在使用进位且结果不匹配的情况下使用carryoverflow回溯到第二个分支。

注意:在这里我们不对\k<f>部分进行任何检查，这是由上面的carrycheckdigit捕获组管理的。

案例1

我们确定不希望1 + 1 = 0匹配。如果仅按checkdigit进行操作，那会是什么。因此，在不同的情况下，前导1是必需的(如果前面的右操作数较长的情况还没有覆盖):

两个操作数(不带前导零)的长度相等(即，它们的最高有效位都为1，加在一起后留下一个进位)

左操作数更长，最高有效位有一个进位，或者两个字符串都一样长。

前一种情况处理诸如10 + 10 = 100之类的输入，第二种情况处理110 + 10 = 1000以及1101 + 11 = 10100，最后一种处理琐碎的111 + 10 = 1001。

第一种情况可以通过设置标志ro是否左操作数长于右操作数来处理，然后可以在递归结束时进行检查:

(?<recurseequallength>
  (?&add) \k<r> (?&eq) (?(ro)|1)\k<f>\b
| (?=\d* (?&add) (?:\k<r>(?<ro>) | \d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recurseequallength)
)

第二种情况意味着在ro的情况下(例如，右侧操作数较短)，我们只需要检查进位的存在。通常可以使用平凡的(?:1(?=0))?\k<f>\b来检查进位(因为最高有效位始终为1，而右边的操作数位则隐式为0)-如果存在进位，则当前偏移量处的位将为0。

这很容易实现，因为毕竟所有其他数字，直到当前偏移量都将通过checkdigit进行验证。因此，我们可以在这里本地检查进位。

因此，我们可以将其添加到recurseequallength交替的第一个分支中:

(?<recurseoverflow>
  (?&add) (?(rlast) \k<r> (?&eq) (?(ro)(?:1(?=0))?|1)\k<f>\b
                | (?:(?<remaining>\d+)(?=0\d* (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) \k<remaining>\k<f>\b
                   | (?&carryoverflow)\k<f>\b))
| (?=\d* (?&add) (?:\k<r>(?<ro>)|(?=(?:\d\k<r>(?&eq)(?<rlast>))?)\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b)
  \d(?&recurseoverflow)
)

然后将所有内容连接在一起:首先检查每个数字的checkdigit(与之前的简单零填充情况相同)，然后初始化recurseoverflow使用的不同捕获组:

\b
(?=(?<iteratedigits> (?=(?&checkdigit))\d (?:\b|(?&iteratedigits)) ))
(?=[01]+ (?&add) [01]+ (?&eq) [01]+ \b)
(?<r>) (?<f>) (?&recurseoverflow)
\b

零呢？
0 + x = x和x + 0 = x仍未处理，将失败。

我们没有用笨拙的方式来抓捕大型捕获小组，而是求助于手动处理它们:

(0*? (?<arg>[01]+) (?&add) 0+ | 0+ (?&add) 0*? (?<arg>[01]+)) (?&eq) 0* \k<arg>

注意:当与主分支交替使用时，我们需要在(*PRUNE)之后放置一个(?&eq)，以避免在任何操作数为零且匹配失败时跳入该主分支。

现在，我们还始终假设输入中没有前导零以简化表达式。如果您查看初始正则表达式，则会发现许多0*和0*+(可能避免回溯到其中，以及发生…意外情况)，以便跳过前导零，因为我们在某些地方假设最左边的数字是1。

结论

就是这样。我们只匹配了正确的二进制数加法。

关于相对较新的J标志的小注释:它允许重新定义捕获组。这对于将捕获组初始化为空值至关重要。此外，它简化了一些条件(例如addone)，因为我们只需要检查一个值即可，而不是两个。比较(?(a) ... | ...)与(?(?=(?(a)|(?(b)|(*F)))) ... | ...)。同样，不可能在(?(DEFINE) ...)构造内对重新定义的多个捕获组进行重新排序。

最后说明:二进制加法不是Chomsky 3类(即常规)语言。这是使用PCRE特定功能的PCRE特定答案。 [.NET等其他正则表达式也可以解决它，但并非所有人都可以。]

如有任何疑问，请发表评论，然后我将尝试在此答案中进行澄清。