regex - probar - expresiones regulares java

Haga coincidir la suma correcta de dos números binarios con la expresión regular PCRE (1)

TL; DR : Sí, de hecho es posible (usar con banderas 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

Demostración en vivo: https://regex101.com/r/yD1kL7/26

[ Actualización : debido a un error en PCRE , el código solo funciona para todos los casos con PCRE JIT activo; gracias a Qwerp-Derp por noticing ; sin JIT, por ejemplo, 100 + 101 = 1001 no coincide.]

Esa es una expresión regular monstruosa. Entonces, vamos a construirlo paso a paso para comprender lo que está sucediendo.

Sugerencia : para una memorización más fácil y seguir la explicación, permítanme explicar los nombres de los nombres de grupos de captura de uno o dos dígitos (todos excepto los dos primeros son indicadores [ver más abajo]):

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

Para un + y = más legibles con posibles espacios iniciales y finales, hay dos grupos de captura (?<add> /s*/+/s*) y (?<eq> /s*=/s*) .

Estamos realizando una adición. Como es una expresión regular, necesitamos verificar cada dígito a la vez. Entonces, eche un vistazo a las matemáticas detrás de esto:

Comprobación de la adición de un solo dígito

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

¿Cómo sabemos el llevar?

Simplemente podemos mirar el último dígito:

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

Esta lógica es proporcionada por el carry grupo de captura, definido de la siguiente manera:

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

siendo cl si el último dígito del operando izquierdo fue 1 o no y cr si el último dígito del operando derecho fue 1 o no; /d0 es para verificar si el último dígito en el resultado fue 0.

Nota : (?(cl) ... | ...) es una construcción condicional que verifica si se ha definido un grupo de captura o no. Debido a que los grupos de captura tienen un alcance para cada nivel de recursión, esto se puede usar fácilmente como un mecanismo para establecer una bandera booleana (se puede establecer con (?<cl>) cualquier lugar) que luego se puede actuar condicionalmente.

Entonces la adición real es simple:

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

expresado por el grupo de captura digitadd (usando a ^ b == (a && !b) || (!a && b) , usando l1 si el dígito del operando izquierdo es igual a 1 y r1 equivalente para el dígito derecho:

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

Comprobación de la suma en un desplazamiento determinado

Ahora, que podemos verificar, dado un cr , cl , l1 y r1 definidos, si el dígito en el resultado es correcto simplemente invocando (?&digitadd) en ese desplazamiento.

... en ese desplazamiento. Ese es el próximo desafío, encontrar dicho desplazamiento.

El problema fundamental es, dadas tres cadenas con un separador conocido en el medio, cómo encontrar el desplazamiento correcto desde la derecha .

Por ejemplo 1***+****0***=****1*** (los separadores son + y = aquí, y * denota cualquier dígito arbitrario).

O incluso, más fundamentalmente: 1***+****0***=1 .

Esto se puede combinar con:

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

(Muchas gracias aquí a nhahdth por su solution a este problema, modificado aquí un poco para ajustarse al ejemplo)

Primero estamos almacenando información sobre el dígito en el desplazamiento actual ( (?:1(?<l1>)|0) - establecemos la bandera (es decir, capturamos el grupo que puede verificarse con (?(flag) ... | ...) ) l1 cuando el dígito actual es 1.

Luego construimos la cadena a la derecha del desplazamiento buscado del operando derecho recursivamente con (?=/d* + /d*(?<r>/d/k<r>) =) /d (?&fundamentalrecursedigit) , que avanza un dígito (en el operando izquierdo) en cada nivel de recursión y agrega un dígito más a la parte derecha del operando derecho: (?<r> /d /k<r>) redefine el grupo de captura r y agrega otro dígito a la captura ya existente (referenciada con /k<r> ).

Por lo tanto, como esto se repite siempre que haya dígitos en el operando izquierdo y se agregue exactamente un dígito al grupo de captura r por nivel de recursión, ese grupo de captura contendrá exactamente tantos caracteres como dígitos en el operando izquierdo.

Ahora, al final de la recursión (es decir, cuando se alcanza el separador + ), podemos ir directamente al desplazamiento correcto a través de /d*(?:1(?<r1>)|0)/k<r> , como el dígito buscado ahora será exactamente el dígito antes de lo que coincide el grupo de captura.

Teniendo ahora también el indicador r1 establecido condicionalmente, podemos ir al final, verificando la corrección del resultado con condicionales simples: (?(r1) (?(l1) 0 | 1) | (?(l1) 1 | 0) .

Dado esto, es trivial extender esto a 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) )

usando exactamente el mismo truco, recogiendo también la parte correcta del resultado en un grupo de captura f y accediendo al desplazamiento justo antes de lo que este grupo de captura f coincide.

Agreguemos soporte para un carry, que realmente solo establece las banderas cr y cl si el siguiente dígito fue 1 a través de (?=(?<cr/cl>1)?) Después de los dígitos actuales de los operandos izquierdo y derecho:

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

Comprobando entradas de igual longitud

Ahora, podríamos hacer aquí si tuviéramos que rellenar todas las entradas con suficientes ceros:

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

es decir, para cada dígito del operando izquierdo recursivamente, se puede realizar la suma y luego tener éxito.

Pero obviamente, aún no hemos terminado. Qué pasa:

¿El operando izquierdo es más largo que el derecho?
¿El operando derecho es más largo que el izquierdo?
¿el operando izquierdo es tan largo o más largo que el operando derecho y el resultado tiene un carry en el dígito más significativo (es decir, necesita un 1 inicial)?

Manejar un operando izquierdo más largo que el derecho

Ese es bastante trivial, simplemente deje de intentar agregar dígitos al grupo de captura r cuando lo hayamos capturado por completo, coloque una bandera (aquí: ro ) para que ya no lo considere elegible para llevarlo y haga un dígito con r opcional (por (?:/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) )

Esto ahora maneja el operando correcto como si estuviera rellenado con ceros; r1 y cr ahora nunca se establecerán después de ese punto. Que es todo lo que necesitamos.

Puede ser fácil confundirse aquí por qué podemos establecer el indicador ro inmediatamente cuando excedemos la longitud correcta de los operadores e ignorar inmediatamente el carry; la razón es que el checkdigit ya está consumiendo el primer dígito en la posición actual, por lo que en realidad ya estamos más de un dígito más allá del final del operando correcto.

El operando derecho pasa a ser más largo que el izquierdo

Esto ahora es un poco más difícil. No podemos recursedigit en recursedigit ya que ese solo repetirá recursedigit veces como haya dígitos en el operando izquierdo. Por lo tanto, necesitamos una coincidencia separada para eso.

Ahora hay algunos casos a considerar:

Hay un acarreo por la adición del dígito más significativo del operando izquierdo
No hay llevar.

Para el primer caso, queremos hacer coincidir 10 + 110 = 1000 , 11 + 101 = 1000 ; para el último caso queremos hacer coincidir 1 + 10 = 11 o 1 + 1000 = 1001 .

Para simplificar nuestra tarea, vamos a ignorar los ceros iniciales por ahora. Entonces sabemos que el dígito más significativo es 1. Ahora no hay carry solo y solo si:

el dígito en el desplazamiento actual (es decir, el desplazamiento del dígito más significativo del operando izquierdo) en el operando derecho es 0
y no hubo arrastre del desplazamiento anterior, lo que significa que el dígito actual en el resultado es 1.

Esto se traduce en la siguiente afirmación:

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

En ese caso, podemos capturar el primer /d+ con (?<remaining>/d+) y requerir que esté delante de /k<f> (la parte a la derecha del desplazamiento actual del resultado):

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

De lo contrario, si hay un carry, necesitamos incrementar la parte izquierda del operando derecho:

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

y úsalo como:

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

Este grupo de captura de carryoverflow funciona copiando la parte izquierda del operando derecho, encontrando el último cero allí y reemplazando todos los menos significativos que ese cero por ceros y el cero por uno. En caso de que no haya cero en esa parte, los que están simplemente son reemplazados por un cero y se agrega uno inicial.

O para expresarlo menos verbalmente (siendo n arbitrario, para que encaje ):

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

Entonces, apliquemos nuestra técnica habitual para descubrir las partes a la derecha de los operandos:

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

Tenga en cuenta que he agregado un (*PRUNE) después de (?&eq) en la primera rama para evitar retroceder en la segunda rama con carryoverflow , en caso de que no haya carry y el resultado no coincida.

Nota : Aquí no realizamos ninguna verificación en la parte /k<f> , esto es administrado por el grupo de captura carrycheckdigit desde arriba.

El caso del líder 1

Seguro que no queremos que 1 + 1 = 0 coincida. Sin embargo, es lo que checkdigit si vamos solo con checkdigit de checkdigit . Por lo tanto, hay diferentes circunstancias en las que ese primer 1 es necesario (si aún no está cubierto por el caso anterior de que el operando correcto sea más largo):

Ambos operandos (sin ceros a la izquierda) son de igual longitud (es decir, ambos tienen un 1 en su dígito más significativo, lo que, sumado, deja un acarreo)
El operando izquierdo es más largo y hay un acarreo en el dígito más significativo o ambas cadenas son igual de largas.

El primer caso maneja entradas como 10 + 10 = 100 , el segundo caso maneja 110 + 10 = 1000 así como 1101 + 11 = 10100 y el último trivialmente 111 + 10 = 1001 .

El primer caso puede manejarse estableciendo un indicador ro si el operando izquierdo es más largo que el derecho, que luego se puede verificar al final de la recursividad:

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

El segundo caso significa que solo debemos verificar la existencia de un carry en caso de ro (es decir, el operando correcto es más corto). El carry se puede comprobar como de costumbre (ya que el dígito más significativo siempre es 1 y el dígito de operandos derecho es implícitamente 0 entonces) con un trivial (?:1(?=0))?/k<f>/b - si fue un carry el dígito en el desplazamiento actual en el resultado será 0.

Eso es fácilmente posible, ya que, después de todo, todos los demás dígitos hasta el desplazamiento actual serán verificados por checkdigit antes. Por lo tanto, podríamos verificar el transporte local aquí.

Por lo tanto, podemos agregar esto a la primera rama de la alternancia de recurseequallength de la 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) )

Luego, para conectar todo: primero verifique el checkdigit verificación para cada dígito individual (igual que para el caso simple con relleno de cero de antes) y luego inicialice los diferentes grupos de captura utilizados por recurseoverflow :

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

¿Qué hay de los ceros?

0 + x = x y x + 0 = x todavía no se manejan y fallarán.

En lugar de hackear grandes grupos de captura para manejarlo feamente, recurrimos a manejarlos manualmente:

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

Nota : Cuando se usa en alternancia con la rama principal, necesitamos poner un (*PRUNE) después de (?&eq) para evitar saltar a esa rama principal cuando cualquier operando es cero y la coincidencia falla.

Ahora, también asumimos que no había ceros a la izquierda en las entradas para simplificar nuestras expresiones. Si observa la expresión regular inicial, encontrará muchas ocurrencias de 0* y 0*+ (posesivas para evitar retroceder en ella y ... suceden cosas inesperadas) para omitir los ceros a la izquierda, ya que asumimos en algunos lugares que el extremo izquierdo el dígito es un 1.

Conclusión

Y eso es. Logramos igualar solo las sumas correctas de números binarios.

Una pequeña nota sobre la relativamente nueva bandera J : permite redefinir los grupos de captura. Esto es importante en primer lugar para inicializar los grupos de captura a un valor vacío. Además, simplifica algunos condicionales (como addone ) ya que solo tenemos que verificar un valor en lugar de dos. Compare (?(a) ... | ...) vs. (?(?=(?(a)|(?(b)|(*F)))) ... | ...) . Además, no es posible reordenar los grupos de captura definidos de forma múltiple arbitrariamente dentro de la construcción (?(DEFINE) ...) .

Nota final: la adición binaria no es un lenguaje Chomsky tipo 3 (es decir, regular). Esta es una respuesta específica de PCRE, utilizando características específicas de PCRE. [Otros sabores de expresiones regulares como .NET también pueden resolverlo, pero no todos pueden hacerlo].

Si tiene alguna pregunta, deje un comentario, luego intentaré aclarar esto en esta respuesta.

¿Es posible hacer coincidir una adición en forma de (?<a>[01]+)/s*/+/s*(?<b>[01]+)/s*=/s*(?<c>[01]+) , donde a + b == c (como en la suma binaria) debe contener?

Estos deben coincidir con:

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

Estos no deben coincidir:

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