Regex для сопоставления строки, которая не содержит «xxx»

Question

Один из моих домашних заданий задал вопрос о разработке регулярного выражения для всех строк свыше x,y,z, которые не содержали xxx

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

(x(?!xx)|y|z)*

Тем не менее, в духе завершенности, есть ли возможность написать это без негативного взгляда?

Чтение, которое я сделал, заставляет меня думать, что это можно сделатьс некоторой комбинацией carets (^), но я не могу получить правильную комбинацию, поэтому я не уверен.

Если сделать шаг вперед, можно ли исключить строку типа xxx, используя толькоor (|) оператор, но все еще проверять строки рекурсивным способом?

РЕДАКТИРОВАТЬ 06.09.2010:

Думаю, я ответил на свой вопрос.Я еще немного запутался, пытаясь сделать это регулярное выражение только с or (|) утверждениями, и я почти уверен, что понял это ... и это не так беспорядочно, как я думал.Если бы у кого-то было время проверить это человеческим глазом, я был бы признателен.

(xxy|xxz|xy|xz|y|z)*(xxy|xxz|xx|xy|xz|x|y|z)

Answer 1

Попробуйте это:

^(x{0,2}(y|z|$))*$

Основная идея такова: для совпадения не более 2 X, с последующей другой буквой или концом строки.

Когда вы достигнете точкитам, где у вас есть 3 X, у регулярного выражения нет правила, которое позволяет ему продолжать сопоставление, и оно терпит неудачу.

Рабочий пример: http://rubular.com/r/ePH0fHlZxL

Менее компактный способ написать то же самое (со свободными пробелами, обычно флаг /x):

^(
y|         # y is ok
z|         # so is z
x(y|z|$)|  # a single x, not followed by x
xx(y|z|$)  # 2 x's, not followed by x
)*$

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

^(xxy|xxz|xy|xz|y|z)*(xx|x|)$

Answer 2

В принципе, у вас уже есть правильный ответ - вы молодцы.:)

Карат (^) в наборе [^abc] будет совпадать только в том случае, если он не находит символ в этом наборе, поэтому его применение для сопоставления порядков символов (т. Е. Строк) ограничено и слабо.

Regex имеет числовые квантификаторы {n} и {a,b}, которые позволяют вам соответствовать определенному количеству повторений шаблона, которое будет работать для этого конкретного шаблона (потому что повторяется 'x'), но это не особенноВыражает проблему, которую вы пытаетесь решить (даже для регулярных выражений!), и немного хрупкая (например, она не подходит для отрицательного соответствия 'xyx'.

Опять или шаблон снова будет многословными довольно невыразительно, но это можно сделать как фрагмент:

(x|xx)[^x] // x OR xx followed by NOT x

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

Хорошо сделано для размышлений за пределамирешение, хотя.

Answer 3

Я знаю, что вы не хотите использовать Lookahead, но есть еще один способ решить эту проблему:

^(?:(?!xxx)[xyz])*$

будет соответствовать любой строке символов x, y или z, если она не содержит строку xxx.