Addition correcte de deux nombres binaires avec une regex PCRE

Question

Est-il possible de faire correspondre une addition sous forme de (?<a>[01]+)\s*\+\s*(?<b>[01]+)\s*=\s*(?<c>[01]+) , donde a + b == c (comme dans l'addition binaire) doit tenir ?

Ils devraient correspondre :

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

Ils ne doivent pas correspondre :

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

Answer 1

TL;DR : Oui, c'est effectivement possible (à utiliser avec Jx drapeaux) :

(?(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

Démonstration en direct : https://regex101.com/r/yD1kL7/26

[ Mise à jour : En raison d'un bogue dans PCRE le code ne fonctionne dans tous les cas qu'avec le PCRE JIT actif ; merci à Qwerp-Derp pour en remarquant ; sans JIT, par exemple 100 + 101 = 1001 ne correspond pas].

C'est une regex assez monstrueuse. Alors, construisons-la étape par étape pour comprendre ce qui se passe.

Indice : Pour faciliter la mémorisation et le suivi de l'explication, permettez-moi d'expliquer les noms des groupes de capture à un ou deux chiffres (tous sauf les deux premiers sont drapeaux [voir ci-dessous]) :

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

Pour une plus grande lisibilité + y = avec éventuellement des espaces en tête et en queue, il existe deux groupes de saisie (?<add> \s*\+\s*) y (?<eq> \s*=\s*) .

Nous effectuons un ajout. Comme c'est une regex, nous devons vérifier chaque chiffre en une fois. Donc, jetez un coup d'oeil aux mathématiques derrière cela :

Vérification de l'addition d'un seul chiffre

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

Comment connaître le portage ?

Nous pouvons simplement regarder le dernier chiffre :

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

Cette logique est assurée par le groupe de capture carry définis comme suit :

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

avec cl étant si le dernier chiffre de l'opérande gauche était 1 ou non et cr si le dernier chiffre de l'opérande droit était 1 ou non ; \d0 est de vérifier si le dernier chiffre du résultat est 0.

Note : (?(cl) ... | ...) est une construction conditionnelle qui vérifie si un groupe de capture a été défini ou non. Étant donné que les groupes de capture ont une portée à chaque niveau de récursion, cette construction est facilement utilisable comme mécanisme pour définir une valeur booléenne. drapeau (peut être réglé avec (?<cl>) n'importe où) qui peuvent ensuite faire l'objet d'une action conditionnelle.

Ensuite, l'ajout proprement dit est simple :

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

exprimée par le digitadd groupe de capture (utilisant a ^ b == (a && !b) || (!a && b) en utilisant l1 étant si le chiffre de l'opérande gauche est égal à 1 et r1 de manière équivalente pour le chiffre de droite :

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

Vérification de l'addition à un décalage donné

Maintenant, que l'on peut vérifier, étant donné un défini cr , cl , l1 y r1 si le chiffre du résultat est correct en invoquant simplement (?&digitadd) à ce décalage.

... à ce décalage. C'est le prochain défi, trouver ce décalage.

La question fondamentale est la suivante : étant donné trois chaînes de caractères avec un séparateur connu entre elles, comment trouver le décalage correct ? de la droite .

Par exemple 1***+****0***=****1*** (les séparateurs sont + y = ici, et * désignant tout chiffre arbitraire).

Ou même, plus fondamentalement : 1***+****0***=1 .

Cela peut être assorti :

(?<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)
)

(Un grand merci ici à nhahdth pour son solution à cette question - modifié ici un peu pour s'adapter à l'exemple)

Tout d'abord, nous stockons des informations sur le chiffre à l'offset actuel ( (?:1(?<l1>)|0) - fixer le drapeau (c'est-à-dire le groupe de capture qui peut être vérifié avec (?(flag) ... | ...) ) l1 lorsque le chiffre actuel est 1.

Ensuite, nous construisons la chaîne à droite de l'offset recherché de l'opérande de droite de manière récursive avec (?=\d* + \d*(?<r>\d\k<r>) =) \d (?&fundamentalrecursedigit) qui avance d'un chiffre (sur l'opérande de gauche) à chaque niveau de récurrence. y ajoute un chiffre de plus à la partie droite de l'opérande de droite : (?<r> \d \k<r>) redéfinit le r groupe de capture et ajoute un autre chiffre à la capture déjà existante (référencée par \k<r> ).

Ainsi, comme cela se répète tant qu'il y a des chiffres dans l'opérande de gauche et qu'un chiffre exactement est ajouté à l'opérande de droite, le résultat est le suivant : un chiffre est ajouté à l'opérande de gauche. r groupe de capture par niveau de récurrence, ce groupe de capture contiendra exactement autant de caractères qu'il y avait de chiffres dans l'opérande de gauche.

Maintenant, à la fin de la récursion (c'est-à-dire lorsque le séparateur + est atteint), nous pouvons aller directement à l'offset correct via \d*(?:1(?<r1>)|0)\k<r> car le chiffre recherché sera maintenant exactement le chiffre avant ce que le groupe de capture r assortis.

Ayant maintenant aussi le r1 Nous pouvons aller jusqu'au bout, en vérifiant l'exactitude du résultat avec des conditionnels simples : (?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) .

Compte tenu de ce qui précède, il est trivial d'étendre cela à 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)
)

en utilisant exactement la même astuce, en collectant également la partie droite du résultat dans un fichier f groupe de capture et accéder à l'offset juste avant ce que ce groupe de capture f appariés.

Ajoutons la prise en charge d'un carry, qui consiste simplement à définir le paramètre cr y cl indique si le chiffre suivant est 1 via (?=(?<cr/cl>1)?) après les chiffres actuels des opérandes gauche et droit :

(?<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)
)

Vérification des entrées de longueurs égales

Maintenant, nous pourrions avoir fini ici si nous remplissions toutes les entrées avec suffisamment de zéros :

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

c'est-à-dire affirmer pour chaque chiffre de l'opérande de gauche de manière récursive que l'addition peut être effectuée et ensuite réussir.

Mais évidemment, nous n'avons pas encore fini. Qu'en est-il :

1. l'opérande de gauche étant plus long que celui de droite ?
2. l'opérande de droite étant plus long que celui de gauche ?
3. l'opérande de gauche étant aussi long ou plus long que l'opérande de droite et le résultat ayant une retenue au niveau du chiffre le plus significatif (c'est-à-dire nécessitant un 1 en tête) ?

Traiter un opérande gauche plus long que le droit

Celui-ci est assez trivial, il suffit d'arrêter d'essayer d'ajouter des chiffres au r capturer le groupe lorsque nous l'avons capturé complètement, mettre un drapeau (ici : ro ) pour ne plus le considérer comme éligible au portage et faire un chiffre en tête. r facultatif (par (?:\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)
)

Il s'agit maintenant de traiter l'opérande de droite comme si elle était remplie de zéro ; r1 y cr ne sera plus jamais réglé après ce point. Ce qui est tout ce dont nous avons besoin.

Il peut être facile de se demander pourquoi nous pouvons définir l'option ro immédiatement lorsqu'il dépasse la longueur des opérateurs de droite et ignore immédiatement le report ; la raison est la suivante checkdigit consomme déjà le premier chiffre à la position actuelle, donc nous sommes en fait déjà plus d'un chiffre après la fin de l'opérande de droite.

L'opérande de droite est plus long que celui de gauche.

C'est maintenant un peu plus difficile. On ne peut pas le mettre dans recursedigit car celui-ci va juste itérer aussi souvent qu'il y a des chiffres dans l'opérande de gauche. Nous avons donc besoin d'une correspondance séparée pour cela.

Il y a maintenant quelques cas à considérer :

1. Il y a un report à partir de l'addition du chiffre le plus significatif de l'opérande de gauche.
2. Il n'y a pas de portage.

Dans le premier cas, nous voulons faire correspondre 10 + 110 = 1000 , 11 + 101 = 1000 ; dans ce dernier cas, nous voulons faire correspondre 1 + 10 = 11 o 1 + 1000 = 1001 .

Pour simplifier notre tâche, nous allons ignorer les zéros de tête pour le moment. Nous savons donc que le chiffre le plus significatif est 1. Il y a maintenant pas de porter seulement et seulement si :

• le chiffre à l'offset actuel (c'est-à-dire l'offset du chiffre le plus significatif de l'opérande de gauche) dans l'opérande de droite est 0
• et il n'y a pas eu de report depuis le décalage précédent, ce qui signifie que le chiffre actuel dans le résultat est 1.

Cela se traduit par l'affirmation suivante :

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

Dans ce cas, nous pouvons capturer le premier \d+ con (?<remaining>\d+) et exiger qu'il soit en face de \k<f> (la partie à droite de l'offset actuel du résultat) :

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

Sinon, s'il y a une retenue, nous devons incrémenter la partie gauche de l'opérande de droite :

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

et l'utiliser comme :

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

Ce site carryoverflow Le groupe de capture fonctionne en copiant la partie gauche de l'opérande de droite, en y trouvant le dernier zéro et en remplaçant tous les uns moins significatifs que ce zéro par des zéros et le zéro par un un. Dans le cas où il n'y a pas de zéro dans cette partie, les uns sont simplement tous remplacés par un zéro et un premier un est ajouté.

Ou pour l'exprimer de façon moins verbeuse (n étant arbitraire, de sorte qu'il s'agit de s'adapte à ) :

  (?<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

Appliquons donc notre technique habituelle pour déterminer les parties à droite des opérandes :

(?<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)
)

Notez que j'ai ajouté un (*PRUNE) après (?&eq) dans la première branche afin d'éviter de revenir en arrière dans la deuxième branche avec carryoverflow au cas où il n'y aurait pas de report et où le résultat ne correspondrait pas.

Note : Nous n'effectuons aucun contrôle sur les \k<f> ici, cette partie est gérée par le carrycheckdigit capturer le groupe depuis le haut.

Le cas du leader 1

Nous ne voulons certainement pas 1 + 1 = 0 à faire correspondre. Ce qui est le cas si l'on s'en tient checkdigit seul. Il y a donc différentes circonstances dans lesquelles ce premier 1 est nécessaire (s'il n'est pas encore couvert par le cas précédent où l'opérande de droite est plus long) :

• Les deux opérandes (sans zéros non significatifs) sont de longueur égale (c'est-à-dire qu'ils ont tous deux un 1 dans leur chiffre le plus significatif, qui, additionné, laisse une retenue).
• L'opérande de gauche est plus long et il y a un report au chiffre le plus significatif ou les deux chaînes sont aussi longues.

Le premier cas traite les entrées comme 10 + 10 = 100 le second cas traite 110 + 10 = 1000 ainsi que 1101 + 11 = 10100 et le dernier trivialement 111 + 10 = 1001 .

Le premier cas peut être traité en définissant un drapeau ro si l'opérande de gauche est plus long que celui de droite, ce qui peut ensuite être vérifié à la fin de la récursion :

(?<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)
)

Dans le second cas, il suffit de vérifier l'existence d'un carry en cas de ro (c'est-à-dire que l'opérande de droite est plus court). La retenue peut généralement être vérifiée (puisque le chiffre le plus significatif est toujours 1 et que le chiffre de l'opérande de droite est implicitement 0) avec une simple opération de vérification. (?:1(?=0))?\k<f>\b - s'il y a eu une retenue, le chiffre à l'offset actuel dans le résultat sera 0.

C'est facilement possible, car, après tout, tous les autres chiffres jusqu'au décalage actuel seront tous vérifiés par checkdigit avant. Par conséquent, nous pourrions simplement vérifier le portage localement ici.

Ainsi, nous pouvons l'ajouter à la première branche de la fonction recurseequallength l'alternance :

(?<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)
)

Ensuite, pour câbler le tout : vérifiez d'abord checkdigit pour chaque chiffre individuel (comme dans le cas simple de la mise à zéro de l'avant) et ensuite initialiser les différents groupes de capture utilisés par recurseoverflow :

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

Et les zéros ?

0 + x = x y x + 0 = x ne sont toujours pas traitées et échoueront.

Au lieu de créer de grands groupes de capture pour les traiter de façon peu élégante, nous nous contentons de les traiter manuellement :

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

Note : Lorsqu'on l'utilise en alternance avec la branche principale, il faut mettre une (*PRUNE) après le (?&eq) afin d'éviter de sauter dans cette branche principale lorsque l'un des opérandes est nul et que la correspondance échoue.

Maintenant, nous avons toujours supposé qu'il n'y avait pas de zéros en tête dans les entrées pour simplifier nos expressions. Si vous regardez la regex initiale, vous trouverez de nombreuses occurrences de 0* y 0*+ (possessif pour éviter de revenir en arrière et que des choses inattendues se produisent) afin de sauter les zéros de tête car nous supposons à certains endroits que le chiffre le plus à gauche est un 1.

Conclusion

Et c'est tout. Nous avons réussi à faire correspondre uniquement des additions correctes de nombres binaires.

Une petite note concernant le relativement nouveau J flag : il permet de redéfinir les groupes de capture. Ceci est d'abord important pour initialiser les groupes de capture à une valeur vide. De plus, cela simplifie certaines conditionnalités (telles que addone ) car nous ne devons vérifier qu'une seule valeur au lieu de deux. Comparez (?(a) ... | ...) vs. (?(?=(?(a)|(?(b)|(*F)))) ... | ...) . De plus, il n'est pas possible de réorganiser arbitrairement les groupes de capture définis de façon multiple à l'intérieur de la structure de la (?(DEFINE) ...) construire.

Note finale : L'addition binaire n'est pas un langage de type 3 (c'est-à-dire régulier) de Chomsky. Il s'agit d'une réponse spécifique à PCRE, utilisant des fonctionnalités spécifiques à PCRE. (D'autres saveurs de regex comme .NET peuvent être capables de résoudre ce problème, mais pas toutes).

S'il y a des questions, veuillez laisser un commentaire, j'essaierai ensuite de les clarifier dans cette réponse.