Регулярное выражение в алфавитном порядке с использованием обратных ссылок

Недавно я наткнулся на головоломку, чтобы найти регулярное выражение, которое соответствует:

5-символьные строки, состоящие из строчных букв английского алфавита в порядке возрастания ASCII

Допустимые примеры:

aaaaa
abcde
xxyyz
ghost
chips
demos

Неверные примеры включают в себя:

abCde
xxyyzz
hgost
chps

Мое текущее решение клудги. Я использую регулярное выражение:

(?=^[a-z]{5}$)^(a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*)$

который использует непотребляющую группу захвата для утверждения длины строки 5, а затем проверяет, что строка состоит из строчных букв английского алфавита по порядку ( см. Rubular).

Вместо этого я хотел бы использовать обратные ссылки внутри классов символов. Что-то вроде:

^([a-z])([\1-z])([\2-z])([\3-z])([\4-z])$

Логика решения ( см. Rubular) в моей голове состоит в том, чтобы захватить первый символ [az], использовать его как обратную ссылку во втором классе символов и так далее. Тем не мение, \1, \2... внутри классов символов, кажется, ссылаются на значения ASCII 1, 2... эффективно совпадающие с любой строкой из четырех или пяти символов.

У меня есть 2 вопроса:

  1. Могу ли я использовать обратные ссылки в моих классах символов для проверки строк в порядке возрастания?
  2. Есть ли какое-нибудь менее удачное решение этой головоломки?
Источник

4 ответа

Решение

Я публикую этот ответ скорее как комментарий, чем как ответ, так как он имеет лучшее форматирование, чем комментарии.

Связанные с вашими вопросами:

  1. Могу ли я использовать обратные ссылки в моих классах символов для проверки строк в порядке возрастания?

Нет, ты не можешь. Если вы посмотрите раздел регулярных выражений backref, вы найдете ниже документацию:

Скобки и обратные ссылки не могут использоваться внутри классов символов

Скобки нельзя использовать внутри классов символов, по крайней мере, в качестве метасимволов. Когда вы помещаете круглые скобки в класс символов, они обрабатываются как буквенные символы. Таким образом, регулярное выражение [(a)b] соответствует a, b, (, и).

Обратные ссылки также нельзя использовать внутри класса символов. \1 в регулярном выражении типа (a)[\1b] является либо ошибкой, либо бесполезно экранированным литералом 1. В JavaScript это восьмеричный побег.

По поводу вашего второго вопроса:

  1. Есть ли какое-нибудь менее удачное решение этой головоломки?

Имхо, ваше регулярное выражение прекрасно, вы могли бы сократить его очень немного в начале, как это:

(?=^.{5}$)^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$
    ^--- Here

Regex demo

Источник

Если вы хотите использовать Perl (!), Это будет работать:

/^([a-z])((??{"[$1-z]"}))((??{"[$2-z]"}))((??{"[$3-z]"}))(??{"[$4-z]"})$/
Источник

Так как кто-то сломал лед с помощью Perl, это
Perl решение, я думаю..

Обратите внимание, что это базовое решение без регулярных выражений,
вставлены в конструкции кода внутри регулярного выражения Perl.
Интересно, что если придет день, когда вам понадобится синергия
регулярного выражения / кода это хороший выбор.
Возможно тогда, что вместо простого [a-z] характер, вы можете
используйте очень сложный паттерн на своем месте и используйте чек против последнего.
Это сила!!

Регулярное выражение ^(?:([a-z])(?(?{ $last gt $1 })(?!)|(?{ $last = $1 }))){5}$

Код Perl

use strict;
use warnings;


$/ = "";

my @DAry = split /\s+/, <DATA>;

my $last;

for (@DAry)
{
    $last = '';
    if ( 
      /
         ^                             # BOS
         (?:                           # Cluster begin
              ( [a-z] )                     # (1), Single a-z letter
                                            # Code conditional
              (?(?{
                   $last gt $1                  # last > current ?
                })
                   (?!)                          # Fail
                |                              # else,
                   (?{ $last = $1 })             # Assign last = current
              )
         ){5}                          # Cluster end, do 5 times
         $                             # EOS
      /x )
    {
        print "good   $_\n";
    }
    else {
        print "bad    $_\n";
    }
}

__DATA__

aaaaa
abcde
xxyyz
ghost
chips
demos
abCde
xxyyzz
hgost
chps

Выход

good   aaaaa
good   abcde
good   xxyyz
good   ghost
good   chips
good   demos
bad    abCde
bad    xxyyzz
bad    hgost
bad    chps
Источник

Ах, ну, это конечный набор, так что вы всегда можете перечислить его с чередованием! Это выдает регулярное выражение "грубой силы" в небольшом perl REPL:

#include <stdio.h>

int main(void) {
  printf("while (<>) { if (/^(?:");
  for (int a = 'a'; a <= 'z'; ++a)
    for (int b = a; b <= 'z'; ++b)
      for (int c = b; c <= 'z'; ++c) {
        for (int d = c; d <= 'y'; ++d)
          printf("%c%c%c%c[%c-z]|", a, b, c, d, d);
        printf("%c%c%czz", a, b, c);
        if (a != 'z' || b != 'z' || c != 'z') printf("|\n");
      }
  printf(")$/x) { print \"Match!\\n\" } else { print \"No match.\\n\" }}\n");
  return 0;
}

И сейчас:

$ gcc r.c
$ ./a.out > foo.pl
$ cat > data.txt
aaaaa
abcde
xxyyz
ghost
chips
demos
abCde
xxyyzz
hgost
chps
^D
$ perl foo.pl < data.txt
Match!
Match!
Match!
Match!
Match!
Match!
No match.
No match.
No match.
No match.

Регулярное выражение всего 220Kb или около того;-)

Источник
Другие вопросы по тегам