Sử dụng cụm từ thông dụng để so sánh số

Question

Vì vậy, đây là trường hợp hiển nhiên là "bạn đang làm sai". Tôi không thực sự có ý định thực hiện việc này, nhưng cuộc trò chuyện tại nơi làm việc đã làm nảy sinh câu hỏi này:

Bạn có thể tạo cụm từ thông dụng để xác định số nguyên nhỏ hơn giá trị tùy ý hay không.

Đối với một số giá trị, điều này thật dễ dàng. Đối với các số nguyên nhỏ hơn 1000, \ d {1,3} nên thực hiện thủ thuật. Đối với số nguyên < 500, nó phức tạp hơn một chút, nhưng không phải là xấu, vì bạn có thể sử dụng [0-4] {0,1} \ d {1,2}.

Khi bạn nhận được các giá trị tùy ý, nó sẽ nhận được rất nhiều mẹo nhỏ. Ví dụ: tất cả các số nhỏ hơn 255 sẽ giống như \ d {1,2} | [0-1] \ d {2} | [2] [0-4] \ d | [2] [5] [0-4].

Có một cụm từ thông dụng duy nhất hoạt động ở đây không? Hay bạn phải tạo lập trình regex một cách có lập trình?

(Và một lần nữa, hãy để tôi chỉ ra rằng tôi không có ý định thực sự làm điều này. Rõ ràng việc sử dụng "foo < bar" trong ngôn ngữ lập trình yêu thích của bạn được hiệu quả hơn, dễ đọc.)

Answer 1

Bạn' sẽ cần phải tạo biểu thức cho mỗi số giới hạn. Giả sử có một biểu thức chính quy sẽ thực hiện công việc. Sau đó, biểu thức chính quy đó sẽ phải có khả năng lấy đầu vào một số chuỗi ký tự. Tuy nhiên, chúng ta biết rằng các biểu thức chính quy và tự động trạng thái hữu hạn là tương đương, vì vậy điều này cũng giống như nói rằng chúng ta có thể xây dựng một FSM vì số lượng có thể không bị chặn, điều đó đòi hỏi một số trạng thái không bị ràng buộc, mâu thuẫn với định nghĩa của FSA.

Answer 2

Điều này khá dễ dàng.

#!/usr/bin/env perl 
use strict; 
use warnings; 
use Regexp::Assemble; 

for my $n (@ARGV) { 
    my $asm = new Regexp::Assemble; 
    for (1 .. $n) { $asm->add($_) } 
    for ($asm->re){ 
     s/\)$/\$/; 
     s/^[^:]*:/^/; 
     print "$n => /$_/\n"; 
    } 
} 

Bây giờ chạy nó để tìm ra mô hình phù hợp với các số nguyên giữa 1 và con số đó:

$ perl /tmp/ra 5 15 153 401 1144 
5 => /^[12345]$/ 
15 => /^(?:[23456789]|1[]?)$/ 
153 => /^(?:1(?:[6789]|5[0123]?|0\d?|1\d?|2\d?|3\d?|4\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
401 => /^(?:1(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:[123456789]|0[01]?)?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
1144 => /^(?:1(?:0(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|1(?:[56789]|4[]?|0\d?|1\d?|2\d?|3\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|5(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|6(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|7(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|8(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|9(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?)$/