從數值範圍生成正則表達式

Question

我想從數值範圍生成（一系列）正則表達式。

例子：

1013 - 4044 => 

regexp      matches 
--------------------------------------- 
101[3-9]     1013 - 1019 
10[2-9][0-9]    1020 - 1099 
11[0-9][0-9]    1100 - 1199 
[23][0-9][0-9][0-9]   2000 - 3999 
40[0-3][0-9]    4000 - 4039 
404[0-4]     4040 - 4044 

什麼是最簡單的算法？

反轉它的最簡單方法是什麼（即給定正則表達式，查找範圍）？

會很高興地看到在Java中，Clojure中，perl的解決方案......

謝謝！

Answer 1

有一個online tool給定範圍生成正則表達式，並提供解釋。你也可以在那裏找到源代碼。例如：

^(101[3-9]|10[2-9][0-9]|1[1-9][0-9]{2}|[23][0-9]{3}|40[0-3][0-9]|404[0-4])$ 

 
First, break into equal length ranges: 
    1013 - 4044 

Second, break into ranges that yield simple regexes: 
    1013 - 1019 
    1020 - 1099 
    1100 - 1999 
    2000 - 3999 
    4000 - 4039 
    4040 - 4044 

Turn each range into a regex: 
    101[3-9] 
    10[2-9][0-9] 
    1[1-9][0-9]{2} 
    [23][0-9]{3} 
    40[0-3][0-9] 
    404[0-4] 

Collapse adjacent powers of 10: 
    101[3-9] 
    10[2-9][0-9] 
    1[1-9][0-9]{2} 
    [23][0-9]{3} 
    40[0-3][0-9] 
    404[0-4] 

Combining the regexes above yields: 
    (101[3-9]|10[2-9][0-9]|1[1-9][0-9]{2}|[23][0-9]{3}|40[0-3][0-9]|404[0-4]) 

Next we'll try factoring out common prefixes using a tree: 
Parse into tree based on regex prefixes: 
    . 1 0 1 [3-9] 
     + [2-9] [0-9] 
    + [1-9] [0-9]{2} 
    + [23] [0-9]{3} 
    + 4 0 [0-3] [0-9] 
     + 4 [0-4] 

Turning the parse tree into a regex yields: 
    (1(0(1[3-9]|[2-9][0-9])|[1-9][0-9]{2})|[23][0-9]{3}|40([0-3][0-9]|4[0-4])) 

We choose the shorter one as our result. 

^(101[3-9]|10[2-9][0-9]|1[1-9][0-9]{2}|[23][0-9]{3}|40[0-3][0-9]|404[0-4])$ 

---

扭轉它，你可以看看字符類，並得到各方案的最小值和最大值。

^(101[3-9]|10[2-9][0-9]|1[1-9][0-9]{2}|[23][0-9]{3}|40[0-3][0-9]|404[0-4])$ 
=> 1013  1020   1100   2000  4000   4040  lowers 
     1019   1999  1199   3999   4039  4044 uppers 

=> 1013 - 4044