Генератор регулярных выражений для числовых диапазонов

Ответ 1

Здесь мое решение и алгоритм со сложностью O(log n) (n - конец диапазона). Я считаю, что это самый простой из них:

В принципе, разделите свою задачу на следующие шаги:

• Постепенно "ослаблять" start диапазона.
• Постепенно "ослабить" диапазон end.
• Объединить эти два.

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

145 -> 149,150 -> 199,200 -> 999,1000 -> etc.

Здесь обратный, для end диапазона:

387 -> 380,379 -> 300,299 -> 0

Слияние было бы процессом замещения перекрытия 299- > 0 и 200- > 999 и объединения их в 200- > 299.

В результате вы получите этот набор чисел (первый список неповрежден, второй инвертирован:

145, 149, 150, 199, 200, 299, 300, 379, 380, 387

Теперь, вот забавная часть. Возьмите числа парами и преобразуйте их в диапазоны:

145-149, 150-199, 200-299, 300-379, 380-387

Или в регулярном выражении:

14[5-9], 1[5-9][0-9], 2[0-9][0-9], 3[0-7][0-9], 38[0-7]

Вот как выглядит код для weakening:

public static int next(int num) {
    //Convert to String for easier operations
    final char[] chars = String.valueOf(num).toCharArray();
    //Go through all digits backwards
    for (int i=chars.length-1; i>=0;i--) {
        //Skip the 0 changing it to 9. For example, for 190->199
        if (chars[i]=='0') {
            chars[i] = '9';
        } else { //If any other digit is encountered, change that to 9, for example, 195->199, or with both rules: 150->199
            chars[i] = '9';
            break;
        }
    }

    return Integer.parseInt(String.valueOf(chars));
}

//Same thing, but reversed. 387 -> 380, 379 -> 300, etc
public static int prev(int num) {
    final char[] chars = String.valueOf(num).toCharArray();
    for (int i=chars.length-1; i>=0;i--) {
        if (chars[i] == '9') {
            chars[i] = '0';
        } else {
            chars[i] = '0';
            break;
        }
    }

    return Integer.parseInt(String.valueOf(chars));
}

Остальные технические детали и их легко реализовать. Здесь реализация этого алгоритма O(log n): https://ideone.com/3SCvZf

О, и, кстати, он работает и с другими диапазонами, например, для диапазона 1-321654 результат:

[1-9]
[1-9][0-9]
[1-9][0-9][0-9]
[1-9][0-9][0-9][0-9]
[1-9][0-9][0-9][0-9][0-9]
[1-2][0-9][0-9][0-9][0-9][0-9]
3[0-1][0-9][0-9][0-9][0-9]
320[0-9][0-9][0-9]
321[0-5][0-9][0-9]
3216[0-4][0-9]
32165[0-4]

И для 129-131 это:

129
13[0-1]

Ответ 2

Наконец я пришел к следующему. Общая идея состоит в том, чтобы начать с начала диапазона, создать регулярное выражение, которое будет соответствовать от этого до, но не включая следующий кратный 10, затем для сотен и т.д., Пока вы не сравните вещи до конца ассортимент; затем начинайте с конца диапазона и работайте вниз, заменяя увеличивающееся число цифр на 0, чтобы соответствовать аналогичному числу 9s, чтобы соответствовать конкретному концу диапазона. Затем создайте одно регулярное выражение для части диапазона, если они еще не покрывают все это.

Особое внимание следует обратить на процедуру bezmax, чтобы преобразовать два числа в регулярное выражение, которое будет соответствовать им. MUCH проще, чем напрямую обращаться со строками или массивами символов.

В любом случае, вот оно:

package numbers;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * Has methods for generating regular expressions to match ranges of numbers.
 */
public class RangeRegexGenerator
{
  public static void main(String[] args)
  {
    RangeRegexGenerator rrg = new RangeRegexGenerator();

//    do
//    {
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("enter start, <return>, then end and <return>");
//      int start = scanner.nextInt();
//      int end = scanner.nextInt();
//      System.out.println(String.format("for %d-%d", start, end));

      List<String> regexes = rrg.getRegex("0015", "0213");
      for (String s: regexes) { System.out.println(s); }
//    } 
//    while(true);
  }

  /**
   * Return a list of regular expressions that match the numbers
   * that fall within the range of the given numbers, inclusive.
   * Assumes the given strings are numbers of the the same length,
   * and 0-left-pads the resulting expressions, if necessary, to the
   * same length. 
   * @param begStr
   * @param endStr
   * @return
   */
  public List<String> getRegex(String begStr, String endStr)
  {
      int start = Integer.parseInt(begStr);
      int end   = Integer.parseInt(endStr);
      int stringLength = begStr.length();
      List<Integer> pairs = getRegexPairs(start, end);
      List<String> regexes = toRegex(pairs, stringLength);
      return regexes;
  }

  /**
   * Return a list of regular expressions that match the numbers
   * that fall within the range of the given numbers, inclusive.
   * @param beg
   * @param end
   * @return
   */
  public List<String> getRegex(int beg, int end)
  {
    List<Integer> pairs = getRegexPairs(beg, end);
    List<String> regexes = toRegex(pairs);
    return regexes;
  }

  /**
   * return the list of integers that are the paired integers
   * used to generate the regular expressions for the given
   * range. Each pair of integers in the list -- 0,1, then 2,3,
   * etc., represents a range for which a single regular expression
   * is generated.
   * @param start
   * @param end
   * @return
   */
  private List<Integer> getRegexPairs(int start, int end)
  {
      List<Integer> pairs = new ArrayList<>();

      ArrayList<Integer> leftPairs = new ArrayList<>();
      int middleStartPoint = fillLeftPairs(leftPairs, start, end);
      ArrayList<Integer> rightPairs = new ArrayList<>();
      int middleEndPoint = fillRightPairs(rightPairs, middleStartPoint, end);

      pairs.addAll(leftPairs);
      if (middleEndPoint > middleStartPoint)
      {
        pairs.add(middleStartPoint);
        pairs.add(middleEndPoint);
      }
      pairs.addAll(rightPairs);
      return pairs;
  }

  /**
   * print the given list of integer pairs - used for debugging.
   * @param list
   */
  @SuppressWarnings("unused")
  private void printPairList(List<Integer> list)
  {
    if (list.size() > 0)
    {
      System.out.print(String.format("%d-%d", list.get(0), list.get(1)));
      int i = 2;
      while (i < list.size())
      {
        System.out.print(String.format(", %d-%d", list.get(i), list.get(i + 1)));
        i = i + 2;
      }
      System.out.println();
    }
  }

  /**
   * return the regular expressions that match the ranges in the given
   * list of integers. The list is in the form firstRangeStart, firstRangeEnd, 
   * secondRangeStart, secondRangeEnd, etc.
   * @param pairs
   * @return
   */
  private List<String> toRegex(List<Integer> pairs)
  {
    return toRegex(pairs, 0);
  }

  /**
   * return the regular expressions that match the ranges in the given
   * list of integers. The list is in the form firstRangeStart, firstRangeEnd, 
   * secondRangeStart, secondRangeEnd, etc. Each regular expression is 0-left-padded,
   * if necessary, to match strings of the given width.
   * @param pairs
   * @param minWidth
   * @return
   */
  private List<String> toRegex(List<Integer> pairs, int minWidth)
  {
    List<String> list = new ArrayList<>();
    String numberWithWidth = String.format("%%0%dd", minWidth);
    for (Iterator<Integer> iterator = pairs.iterator(); iterator.hasNext();)
    {
      String start = String.format(numberWithWidth, iterator.next()); // String.valueOf(iterator.next());
      String end = String.format(numberWithWidth, iterator.next());

      list.add(toRegex(start, end));
    }
    return list;
  }

  /**
   * return a regular expression string that matches the range
   * with the given start and end strings.
   * @param start
   * @param end
   * @return
   */
  private String toRegex(String start, String end)
  {
    assert start.length() == end.length();

    StringBuilder result = new StringBuilder();

    for (int pos = 0; pos < start.length(); pos++)
    {
      if (start.charAt(pos) == end.charAt(pos))
      {
        result.append(start.charAt(pos));
      } else
      {
        result.append('[').append(start.charAt(pos)).append('-')
            .append(end.charAt(pos)).append(']');
      }
    }
    return result.toString();
  }

  /**
   * Return the integer at the end of the range that is not covered
   * by any pairs added to the list.
   * @param rightPairs
   * @param start
   * @param end
   * @return
   */
  private int fillRightPairs(List<Integer> rightPairs, int start, int end)
  {
    int firstBeginRange = end;    // the end of the range not covered by pairs
                                  // from this routine.
    int y = end;
    int x = getPreviousBeginRange(y);

    while (x >= start)
    {
      rightPairs.add(y);
      rightPairs.add(x);
      y = x - 1;
      firstBeginRange = y;
      x = getPreviousBeginRange(y);
    }
    Collections.reverse(rightPairs);
    return firstBeginRange;
  }

  /**
   * Return the integer at the start of the range that is not covered
   * by any pairs added to its list. 
   * @param leftInts
   * @param start
   * @param end
   * @return
   */
  private int fillLeftPairs(ArrayList<Integer> leftInts, int start, int end)
  {
    int x = start;
    int y = getNextLeftEndRange(x);

    while (y < end)
    {
      leftInts.add(x);
      leftInts.add(y);
      x = y + 1;
      y = getNextLeftEndRange(x);
    }
    return x;
  }

  /**
   * given a number, return the number altered such
   * that any 9s at the end of the number remain, and
   * one more 9 replaces the number before the other
   * 9s.
   * @param num
   * @return
   */
  private int getNextLeftEndRange(int num)
  {
    char[] chars = String.valueOf(num).toCharArray();
    for (int i = chars.length - 1; i >= 0; i--)
    {
      if (chars[i] == '0')
      {
        chars[i] = '9';
      } else
      {
        chars[i] = '9';
        break;
      }
    }

    return Integer.parseInt(String.valueOf(chars));
  }

  /**
   * given a number, return the number altered such that
   * any 9 at the end of the number is replaced by a 0,
   * and the number preceding any 9s is also replaced by
   * a 0.
   * @param num
   * @return
   */
  private int getPreviousBeginRange(int num)
  {
    char[] chars = String.valueOf(num).toCharArray();
    for (int i = chars.length - 1; i >= 0; i--)
    {
      if (chars[i] == '9')
      {
        chars[i] = '0';
      } else
      {
        chars[i] = '0';
        break;
      }
    }

    return Integer.parseInt(String.valueOf(chars));
  }
}

Это правильно, насколько я смог проверить его; тот, который был отправлен bezmax, не совсем сработал, хотя у него была правильная идея (что я также придумал) для общего алгоритма, а также большая деталь реализации или две, которые были полезны, поэтому я оставляю галочку "ответ" на его ответ.

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

Ответ 3

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

• от начала до следующего кратного 10 (если старт уже не кратен 10)
• от последнего кратного 10 до конца (если конец уже не кратен 10)
• диапазон между этими двумя кратными 10 может быть обработан рекурсией, сняв последнюю цифру и добавив регулярное выражение [0-9] ко всем сгенерированным регулярным выражениям впоследствии

В приведенном ниже коде даже оптимизируются диапазоны одиночных значений, например [1-1] - 1. Функция вызова - genRangeRegex (start is inclusive, end is exclusive):

def regexRangeDigits(start,stop):
  if start == stop:
    return str(start)
  return '[%d-%d]' % (start,stop)

# generate list of regular expressions for the number range [start,end[
def genRangeRegex(start, end):
  if start <= 0:
    raise ValueError('only ranges of positive numbers supported')

  print 'getting regex list for range [%d,%d[' % (start,end)
  if start >= end:
    return []

  digitsStart = str(start)
  digitsEnd   = str(end)
  lastDigitStart = start%10

  if start//10 == (end-1)//10: # integer division
    lastDigitStop = (end-1)%10
    regexAll = digitsStart[:-1] + regexRangeDigits(lastDigitStart,lastDigitStop)
    print '  regexAll   = %s' % regexAll
    return [regexAll]

  regexListStart = [] # at most one regular expression for going up to first multiple of 10
  if lastDigitStart != 0:
    regexStart = digitsStart[:-1] + regexRangeDigits(lastDigitStart,9)
    print '  regexStart = %s' % regexStart
    regexListStart.append(regexStart)

  regexListEnd = [] # at most one regular expression for going up from last multiple of 10
  lastDigitEnd = end%10
  if lastDigitEnd != 0:
    regexEnd = digitsEnd[:-1] + regexRangeDigits(0,lastDigitEnd-1)
    print '  regexEnd   = %s' % regexEnd
    regexListEnd.append(regexEnd)

  regexListMidTrunc = genRangeRegex((start+9)//10, end//10)
  regexListMid = [r+'[0-9]' for r in regexListMidTrunc]

  return regexListStart + regexListMid + regexListEnd

И вот пример: как работает функция:

>>> genRangeRegex(12,231)
getting regex list for range [12,231[
  regexStart = 1[2-9]
  regexEnd   = 230
getting regex list for range [2,23[
  regexStart = [2-9]
  regexEnd   = 2[0-2]
getting regex list for range [1,2[
  regexAll   = 1
['1[2-9]', '[2-9][0-9]', '1[0-9][0-9]', '2[0-2][0-9]', '230']

Ответ 4

Вы не можете покрыть свое требование только группами символов. Представьте диапазон 129-131. Шаблон 1[2-3][1-9] также будет соответствовать 139, который находится за пределами допустимого диапазона.

Итак, в этом примере вам нужно изменить последнюю группу на что-то еще: 1[2-3](1|9). Теперь вы можете найти этот эффект также для десятков и hundrets, что приводит к проблеме, что aapattern, который в основном представляет каждое действительное число как фиксированную последовательность чисел, является единственным рабочим решением. (если вам не нужен алгоритм, который должен отслеживать переполнение, чтобы решить, следует ли использовать [2-8] или (8,9,0,1,2))

если вы все равно создадите шаблон - сохраните его просто:

128-132

может быть записана как (я оставил дополнение группы без соответствия ?: для лучшей читаемости)

(128|129|130|131|132)

должен быть ovious, a, массивом, конкатенацией строк и объединением.

Это будет работать так, как ожидалось, но вы также можете выполнить некоторую "оптимизацию" на этом, если вам нравится более компактный:

(128|129|130|131|132) <=>
1(28|29|30|31|32) <=>
1(2(8|9)|3(0|1|2))

больше оптимизации

1(2([8-9])|3([0-2]))

Алгоритмы для последних шагов находятся там, ищите факторизацию. Простым способом было бы толкать все числа на дерево, в зависимости от положения символа:

1
  2
    8
    9
  3
    0
    1
    2

и, наконец, итерации по трем и сформировать шаблон 1(2(8|9)|3(0|1|2)). В качестве последнего шага замените что-либо из шаблона (a|(b|)*?c) на [a-c]

То же самое для 11-29:

11-29 <=>
(11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29) <=>   
(1(1|2|3|4|5|7|8|9)|2(1|2|3|4|5|7|8|9)) <=>
(1([1-9])|2([1-9]) 

в качестве дополнения вы можете продолжить факторизацию:

(1([1-9])|2([1-9]) <=>
(1|2)[1-9] <=>
[1-2][1-9]

Ответ 5

[Подсказка: как-то идея применения рекурсии, представленная в моем первом ответе (с использованием Python), не дошла до OP, так что вот она снова в Java. Заметим, что для рекурсивного решения часто бывает проще доказать правильность.]

Ключевое наблюдение за использованием рекурсии состоит в том, что диапазоны, начинающиеся с числа, заканчивающегося на 0 и заканчивающегося номером, заканчивающимся на 9, покрываются цифровыми шаблонами, которые заканчиваются на [0-9].

20-239 is covered by [2-9][0-9], 1[0-9][0-9], 2[0-3][0-9]

При снятии последней цифры начала и конца диапазона результирующий диапазон покрывается одними и теми же образцами цифр, за исключением отсутствующего заднего [0-9]:

20-239 is covered by [2-9][0-9], 1[0-9][0-9], 2[0-3][0-9]
2 -23  is covered by [2-9],      1[0-9],      2[0-3]

Итак, когда мы ищем цифровые шаблоны, охватывающие диапазон (например, 13-247), мы отделим диапазон до первого числа, заканчивающегося на 0, и диапазон после последнего числа, заканчивающегося на 9 ( обратите внимание, что эти разделенные диапазоны могут быть пустыми), например

13-247 = 13-19, 20-239, 240-247
20-247 =        20-239, 240-247
13-239 = 13-19, 20-239
20-239 =        20-239

Оставшийся диапазон обрабатывается рекурсивно, снимая последние цифры и добавляя [0-9] ко всем цифровым паттернам уменьшенного диапазона.

При создании пар start,end для поддиапазонов, которые могут быть покрыты одним цифровым шаблоном (как это сделано безмасштабированием и OP), поддиапазоны уменьшенного диапазона должны соответственно "взорваться".

Особые случаи, когда число или число, заканчивающееся на 0, не заканчивается в 0 в диапазоне, может произойти только в том случае, если начало и конец отличаются только на последнюю цифру; в этом случае весь диапазон может быть покрыт одним цифровым шаблоном.

Итак, вот альтернативная реализация getRegexPairs на основе этого принципа рекурсии:

private static List<Integer> getRegexPairs(int start, int end)
{
  List<Integer> pairs = new ArrayList<>();   
  if (start > end) return pairs; // empty range
  int firstEndingWith0 = 10*((start+9)/10); // first number ending with 0
  if (firstEndingWith0 > end) // not in range?
  {
    // start and end differ only at last digit
    pairs.add(start);
    pairs.add(end);
    return pairs;
  }

  if (start < firstEndingWith0) // start is not ending in 0
  {
    pairs.add(start);
    pairs.add(firstEndingWith0-1);
  }

  int lastEndingWith9 = 10*(end/10)-1; // last number in range ending with 9
  // all regex for the range [firstEndingWith0,lastEndingWith9] end with [0-9]
  List<Integer> pairsMiddle = getRegexPairs(firstEndingWith0/10, lastEndingWith9/10);
  for (int i=0; i<pairsMiddle.size(); i+=2)
  {
    // blow up each pair by adding all possibilities for appended digit
    pairs.add(pairsMiddle.get(i)  *10+0);
    pairs.add(pairsMiddle.get(i+1)*10+9);
  }

  if (lastEndingWith9 < end) // end is not ending in 9
  {
    pairs.add(lastEndingWith9+1);
    pairs.add(end);
  }

  return pairs;
}

Ответ 6

Один из вариантов должен был бы (для диапазона [n, m]) генерировать регулярное выражение n|n+1|...|m-1|m. Однако, я думаю, вы после получения чего-то более оптимизированы. Вы по-прежнему можете сделать то же самое, создать FSM, который соответствует каждому номеру, используя отдельный путь через конечный автомат, а затем использовать любой из известных алгоритмов минимизации FSM для создания более мелкой машины, а затем превратить это в более сжатое регулярное выражение (поскольку "регулярные выражения" без расширений Perl изоморфны машинам конечного состояния).

Скажем, мы смотрим на диапазон [107, 112]:

state1:
  1 -> state2
  * -> NotOK
state2:
  0 -> state2.0
  1 -> state2.1
  * -> NotOK
state2.0:
  7 -> OK
  8 -> OK
  9 -> OK
  * -> NotOK
state2.1:
  0 -> OK
  1 -> OK
  2 -> OK
  * -> NotOK

Мы больше не можем уменьшить эту машину. Мы можем видеть, что состояние2.0 соответствует RE [789], а 2.1 соответствует [012]. Затем мы можем видеть, что состояние2.0 равно (0[789])|(1[012]), а целое - 1(0[789])|(1[012]).

Дальнейшее чтение DFA minimization можно найти в Википедии (и связанных страницах).

Ответ 7

Если вы найдете диапазон шаблонов регулярных выражений от 5 до 300, которые также поддерживают float; есть лучший ответ, созданный мной...

^0*(([5-9]([.][0-9]{1,2})?)|[1-9][0-9]{1}?([.][0-9]{1,2})?|[12][0-9][0-9]([.][0-9]{1,2})?|300([.]0{1,2})?)$

для диапазона от 1 до 300

^0*([1-9][0-9]?([.][0-9]{1,2})?|[12][0-9][0-9]([.][0-9]{1,2})?|300([.]0{1,2})?)$

Ответ 8

Ответ Bezmax близок, но не совсем решает проблему правильно. Я считаю, что в нем есть несколько неверных деталей. Я исправил ошибки и написал алгоритм в c++. Основная проблема в алгоритме Bezmax заключается в следующем:

Функция prev должна выдавать следующее: 387 → 380 379 → 300 299 → 100, 99-> 10, 9-> 0 В то время как Безмакс имел: 387 → 380 379 → 300 299 → 0

У Bezmax было 299 "ослаблений" до 0, что могло бы оставить часть диапазона в определенных обстоятельствах. В основном вы хотите ослабить до минимального числа, которое вы можете, но никогда не меняете количество цифр. Полное решение - слишком много кода, чтобы публиковать здесь, но здесь есть важные части. Надеюсь, это кому-нибудь поможет.

    // Find the next number that is advantageous for regular expressions.
    //
    // Starting at the right most decimal digit convert all zeros to nines. Upon
    // encountering the first non-zero convert it to a nine and stop. The output
    // always has the number of digits as the input.
    // examples: 100->999, 0->9, 5->9, 9->9, 14->19, 120->199, 10010->10099
    static int Next(int val)
    {
       assert(val >= 0);

       // keep track of how many nines to add to val.
       int addNines = 0;

       do {
          auto res = std::div(val, 10);
          val = res.quot;
          ++addNines;
          if (res.rem != 0) {
             break;
          }
       } while (val != 0);

       // add the nines
       for (int i = 0; i < addNines; ++i) {
          val = val * 10 + 9;
       }

       return val;
    }

    // Find the previous number that is advantageous for regular expressions.
    //
    // If the number is a single digit number convert it to zero and stop. Else...
    // Starting at the right most decimal digit convert all trailing 9 to 0's
    // unless the digit is the most significant digit - change that 9 to a 1. Upon
    // encounter with first non-nine digit convert it to a zero (or 1 if most
    // significant digit) and stop. The output always has the same number of digits
    // as the input.
    // examples: 0->0, 1->0, 29->10, 999->100, 10199->10000, 10->10, 399->100
    static int Prev(int val)
    {
       assert(val >= 0);

       // special case all single digit numbers reduce to 0
       if (val < 10) {
          return 0;
       }

       // keep track of how many zeros to add to val.
       int addZeros = 0;

       for (;;) {
          auto res = std::div(val, 10);
          val = res.quot;
          ++addZeros;
          if (res.rem != 9) {
             break;
          }

          if (val < 10) {
             val = 1;
             break;
          }
       }

       // add the zeros
       for (int i = 0; i < addZeros; ++i) {
          val *= 10;
       }

       return val;
    }

    // Create a vector of ranges that covers [start, end] that is advantageous for
    // regular expression creation. Must satisfy end>=start>=0.
    static std::vector<std::pair<int, int>> MakeRegexRangeVector(const int start,
                                                                 const int end)
    {
       assert(start <= end);
       assert(start >= 0);

       // keep track of the remaining portion of the range not yet placed into
       // the forward and reverse vectors.
       int remainingStart = start;
       int remainingEnd = end;

       std::vector<std::pair<int, int>> forward;
       while (remainingStart <= remainingEnd) {
          auto nextNum = Next(remainingStart);
          // is the next number within the range still needed.
          if (nextNum <= remainingEnd) {
             forward.emplace_back(remainingStart, nextNum);
             // increase remainingStart as portions of the numeric range are
             // transfered to the forward vector.
             remainingStart = nextNum + 1;
          } else {
             break;
          }
       }
       std::vector<std::pair<int, int>> reverse;
       while (remainingEnd >= remainingStart) {
          auto prevNum = Prev(remainingEnd);
          // is the previous number within the range still needed.
          if (prevNum >= remainingStart) {
             reverse.emplace_back(prevNum, remainingEnd);
             // reduce remainingEnd as portions of the numeric range are transfered
             // to the reverse vector.
             remainingEnd = prevNum - 1;
          } else {
             break;
          }
       }

       // is there any part of the range not accounted for in the forward and
       // reverse vectors?
       if (remainingStart <= remainingEnd) {
          // add the unaccounted for part - this is guaranteed to be expressable
          // as a single regex substring.
          forward.emplace_back(remainingStart, remainingEnd);
       }

       // Concatenate, in reverse order, the reverse vector to forward.
       forward.insert(forward.end(), reverse.rbegin(), reverse.rend());

       // Some sanity checks.
       // size must be non zero.
       assert(forward.size() > 0);

       // verify starting and ending points of the range
       assert(forward.front().first == start);
       assert(forward.back().second == end);

       return forward;
    }

Ответ 9

Недавно у меня появилось требование, в котором мне нужно было разработать "Генератор регулярных выражений для диапазонов номеров" с использованием Java, и я разработал полное решение, которое публикуется на IdeOne, а класс называется ideone.java - Исходный код на ideone. ком. Код на ideone тщательно прокомментирован и использует тот же алгоритм, что и другие пользователи, поэтому я лишь выделю изменения и добавленные функции или исправленные проблемы. Я использовал часть решений, представленных в ответах Bezmax (концепция), arcy (общий код и идея создания диапазона RegEx в виде пар) и coproc (вместо этого использовалась рекурсия для генерации пар RegEx). метода, используемого Arcy). Спасибо всем трем людям.

Ideone.java предоставляет два открытых метода, которые реализуют логику RegExGenerator: один принимает строковые числовые диапазоны, а другой - целочисленные.

generateRegEx(String begStr, String endStr)
generateRegEx(int beg, int end)

Оба вышеупомянутых открытых метода вызывают метод generateRegExCommon, который, в свою очередь, вызывает метод getRegExPairsRecursion (та же реализация, что и в ответе coproc), чтобы создать список, содержащий числа в парах, которые представляют нижний и верхний пределы допустимых диапазонов RegEx. Затем он вызывает метод formatPairsToRegEx для преобразования пар RegEx в фактические диапазоны RegEx, которые могут содержать префикс нулей, чтобы соответствовать длине ввода, если во входе были нули. Если входные данные не содержат начальных нулей или если используется целочисленный ввод, никакие начальные нули не будут добавлены в выходные диапазоны. Вывод доступен в виде списка массивов строк, где каждая запись/элемент является допустимым числовым диапазоном регулярного выражения:

regexArray - String Array where each element is a valid regular expression range.
regexList  - List of String elements where each element is a valid regular expression range.

На рисунке ниже показана схема последовательности выполнения примера кода Java (ideone.java) с вводом и выводом на каждом этапе. Используемый пример имеет Диапазон ввода числовых строк с ведущими нулями, где нижнее значение диапазона равно "0006", а верхнее значение - "0977". Вывод, как показано на рисунке ниже:

000[6-9]
00[1-9][0-9]
0[1-8][0-9][0-9]
09[0-6][0-9]
097[0-7]

Код предоставляет следующие преимущества:

• Единое комплексное решение, сочетающее в себе лучшие из всех ответов и алгоритмов.
• Напечатайте операторы, которые помогают в отладке кода и могут быть легко преобразованы в любые операторы трассировки/отладки каркаса журналирования вместо System.out.
• Исправлена проблема, при которой низкий диапазон 0 не работал с другими ответами.