Сопоставьте правильное сложение двух двоичных чисел с регулярным выражением PCRE

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

[обновление: из-за a ошибка в PCRE, код работает только для всех случаев с PCRE JIT active; благодаря Qwerp-Derp на заметили; без 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) ... | ...) является условной конструкцией, проверяющей, была ли определена группа захвата или нет. Из-за захвата групп, охватываемых каждым уровнем рекурсии, это легко использовать в качестве механизма для установки логического флаг (можно установить с (?<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) )

проверка сложения при a учитывая смещения

теперь, что мы можем проверить, учитывая определенный 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 за его решение к этому вопросу-изменено здесь немного, чтобы соответствовать примеру)

Сначала мы храним информацию о цифре при текущем смещении ((?:1(?<l1>)|0) - установить флаг (т. е. захват группы, которая может быть проверена с помощью (?(flag) ... | ...))l1 когда текущая цифра равна 1.

затем мы строим строку справа от искомого смещения правого операнда рекурсивно с (?=\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 флаги ли следующая цифра была 1 через (?=(?<cr/cl>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. левый операнд больше чем правый?
2. правый операнд длиннее левой?
3. левый операнд является таким же длинным или более длинным, чем правый операнд, и результат имеет перенос на самую значительную цифру (т. е. нуждается в ведущей 1)?

ручки левый операнд больше чем правый

это довольно тривиально, просто перестаньте пытаться добавить цифры в r захват группы когда мы захватили его полностью, установите флаг (здесь:ro) чтобы не считать его пригодным для переноса больше и сделать цифру ведущей r необязательно (by (?:\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 поскольку это будет просто повторяться так часто, как есть цифры в левом операнде. Таким образом, для этого нам нужен отдельный матч.

теперь есть несколько случаев, чтобы рассмотреть:

1. есть перенос от сложения самой значащей цифры левого операнда
2. нет никакого переноса.

для первого случая мы хотим соответствовать 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 захват группы работает путем копирования левой части правого операнда, находя там последний ноль и заменяя все менее значимые, чем этот ноль, нулями и нулем на единицу. В случае, если в этой части нет нуля, все они просто заменяются нулем и добавляется ведущий.

или выражать его менее словесно (причем 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 для сопоставления. Что, однако, если мы пройдем мимо