Обратные регулярные выражения
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [3.144.38.24] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Обратные регулярные выражения
|
Сообщ.
#1
,
|
|
|
|
Возмем, к примеру, регулярное выражение "Доброго дня, Во(ва|лодя)". Множество строк, принимаемых этим выражением конечно: "Доброго дня, Володя" и "Доброго дня, Вова".
Задача: исходя из регулярного выражения, построить множество строк, принимаемых этим выражением. У кого какие идеи. Нужно решить эту задачу с минимальными усилиями. |
|
Сообщ.
#2
,
|
|
|
|
Не поняла задачу.
Из примера видно: сколько вариантов задано в регулярном выражении, столько строк получаем. |
|
Сообщ.
#3
,
|
|
|
|
Цитата Swetlana @ Не поняла задачу. Из примера видно: сколько вариантов задано в регулярном выражении, столько строк получаем. Весь вопрос состоит в том как реализовать функцию, принимающую на входе регулярное выражение и выдающую множество строк, порождаемого регулярным выражением. А сколько здесь строк получим: "In the 19[0-9]{2,2} year mr. (John|Smith|Bin) found a hairy (hand|banana|apple|ass) in his (car|bedroom|closet)" ? Будем комбинаторикой заниматься? |
|
Сообщ.
#4
,
|
|
|
|
Да, комбинаторикой. Самое эффективное представление этого перебора - алгоритм с возвратом.
Более быстрого алгоритма нет, потому что это задача перечисления. Если ты хочешь увидеть на печати все решения, то алгоритм должен совершить шагов не меньше, чем этих решений. В этой задаче кол-во вариантов строк растет экспоненциально от размерности входных данных. |
|
Сообщ.
#5
,
|
|
|
|
Цитата Swetlana @ Да, комбинаторикой. Самое эффективное представление этого перебора - алгоритм с возвратом. Более быстрого алгоритма нет, потому что это задача перечисления. Если ты хочешь увидеть на печати все решения, то алгоритм должен совершить шагов не меньше, чем этих решений. В этой задаче кол-во вариантов строк растет экспоненциально от размерности входных данных.  |
|
Сообщ.
#6
,
|
|
|
|
Можно представить это в виде ориентированного дерева. Корень дерева - вершина s="In the 19". Это нулевой уровень. От нее идут направленные дуги к вершинам 0, 1,..., 9. Это первый уровень. На предпоследнем уровне находятся вершины "car", "bedroom", "closet". От них идут дуги к вершине t=".", это последний уровень.
Задача формулируется так: "Напечатать все пути от s до t". Бустер, у меня и программка на паскале имеется. В хорошие руки отдам задешево  |
|
Сообщ.
#7
,
|
|
  |
Язык регулярного выражения может быть бесконечным.
Алгоритм: По регулярному выражению строим детерменистический конечный автомат for i=0 to бесконечность Прогоняем на автомате все длины i и те из них которые автомат получает печатем end for |
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0244 ] [ 14 queries used ] [ Generated: 19.05.24, 16:29 GMT ]