Цель
Сегодня задача Code Golf состоит в том, чтобы создать парсер регулярных выражений как можно меньше символов.
Синтаксис
Нет, я не прошу вас сопоставлять регулярные выражения в стиле Perl. В конце концов, для них очень надежный переводчик!: -)
Здесь все, что вам нужно знать о синтаксисе regex для этой задачи:
- Термин определяется как одиночный литерал или регулярное выражение в группировке круглых скобок
()
. - Символ
*
(звездочка) представляет собой операцию Kleene star на предыдущем TERM. Это означает, что ноль или более предыдущего термина объединены вместе. - Символ
+
(плюс) представляет собой удобный ярлык:a+
эквивалентенaa*
, что означает один или несколько предыдущих членов. - Символ
?
(вопросительный знак) представляет нуль или один из предыдущих членов. - Символ
|
(pipe) представляет собой чередование, что означает, что РЕГУЛЯРНЫЕ ЭКСПРЕССИИ с обеих сторон могут использоваться в матче. - Все остальные символы считаются буквальными. Вы можете предположить, что все остальные символы находятся в пределах
[0-9A-Za-z]
(т.е. Все английские буквенно-цифровые символы).
Или, по-другому: *
/+
/?
имеют наивысший приоритет, затем конкатенацию, затем чередование. Поскольку чередование имеет более низкий приоритет, чем конкатенация, его использование в регулярном выражении без круглых скобок заставляет его привязываться к полному регулярному выражению с каждой стороны. *
и +
и ?
, с другой стороны, применимы только к непосредственно предыдущему члену.
Задача
Ваша задача - написать программу, которая будет компилировать или интерпретировать регулярное выражение (как определено выше), а затем проверять несколько строк против него.
Я оставляю вам информацию. Моя рекомендация состояла бы в том, что регулярное выражение должно, вероятно, на первом месте, а затем любое количество строк, которые будут проверяться против него; но если вы хотите сделать это последним, это прекрасно. Если вы хотите поместить все в аргументы командной строки или в stdin, или в регулярное выражение в командной строке, и строки в stdin или что-то еще, это прекрасно. Просто покажите пример использования или два.
Вывод должен быть true
или false
, по одному в каждой строке, чтобы отображать соответствие регулярного выражения.
Примечание:
- Мне не нужно говорить об этом... но не используйте никакие библиотеки регулярных выражений на вашем языке! Вам нужно скомпилировать или интерпретировать шаблон самостоятельно. ( Изменить: Вы можете использовать регулярное выражение, если оно требуется для разделения или объединения строк. Вы просто не можете использовать его для прямого решения проблемы, например, преобразование входного регулярного выражения в языковое регулярное выражение и использование этого. )
- Регулярное выражение должно ПОЛНОСТЬЮ соответствовать строке ввода для этой задачи. (Эквивалентно, если вы знакомы с Perge-подобным регулярным выражением, предположите, что привязка начала и конца строки подходит для всех совпадений)
- Для этой задачи все специальные символы
()*+?|
не будут встречаться буквально. Если вы встаете на вход, можно с уверенностью предположить, что никакой шаблон не может соответствовать соответствующей строке. - Строки ввода для тестирования должны оцениваться с учетом регистра.
Примеры
В примерах я предполагаю, что все сделано в аргументах командной строки, сначала в regex. (Как я уже сказал выше, ввод зависит от вас.) myregex
здесь представляет собой ваш вызов программы.
> myregex easy easy Easy hard
true
false
false
> myregex ab*a aa abba abab b
true
true
false
false
> myregex 0*1|10 1 10 0110 00001
true
true
false
true
> myregex 0*(1|1+0) 1 10 0110 00001
true
true
true
true
> myregex a?b+|(a+b|b+a?)+ abb babab aaa aabba a b
true
true
false
true
false
true
ПРИМЕЧАНИЕ: Извините, забыли сделать сообщество wiki!: - (