Como esta regex encontra números triangulares?

Parte de uma série de artigos de regex educacionais, esta é uma introdução suave ao conceito de referências aninhadas.

Os primeiros números triangulares são:

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

Existem várias maneiras de verificar se um número é triangular. Existe uma técnica interessante que usa expressões regulares da seguinte maneira:

  • Dado n , primeiro criamos uma string de comprimento n preenchida com o mesmo caractere
  • Em seguida, combinamos essa string com o padrão ^(\1.|^.)+$
    • n é triangular se e somente se esse padrão corresponder à string

Aqui estão alguns trechos para mostrar que isso funciona em vários idiomas:

PHP (em ideone.com)

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

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

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

Então este regex parece funcionar, mas alguém pode explicar como?

Perguntas semelhantes

  • Como determinar se um número é primo com regex?

Explicação

Aqui está uma análise esquemática do padrão:

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

Os colchetes (…) definem o grupo de captura 1 e esse grupo é correspondido repetidamente com + . Esse subpadrão é ancorado com ^ e $ para ver se ele pode corresponder à cadeia inteira.

O grupo 1 tenta corresponder this|that alterna :

  • \1. , ou seja, o grupo 1 correspondido (auto referência!), mais um caractere “qualquer” ,
  • ou ^. , isto é, apenas “qualquer” personagem no começo

Note que no grupo 1, temos uma referência ao que o grupo 1 combinou! Essa é uma referência aninhada / própria e é a ideia principal apresentada neste exemplo. Lembre-se de que, quando um grupo de captura é repetido, geralmente ele apenas mantém a última captura , portanto, a auto-referência, nesse caso, diz essencialmente:

“Tente combinar o que eu combinei da última vez, mais um. Isso é o que eu vou combinar desta vez.”

Semelhante a uma recursion, tem que haver um “caso base” com referências próprias. Na primeira iteração do + , o grupo 1 ainda não havia capturado nada (o que NÃO é o mesmo que dizer que ele começa com uma string vazia). Daí a segunda alternação é introduzida, como uma forma de “inicializar” o grupo 1, que é que é permitido capturar um caractere quando ele está no início da string.

Então, como ele é repetido com + , o grupo 1 primeiro tenta corresponder 1 caractere, depois 2, depois 3, depois 4, etc. A sum desses números é um número triangular.


Mais explorações

Note que, para simplificação, usamos cordas que consistem no mesmo caractere repetitivo de nossa input. Agora que sabemos como esse padrão funciona, podemos ver que esse padrão também pode corresponder a strings como "1121231234" , "aababc" etc.

Note também que se acharmos que n é um número triangular, ie n = 1 + 2 +… + k , o comprimento da string capturada pelo grupo 1 no final será k .

Ambos os pontos são mostrados no seguinte trecho de C # ( também visto em 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

Nem todos os tipos suportam referências aninhadas. Sempre se familiarize com as peculiaridades do sabor com o qual você está trabalhando (e, consequentemente, quase sempre ajuda a fornecer essas informações sempre que você estiver fazendo perguntas relacionadas ao regex).

Na maioria dos sabores, o mecanismo de correspondência regex padrão tenta ver se um padrão pode corresponder a qualquer parte da sequência de input (possivelmente, mas não necessariamente, toda a input). Isso significa que você deve se lembrar de sempre ancorar seu padrão com ^ e $ sempre que necessário.

Java é um pouco diferente em que String.matches , Pattern.matches e Matcher.matches tentam corresponder um padrão a toda a string de input. É por isso que as âncoras podem ser omitidas no trecho acima.

Observe que, em outros contextos, talvez seja necessário usar âncoras \A e \Z Por exemplo, no modo multilinha , ^ e $ correspondem ao início e ao final de cada linha na input.

Uma última coisa é que, no .NET regex, você pode obter todas as capturas intermediárias feitas por um grupo de captura repetido. Na maioria dos sabores, você não pode: todas as capturas intermediárias são perdidas e você só consegue manter a última.

Perguntas relacionadas

  • As correspondências do método (Java) não funcionam bem - com exemplos sobre como fazer correspondência de prefixo / sufixo / infixo
  • Existe um sabor de regex que me permite contar o número de repetições correspondidas por * e + (.NET!)

Material de bônus: Usando regex para encontrar o poder dos dois !!!

Com modificações muito pequenas, você pode usar as mesmas técnicas apresentadas aqui para encontrar o poder dos dois.

Aqui está a propriedade matemática básica da qual você deseja tirar proveito:

  • 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

A solução é dada abaixo (mas tente resolvê-lo você mesmo primeiro !!!!)

(veja em ideone.com em PHP , Java e C # ):

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

Intereting Posts