c# java regex capturing-group nested-reference

c# - ¿Cómo esta expresión regex encuentra números triangulares?



java capturing-group (1)

Explicación

Aquí hay un desglose esquemático del patrón:

from beginning… | …to end | | ^(/1.|^.)+$ /______/|___match group 1 one-or-more times

Los brackets (…) definen el grupo de captura 1, y este grupo se combina repetidamente con + . Este subpatrón está anchored con ^ y $ para ver si puede coincidir con la cadena completa.

El Grupo 1 intenta hacer coincidir this|that alternates :

  • /1. , es decir, qué grupo 1 coincidió (¡auto referencia!), más uno de "cualquier" carácter ,
  • o ^. , es decir, solo "un" personaje al principio

Tenga en cuenta que en el grupo 1, tenemos una referencia a lo que el grupo 1 igualó. Esta es una referencia anidada / propia , y es la idea principal introducida en este ejemplo. Tenga en cuenta que cuando se repite un grupo de captura, generalmente solo conserva la última captura , por lo que la auto referencia en este caso básicamente dice:

"Trata de hacer coincidir lo que hice coincidir la última vez, más uno más. Eso es lo que igualaré esta vez".

Similar a una recursión, tiene que haber un "caso base" con referencias propias. En la primera iteración de + , el grupo 1 no había capturado nada aún (lo cual NO es lo mismo que decir que comienza con una cadena vacía). Por lo tanto, se introduce la segunda alternancia, como una forma de "inicializar" el grupo 1, que es que se permite capturar un carácter cuando está al principio de la cadena.

Entonces, como se repite con + , el grupo 1 primero intenta hacer coincidir 1 carácter, luego 2, luego 3, luego 4, etc. La suma de estos números es un número triangular.

Exploraciones adicionales

Tenga en cuenta que, para simplificar, utilizamos cadenas que constan del mismo carácter repetitivo que nuestra entrada. Ahora que sabemos cómo funciona este patrón, podemos ver que este patrón también puede coincidir con cadenas como "1121231234" , "aababc" , etc.

Tenga en cuenta también que si encontramos que n es un número triangular, es decir, n = 1 + 2 + ... + k , la longitud de la cadena capturada por el grupo 1 al final será k .

Ambos puntos se muestran en el siguiente fragmento de C # ( también visto en ideone.com ):

Regex r = new Regex(@"^(/1.|^.)+$"); Console.WriteLine(r.IsMatch("aababc")); // True Console.WriteLine(r.IsMatch("1121231234")); // True Console.WriteLine(r.IsMatch("iLoveRegEx")); // False for (int n = 0; n <= 50; n++) { Match m = r.Match("".PadLeft(n)); if (m.Success) { Console.WriteLine("{0} = sum(1..{1})", n, m.Groups[1].Length); } } // 1 = sum(1..1) // 3 = sum(1..2) // 6 = sum(1..3) // 10 = sum(1..4) // 15 = sum(1..5) // 21 = sum(1..6) // 28 = sum(1..7) // 36 = sum(1..8) // 45 = sum(1..9)

Notas de sabor

No todos los sabores admiten referencias anidadas. Siempre familiarícese con las peculiaridades del sabor con el que está trabajando (y, en consecuencia, casi siempre ayuda a proporcionar esta información cada vez que hace preguntas relacionadas con expresiones regulares).

En la mayoría de los sabores, el mecanismo estándar de correspondencia de expresiones regulares intenta ver si un patrón puede coincidir con cualquier parte de la cadena de entrada (posiblemente, pero no necesariamente, toda la entrada). Esto significa que debe recordar anclar siempre su patrón con ^ y $ siempre que sea necesario.

Java es ligeramente diferente en que String.matches , Pattern.matches y Matcher.matches intentan emparejar un patrón con toda la cadena de entrada. Esta es la razón por la que los anclajes se pueden omitir en el fragmento anterior.

Tenga en cuenta que en otros contextos, es posible que necesite usar anclajes /A y /Z lugar. Por ejemplo, en el modo multilínea , ^ y $ coinciden con el comienzo y el final de cada línea en la entrada.

Una última cosa es que en .NET regex, PUEDE obtener todas las capturas intermedias realizadas por un grupo de captura repetido. En la mayoría de los sabores, no puedes: todas las capturas intermedias se pierden y solo puedes quedarte la última.

Preguntas relacionadas

Material de bonificación: ¡Usando expresiones regulares para encontrar potencia de dos!

Con una ligera modificación, puede usar las mismas técnicas presentadas aquí para encontrar el poder de dos.

Aquí está la propiedad matemática básica que desea aprovechar:

  • 1 = 1
  • 2 = (1) + 1
  • 4 = (1 + 2) + 1
  • 8 = (1 + 2 + 4) + 1
  • 16 = (1 + 2 + 4 + 8) + 1
  • 32 = (1 + 2 + 4 + 8 + 16) + 1

La solución se da a continuación (¡pero primero intenta resolverla tú mismo!)

(ver en ideone.com en PHP , Java y C# ):

^(/1/1|^.)*.$

Parte de una serie de artículos educativos de expresiones regulares, esta es una introducción suave al concepto de referencias anidadas.

Los primeros pocos números triangulares son:

1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5

Hay muchas maneras de verificar si un número es triangular. Existe esta técnica interesante que usa expresiones regulares de la siguiente manera:

  • Dado n , primero creamos una cadena de longitud n llena con el mismo personaje
  • Luego hacemos coincidir esta cadena con el patrón ^(/1.|^.)+$
    • n es triangular si y solo si este patrón coincide con la cadena

Aquí hay algunos fragmentos para mostrar que esto funciona en varios idiomas:

PHP (en ideone.com)

$r = ''/^(/1.|^.)+$/''; foreach (range(0,50) as $n) { if (preg_match($r, str_repeat(''o'', $n))) { print("$n "); } }

Java (en ideone.com)

for (int n = 0; n <= 50; n++) { String s = new String(new char[n]); if (s.matches("(//1.|^.)+")) { System.out.print(n + " "); } }

C # (en ideone.com)

Regex r = new Regex(@"^(/1.|^.)+$"); for (int n = 0; n <= 50; n++) { if (r.IsMatch("".PadLeft(n))) { Console.Write("{0} ", n); } }

Entonces esta expresión regular parece funcionar, pero ¿alguien puede explicar cómo?

Preguntas similares