Convert integer numeric interval to regex

Question

SO,

I'm looking for a solution about the problem - how to convert integer interval to regex. Suppose I have two numbers, A and B. Both of them are positive integers and let be A < B

Now, I'm looking for algorithm (may be code) that will result in a single regex, that will match numbers between A and B (borders included). For example, I have A=20, B=35, then the correct regex is ^2[0-9]$|^3[0-5]$ - since only numbers 20..35 will fit to it.

In common case, when A is something like 83724 and B is something like 28543485 it's not so obvious, however.

upd. Mostly, it is a curiosity matter. I know the best way to do this: return result: A<=X && X<=B

Answer 1

Why use regex in this situation?

I would just do this:

boolean isBetween = num > A && num < B;

(Code written in Java)

Far easier, a regex like what you're asking for could be huge and using it in this situation would be pointless and inefficient.

Good Luck.

If you truly insist on using RegEx for this task, see this website, run the regex with verbose mode on and it will explain to you how the author's RegEx works.

Answer 2

As others have already told you, this is not a very good idea. It will not be faster than just matching all integers and filter them afterwards. But I will answer your question anyway.

Depending on how large the interval is you can let the regex engine optimize it for you, so you just output a |-separated list of values. This can be minimized algorithmically with basic algorithms from finite automata theory.

This may be too memory-intensive for large intervals. In that case you can match all numbers of different lengths from A and B in one go. In your example, all numbers of 6-7 digits are easily matched with [0-9][1-9]{5,6}. Now you have the border cases left, which you can create recursively by (for the A side in this case, I have not included the base case of the recursion):

1. Let S be A.
2. Let f be first digit of S, g=f+1, and n be (digits of S)-1
3. Add a segment to the regex for digits larger than f of: [g-9][0-9]{n}
4. Add a segment for numbers starting with f: f(recursive call starting from step 2, with S=the rest of digits of S)

So for A=123 we would end up with something like (spaces only added for "readability"):

([2-9][0-9]{2}) | (1(([3-9][0-9]{1}) | (2(([4-9]) | 3))) )