Come funziona questo regex trovare i numeri triangolari?

Question

  

_{Parte di una serie di articoli regex educativi, questo è una breve introduzione al concetto di riferimenti annidati.}

I primi numeri triangolari sono:

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

Ci sono molti modi per controllare se un numero è triangolare. C'è questa tecnica interessante che utilizza espressioni regolari come segue:

• Data n , per prima cosa creiamo una stringa di lunghezza n riempita con lo stesso carattere
• Abbiamo poi corrisponde a questa stringa contro il ^(\1.|^.)+$ modello
  • n è triangolare se e solo se questo modello corrisponde alla stringa

Ecco alcuni frammenti per dimostrare che questo funziona in diverse lingue:

PHP (su ideone.com)

$r = '/^(\1.|^.)+$/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java (su 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 # (su ideone.com)

Regex r = new Regex(@"^(\1.|^.)+$");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

Quindi questo regex sembra funzionare, ma qualcuno può spiegare come?

Domande simili

• Come determinare se un numero è un primo con regex?

Answer 1

Spiegazione

Ecco una ripartizione schematica del modello:

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

Il (…) parentesi define gruppo di cattura di 1, e questo gruppo è abbinato ripetutamente con +. Questo è subpattern ancorato con ^ e $ per vedere se può abbinare l'intera stringa.

Gruppo 1 tenta di abbinare this|that alterna :

• \1., che è, ciò che il gruppo 1 abbinato (auto di riferimento!), Più uno dei " qualsiasi" carattere ,
• o ^., cioè, un solo carattere "qualsiasi" all'inizio

Si noti che nel gruppo 1, abbiamo un riferimento a quale gruppo 1 abbinato! Questo è un annidati di riferimento / self , ed è l'idea principale introdotto in questo esempio. Tenete a mente che quando un gruppo di cattura è ripetuta, in genere mantiene solo l'ultimo di cattura , quindi il riferimento di sé in questo caso dice in sostanza:

  

"Cerca di far corrispondere ciò che ho abbinato l'ultima volta, più un altro. Questo è quello che ti abbino questo momento".

Simile a una ricorsione, ci deve essere un "caso base" con i riferimenti sé. Alla prima iterazione del +, gruppo 1 non aveva ancora catturato nulla (che è non lo stesso che dire che inizia con una stringa vuota). Quindi il secondo alternanza è introdotto, come un modo per "inizializzare" gruppo 1, che è che è consentito cattura un carattere quando è all'inizio della stringa.

Così come viene ripetuto con +, gruppo 1 primi tentativi per abbinare 1 carattere, poi 2, poi 3, poi 4, ecc La somma di questi numeri è un numero triangolare.

---

ulteriori esplorazioni

Si noti che per la semplificazione, abbiamo usato le stringhe che si compone dello stesso carattere ripetuto come il nostro ingresso. Ora che sappiamo come funziona questo modello, possiamo vedere che questo modello può anche corrispondere stringhe come "1121231234", "aababc", ecc.

Si noti anche che, se troviamo che n è un numero triangolare, cioè n = 1 + 2 + ... + k , la lunghezza della stringa catturato dal gruppo 1 alla fine sarà k .

Entrambi questi punti sono riportati nel seguente frammento di codice C # ( anche visto sul 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)

---

note aromatiche

Non tutti i sapori supportano i riferimenti annidati. Sempre conoscere te stesso con le stranezze del sapore che si sta lavorando con (e di conseguenza , aiuta quasi sempre a fornire queste informazioni ogni volta che si sta chiedendo domande regex-correlato).

Nella maggior parte dei sapori, i tentativi meccanismo regex corrispondenza standard per vedere se un modello può abbinare qualsiasi parte della stringa di input (eventualmente, ma non necessariamente, l'intero ingresso). Questo significa che si dovrebbero ricordare per ancorare sempre il vostro modello con ^ e $ in caso di necessità.

Java è leggermente diversa in quanto String.matches , Pattern.matches e Matcher.matches tentare di abbinare un modello contro il> tutto il / em> string

Si noti che in altri contesti, potrebbe essere necessario utilizzare \A e \Z ancore, invece. Per esempio, in multilinea modalità , ^ e $ corrispondono all'inizio e alla fine di ogni riga nell'input.

Un ultima cosa è che in .NET regex, è possono effettivamente ottenere tutte le catture intermedi effettuati da un gruppo di cattura ripetuto. Nella maggior parte dei sapori, non è possibile:. Tutte le catture intermedi sono persi e si ottiene solo per mantenere l'ultima

Domande correlate

• (Java) metodo partite non funzionano bene - con esempi su come fare prefisso / suffisso / infisso corrispondenza
• c'è un sapore regex che mi permette di contare il numero di ripetizioni appaiati per * e + (NET!)

---

materiale bonus: Utilizzo di espressioni regolari per trovare il potere di gruppi di due !!!

Con molto leggera modifica, è possibile utilizzare le stesse tecniche presentate qui per trovare il potere di due a due.

Ecco la proprietà matematica di base che si desidera usufruire di:

• 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 soluzione è riportata qui sotto (ma cercare di risolvere da soli prima !!!!)

  

(vedi su ideone.com in PHP , Java e C # ):

     

^{^(\1\1|^.)*.$}