Desafio regex

Meu amigo Rogério Zamboim me desafiou a resolver um problema com uma expressão regular. Desconfio que isso estava lhe causando insônia e ele queria transferi-la pra alguém… De qualquer modo, o desafio acabou sendo bem interessante.

O problema é validar um campo cujo conteúdo deve ser uma seqüência de dígitos, de 1 a 8, separados por barras invertidas, em ordem monotônica decrescente. Exemplificando, os seguintes valores são válidos para o campo:

8\7\6\5\4\3\2\1
8
8\1
8\7\2
1
2\1
7\5\3

Já os seguintes valores são inválidos:

8\
\7
8\6\
\2\1
6\\2
7\6\6\2
6\2\5

Confesso que de cara dei um tiro n’água e enviei-lhe a seguinte “solução”, obviamente errada:

   /^[1-8](?:\\[1-7])?(?:\\[1-6])?(?:\\[1-5])?(?:\\[1-4])?(?:\\[1-3])?(?:\\[1-2])?(?:\\1)?$/

O problema é que ela não garante que os dígitos são decrescentes. Por exemplo, a string “4\5” é aceita por ela.

Pensando melhor, ficou claro que expressões regulares “puras” não têm poder de expressão suficiente pra especificar a regra de validação de modo conciso. Isso porque elas não conseguem expressar a ordenação dos dígitos. Não se trata de um impossibilidade teórica, mas prática. Uma solução puramente regular envolveria a descrição explícita de todas as possibilidades, resultando numa expressão enorme. Algo como:

   /^(?:[1-8]|[2-8]\\1|[3-8]\\2|...|[3-8]\\2\\1|[4-8]\\3\\1|.../

Convencido de que não seria possível uma solução direta, resolvi usar uma expressão regular apenas para garantir a forma básica, i.e., uma seqüência de dígitos separados por barras invertidas, e deixar a verificação da ordem para um código posterior. O melhor que consegui foi o seguinte:

   sub validate_loop {
       my ($string) = @_;
       my $top = 9;
       for my $val (split /\\/, $string) {
           return 0 unless $val =~ /^[1-8]$/;
           return 0 unless $top > $val;
           $top = $val;
       }
       return 1;
   }

Esta função recebe uma string com o valor do campo. A variável $top contém sempre o valor máximo que o próximo dígito pode conter mais um, e começa com 9, já que o primeiro dígito pode estar entre 1 e 8. O loop quebra a string nas barras invertidas e verifica se o que há entre elas são dígitos entre 1 e 8 e se eles são menores que $top, atribuindo a $top o valor do próximo dígito.

É razoável, mas não satisfatório. Usa duas expressões regulares e faz muitos testes separados… Não estava muito bom.

Fiquei matutando uns dois dias sobre isso e pensando se dentre as várias extensões que Perl oferece além dos operadores básicos de expressões regulares não haveria algum que me permitisse construir uma solução mais sucinta. Relendo a documentação deparei-me com o operador “(?{code})“, que permite inserir código no meio de uma expressão regular. Hmmm… parecia útil, mas eu nunca havia usado algo assim.

Depois de algumas tentativas frustradas acabei bolando a seguinte solução:

   sub validate_re {
       my ($string) = @_;
       our ($dec, $last) = (1);
       return ($string =~ /^([1-8])(?{$last=$^N})(?:\\([1-8])(?{$dec=0 if $last <= $^N; $last=$^N}))*$/) && $dec;
   }

A expressão regular ficou maior por causa do código embutido dentro dela. Remova mentalmente os operadores (?{…}) e você verá que ela está simplesmente verificando se a string consiste em uma sequência de dígitos separados por barras invertidas.

No primeiro operador de código, a variável $last recebe o valor do primeiro dígito da string. (A variável implícita $^N lembra o valor da última captura por parêntesis.) No segundo operador, usamos seu valor para verificar se o próximo dígito é menor que o anterior e atribuímos o novo dígito a ela.

A variável $dec mantém o estado da verificação de ordem. Ela começa como 1 e recebe 0 caso o segundo operador de código detecte que há algum dígito fora de ordem monotônica decrescente.

Eu demorei um bom tempo pra chegar à conclusão de que essas duas variáveis tinham que ser globais (declaradas com “our”). Se elas são locais (declaradas com “my”) não funciona. A documentação não é clara a esse respeito e eu desconfio que seja um bug do próprio interpretador Perl, mas não tenho certeza.

A função acaba retornando a conjunção da avaliação da expressão regular com o valor final de $dec.

Pronto, agora eu posso dormir em paz.

4 respostas para Desafio regex

  1. Anonymous disse:

    Tem uma expressão "pequena" que resolve o problema: ^(?=[8-1])(?:8)?(?:\\?7)?(?:\\?6)?(?:\\?5)?(?:\\?4)?(?:\\?3)?(?:\\?2)?(?:\\?1)?$

  2. Gnustavo disse:

    @Anônimo: gostei do truque de usar uma "zero-width positive look-ahead assertion" pra forçar um dígito inicial. (Só que a classe de dígitos deve ser [1-8] ao invés de [8-1].)Infelizmente, isso não resolve todo o problema. Sua expressão aceita qualquer sequêcia monotônica decrescente de dígitos não separados por barras. Por exemplo, ela aceita a string "87654321", que não é válida.

  3. Alexandre disse:

    Olá!Comecei a estudar regex há poucas semanas. Resolvi dar um google "desafio regex" pra testar meu aprendizado e me deparei com seu problema. Eis minha solução:^8?(((?<=[8])(\\7)?)|^7?)(((?<=[7-8])(\\6)?)|^6?)(((?<=[6-8])(\\5)?)|^5?)(((?<=[5-8])(\\4)?)|^4?)(((?<=[4-8])(\\3)?)|^3?)(((?<=[3-8])(\\2)?)|^2?)(((?<=[2-8])(\\1)?)|^1?)$:)

  4. Gnustavo disse:

    @Alexandre: Muito bom! Eu acreditava que qualquer solução "não interativa" como a minha teria que ser necessariamente gigante. Mas a sua é sucinta e muito elegante. Até onde eu consegui enxergar, a única diferença é que a sua admite a string vazia e a minha não. Mas como isso não estava especificado no problema, considero a sua solução correta e mais interessante do que a minha. Parabéns!

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: