Como podemos combinar um^n b^n com Java regex?

Em vez de dar imediatamente o padrão, esta resposta guiará os leitores através do processo de derivá-lo. Várias dicas são dadas como a solução é construída lentamente. Neste aspecto, espero que esta resposta conter muito mais do que apenas outro padrão regular puro. Esperemos que os leitores também aprendam a" pensar em regex", e como colocar várias construções harmoniosamente juntos, para que eles possam derivar mais padrões por conta própria no futuro.

A linguagem usada para desenvolver a solução será PHP para a sua concisão. O teste final uma vez que o padrão está finalizado será feito em Java.

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}

$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');

$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

A saída é (conforme visto em ideone.com):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

lição: você pode usar padrões em lookarounds para fazer afirmações.

Passo 2: capturar num lookahead (E F R e E - S P A C i n g mode)

Com base no nosso excerto anterior do PHP, temos agora o seguinte padrão:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead

testAll($r2, $tests);

A saída é agora (como visto em ideone.com):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Note que por exemplo aaa|b é o resultado de join-ing o que cada grupo capturou com '|'. Neste caso, o grupo 0 (ou seja, o que corresponde ao padrão) capturou aaa, e o grupo 1 capturou b.

Lição: Você pode capturar dentro de um lookaround. Você pode usar o espaço livre para melhorar a legibilidade.

Passo 3: Refactorar o lookahead no "loop"

• primeiro refactor a+ a (?: a )+ (note que (?:…) é um grupo que não captura)
• depois mova a cabeça de leitura para dentro deste grupo de não-captura
  Note que agora temos de "saltar" antes de podermos "see" the b+, so modify the pattern accordingly

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

A saída é a mesma que antes (vista em ideone.com então, não há mudança nesse aspecto. O importante é que agora estamos fazendo a afirmação em todas as iterações do "loop". Com o nosso padrão atual, isso não é necessário, mas em seguida vamos fazer o grupo 1 "contar" para nós usando auto-referência.

lição: você pode capturar dentro de um grupo de não-captura. Os olhares podem ser repetidos.

Passo 4: Este é o passo em que começamos a contar

• no final da primeira iteração do +, quando o primeiro a é combinado, ele deve capturar b
• no final da segunda iteração, quando outro a é combinado, deve capturar bb
No final da terceira iteração, deve capturar bbb
• ...
• no final daN -é a iteração, o grupo 1 deve capturar B ⁿ
• se não há o suficiente b para capturar no grupo 1 então a afirmação simplesmente falha

Há um pequeno problema aqui em que este padrão está faltando o "caso base", ou seja, o caso onde ele pode corresponder sem a auto-referência. Um caso de base é necessário porque o grupo 1 começa "não-iniciado"; ele ainda não capturou nada (nem mesmo uma cadeia vazia), então uma tentativa de auto-referência sempre falhará.

Há muitas maneiras de contornar isto, mas por agora vamos apenas fazer a correspondência de auto-referência {[[216]}opcional , ou seja, \1?. Isto pode ou não funcionar perfeitamente, mas vamos ver o que isso faz, e se houver algum problema, então atravessaremos essa ponte quando chegarmos a ela. Além disso, vamos adicionar mais alguns casos de teste.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);

$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

A saída é agora (como visto em ideone.com):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

lição: uma maneira de" inicializar " um grupo de auto-referenciamento é fazer a correspondência de auto-referência opcional.

O problema é que como fizemos a correspondência de auto-referência opcional, o "contador" pode "reiniciar" de volta a 0 quando não há suficientes b ' S. examine o que acontece em cada iteração do nosso padrão com aaaaabbb como entrada.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

lição: Cuidado com o retrocesso. O motor regex fará tanto retrocesso quanto você permitir até que o padrão indicado corresponda. Isto pode ter impacto no desempenho (isto é, [245]}catastrófico backtracking ) e / ou correcção.

A" correcção " deve agora ser óbvia: combinar repetição opcional com possessivo quantificador. Isto é, em vez de simplesmente ?, use ?+ em vez disso (lembre-se que uma repetição que é quantificada como possessiva não recua, mesmo que tal "cooperação" possa resultar em uma correspondência do padrão geral).

?+

• (opcional) " não tem de estar lá,"
  (Possessivo) " mas se ele está lá, você deve pegá-lo e não deixá-lo ir!"

?

• (opcional) " não tem de estar lá,"
  Mas se for você pode tomá-lo por agora,
  • "mas você pode ser pedido para deixá-lo ir mais tarde!"

??

• (opcional) " não tem de estar lá,"
  "E mesmo que seja, ainda não tens de aceitar,"
  • (retroceder) "mas você pode ser convidado a tomá-lo mais tarde!"

Em nossa configuração, \1 não vai estar lá a primeira vez, mas vai sempre estar lá a qualquer momento depois disso, e nós sempre quero então bate. Assim, \1?+ realizaria exatamente o que queremos.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Agora a saída é (como visto em ideone.com):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

lição: Aprenda a diferença entre a repetição gananciosa, relutante e possessiva. Opcional-possessivo pode ser uma combinação poderosa.

Para terminar o trabalho, precisamos simplesmente de adicionar ao nosso padrão \1 $. Esta é agora uma referência traseira ao que o grupo 1 correspondeu, seguido pelo fim da âncora da linha. A âncora garante que ali não há nenhum extra b na corda; em outras palavras, que de fato temos a ⁿ B ⁿ.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);

$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Passo 7: O teste Java

public static void main(String[] args) {

        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }

}

static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

O padrão funciona como esperado ( visto em ideone.com).

É preciso dizer que o a* no lookahead, e na verdade o "laço principal +", ambos permitem retroceder. Os leitores são encorajados a confirmar por que isso não é um problema em termos de correção, e por que, ao mesmo tempo, tornar ambos possessivos também funcionaria (embora a mistura de quantificadores possessivos obrigatórios e não obrigatórios no mesmo padrão possa levar a equívocos).

Também deve ser dito que, embora seja legal que haja um padrão regex que irá corresponder a ⁿ b ⁿ, esta nem sempre é a melhor solução na prática. Uma solução muito melhor é simplesmente combinar ^(a+)(b+)$, e então comparar o comprimento das cadeias capturadas pelos grupos 1 e 2 na linguagem de programação de hospedagem.

Em PHP, pode ser parecido com isto ( visto em ideone.com):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

O objectivo deste artigo é não convencer os leitores de que a regex pode fazer quase tudo; claramente não pode, e mesmo para as coisas que pode fazer, pelo menos uma delegação parcial na língua de acolhimento deve ser considerada se conduzir a uma solução mais simples.

Como mencionado no topo, embora este artigo seja necessariamente marcado [regex] para stackoverflow, é talvez sobre mais de que. Embora certamente haja valor em aprender sobre asserções, referências aninhadas, quantificador possessivo, etc, talvez a lição maior aqui é o processo criativo pelo qual se pode tentar resolver problemas, a determinação e o trabalho duro que muitas vezes requer quando você está sujeito a várias restrições, a composição sistemática de várias partes para construir uma solução de trabalho, etc.

Material de bónus! Padrão recursivo PCRE!

$rRecursive = '/ ^ (a (?1)? b) $ /x';

Actualmente a expressão regular do Java não suporta o padrão recursivo.

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $