Генерация всех перестановок текста из регулярного выражения в C # - PullRequest
Новая
       20

Генерация всех перестановок текста из регулярного выражения в C #

0 голосов
/ 08 октября 2009

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

Пример: 

var pattern = "^My (?:biological|real)? Name is Steve$";
var permutations = getStringPermutations(pattern);

Это вернет список строк ниже:

Меня зовут Стив

Мое настоящее имя Стив

Мое биологическое имя Стив

Обновление: Очевидно, что регулярное выражение имеет бесконечное количество совпадений, поэтому я хочу генерировать только из необязательных строковых литералов, как в (?: Bio | real)? из моего примера выше. Что-то вроде (.) * Имеет слишком много совпадений, поэтому я не буду генерировать их из этого.

Ответы [ 3 ]

1 голос
/ 08 октября 2009

Если вы ограничиваетесь подмножеством регулярных выражений, которые привязаны на обоих концах и включают только буквальный текст, подстановочные знаки из одного символа и чередование, сопоставление Строки должны быть довольно легко перечислить. Я, вероятно, переписал бы регулярное выражение как грамматику БНФ и использовать это для генерации исчерпывающего списка совпадающих строк. Для вашего примера: 

<lang>   -> <begin> <middle> <end>
<begin>  -> "My "
<middle> -> "" | "real" | "biological"
<end>    -> " name is Steve"

Начните с производств, которые имеют только терминальные символы в RHS, и перечислите все возможные значения, которые может принять нетерминал на LHS. Тогда работай своим вплоть до постановок с нетерминалами на RHS. Для объединения нетерминальных символов сформируйте декартово произведение множеств, представленных каждым нетерминалом RHS. Для чередования возьмем объединение множеств, представленных каждой опцией. Продолжить пока вы не доберетесь до <lang>, тогда все готово.

Однако, если вы включите операторы «*» или «+», вам придется бороться с бесконечным количество совпадающих строк. И если вы также хотите обрабатывать расширенные функции, такие как обратные ссылки ... вы, вероятно, уже на пути к чему-то изоморфному к проблеме остановки!

0 голосов
/ 08 октября 2009

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

public static List<string> Calculate(List<string> strings) {
            List<string> returnValue = new List<string>();
            int[] numbers = new int[strings.Count];
            for (int x = 0; x < strings.Count; x++) {
                numbers[x] = 0;
            }
            while (true) {
                StringBuilder value = new StringBuilder();
                for (int x = 0; x < strings.Count; x++) {
                    value.Append(strings[x][numbers[x]]);
                    //int absd = numbers[x];
                }
                returnValue.Add(value.ToString());
                numbers[0]++;
                for (int x = 0; x < strings.Count-1; x++) {
                    if (numbers[x] == strings[x].Length) {
                        numbers[x] = 0;
                        numbers[x + 1] += 1;
                    }
                }
                if (numbers[strings.Count-1] == strings[strings.Count-1].Length)
                    break;

            }
            return returnValue;
        }
0 голосов
/ 08 октября 2009

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

...