сопоставление конечных рядов натуральных чисел

Question

Как мне сопоставить конечное натуральное число серии с регулярным выражением?

Итак, требования:

• строка содержит числа и пробелы (в качестве разделителей)
• первое число равно 1
• каждое число (кроме первого) равно предыдущему числу + 1

Должно совпадать :

• 1
• 1 2
• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
• длинные серии последовательных чисел от 1 до 10 ^1000

Не должно совпадать :

• ``
• 1 3 4
• 1 2 3 4 5 6 6

Помимо некоторых требований к регулярному выражению:

• это должно быть одноразовое выражение, а не пакет инструкций алгоритма условия цикла
• он мог бы использовать всю мощь perl регулярных выражений

Я не уверен, что регулярные выражения на самом деле ленивы, поэтому было бы здорово, если бы они были.Потому что ряд натуральных чисел не конечен в своем первоначальном значении из теории чисел.

И последний.Обратите внимание, что я не использую не тот инструмент для этой работы.Это не настоящая задача программирования вообще.

Answer 1

Вот, пожалуйста.Протестировано на Perl v5.10 до v5.14.Ключом является рекурсивный шаблон , где мы применяем правило (?&Sequence).Это что-то вроде доказательства по индукции.

bigint есть на тот случай, если вы действительно хотите сгенерировать последовательность из 1 .. 10**10_000.Он будет работать значительно быстрее, если вы сможете ограничиться собственными машинными целочисленными значениями, 32-разрядными или 64-разрядными, в зависимости от вашей платформы.

#!/usr/bin/env perl
use v5.10;
use bigint;  # only if you need stuff over maxint

my $pat = qr{
    ^
    (?= 1 \b )
    (?<Sequence>
        (?<Number> \d+ )
        (?:
            \s+
            (??{  "(?=" . (1 + $+{Number}) . ")" })
            (?&Sequence)
        )?
    )
    $
}x;

# first test embedded data
while (<DATA>) {
    if ( /$pat/ ) {
        print "PASS: ", $_;

    } else {
        print "FAIL: ", $_;
    }
}

# now generate long sequences
for my $big ( 2, 10, 25, 100, 1000, 10_000, 100_000 ) {
    my $str = q();
    for (my $i = 1; $i <= $big; $i++) {
        $str .= "$i ";
    }
    chop $str;
    if ($str =~ $pat) {
        print "PASS: ";
    } else {
        print "FAIL: ";
    }
    if (length($str) > 60) {
        my $len = length($str);
        my $first = substr($str,   0, 10);
        my $last  = substr($str, -10);
        $str = $first . "[$len chars]" . $last;
    }
    say $str;

}


__END__
5
fred
1
1 2 3
1 3 2
1 2 3 4 5
1 2 3 4 6
2 3 4 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 6

В результате выполнения:

FAIL: 5
FAIL: fred
PASS: 1
PASS: 1 2 3
FAIL: 1 3 2
PASS: 1 2 3 4 5
FAIL: 1 2 3 4 6
FAIL: 2 3 4 6
PASS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
FAIL: 1 2 3 4 5 6 6
PASS: 1 2
PASS: 1 2 3 4 5 6 7 8 9 10
PASS: 1 2 3 4 5 [65 chars]2 23 24 25
PASS: 1 2 3 4 5 [291 chars] 98 99 100
PASS: 1 2 3 4 5 [3892 chars]8 999 1000
PASS: 1 2 3 4 5 [588894 chars]999 100000

Atриск казаться корыстным, есть книга , которая покрывает подобные вещи.См. Раздел «Необычные шаблоны» в главе 5 Программирование на Perl , издание 4ᵗʰ.Вы захотите проверить новые разделы «Именованные группы», «Рекурсивные паттерны» и «Грамматические паттерны».Книга находится в типографии и должна быть доступна в электронном виде через день или два.

Answer 2

Попробуйте следующее регулярное выражение (в perl):

m/\A((??{ our $i += 1 })(?>\s*))+\Z/

---

Тест

Содержимое script.pl:

use warnings;
use strict;

while ( <DATA> ) { 
    chomp;
    our $i = 0;
    printf qq[%s\n], $_ if m/\A((??{ our $i += 1 })(?>\s*))+\Z/;
}

__DATA__
0
2
1
1 3 4
1 2
1 2 3 4 5 6 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
2 1
1 2 3 4 5 7
1           2            3    

Запустить скрипт:

perl script.pl

И результат:

1
1 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1           2            3 

Answer 3

Я не думаю, что существует возможный шаблон для выполнения ваших требований, потому что регулярные выражения в основном совпадают по тексту;при сопоставлении

вычисление не выполняется, однако вы можете создать свой собственный автомат, который выполняет вычисления, или просто выполнить итерации по числам, что должно быть намного эффективнее