Ответ, разумеется, ДА! Вы, безусловно, можете написать шаблон регулярного выражения Java для соответствия a n b n . Он использует положительный прогноз для утверждения и одну вложенную ссылку для «подсчета».
Вместо того, чтобы немедленно выдавать образец, этот ответ проведет читателей через процесс его получения. Различные подсказки даны, поскольку решение медленно построено. В этом аспекте, надеюсь, этот ответ будет содержать гораздо больше, чем просто еще один аккуратный шаблон регулярных выражений. Надеемся, что читатели также узнают, как «мыслить в регулярных выражениях» и как гармонично соединять различные конструкции, чтобы в будущем они могли самостоятельно получать больше шаблонов.
Язык, используемый для разработки решения, будет PHP для краткости. Окончательный тест после завершения шаблона будет выполнен в Java.
Шаг 1. Ожидание утверждения
Давайте начнем с более простой задачи: мы хотим сопоставить a+ в начале строки, но только если за ней сразу следует b+. Мы можем использовать ^ до привязки нашего соответствия, и, поскольку мы хотим сопоставить только a+ без b+, мы можем использовать lookahead утверждение (?=…).
Вот наш шаблон с простым тестовым набором:
function testAll($r, $tests) {
foreach ($tests as $test) {
$isMatch = preg_match($r, $test, $groups);
$groupsJoined = join('|', $groups);
print("$test $isMatch $groupsJoined\n");
}
}
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
$r1 = '/^a+(?=b+)/';
# └────┘
# lookahead
testAll($r1, $tests);
Вывод ( как видно на ideone.com ):
aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a
Это именно тот результат, который нам нужен: мы сопоставляем a+, только если он находится в начале строки, и только если за ним сразу следует b+.
Урок : Вы можете использовать шаблоны в обходах, чтобы делать утверждения.
Шаг 2. Захват в предвкушении (и в режиме реального времени)
Теперь давайте скажем, что хотя мы не хотим, чтобы b+ был частью матча, мы все равно хотим захватить в любом случае в группу 1. Кроме того, поскольку мы ожидаем, что у нас будет больше сложный шаблон, давайте используем x модификатор для свободного пробела , чтобы мы могли сделать наше регулярное выражение более читабельным.
Основываясь на нашем предыдущем фрагменте PHP, теперь у нас есть следующий шаблон:
$r2 = '/ ^ a+ (?= (b+) ) /x';
# │ └──┘ │
# │ 1 │
# └────────┘
# lookahead
testAll($r2, $tests);
Вывод теперь ( как видно на ideone.com ):
aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb
Обратите внимание, что, например, aaa|b - это результат join, что каждая группа захватила с помощью '|'. В этом случае группа 0 (то есть, что соответствует шаблону) захватила aaa, а группа 1 захватила b.
Урок : Вы можете захватить в обходном взгляде. Вы можете использовать свободное пространство для улучшения читаемости.
Шаг 3: Перевод заглядывания в «петлю»
Прежде чем мы сможем ввести наш механизм подсчета, нам нужно сделать одну модификацию нашего паттерна. В настоящее время предвидение находится за пределами "цикла" + повторения. Пока все в порядке, потому что мы просто хотели утверждать, что после нашего a+ есть b+, но то, что мы действительно хотим сделать в конце концов, это утверждать, что для каждого a, который мы сопоставляем внутри "loop", есть соответствующий b, чтобы идти с ним.
Давайте пока не будем беспокоиться о механизме подсчета, а просто проведем рефакторинг следующим образом:
- Первый рефакторинг
a+ до (?: a )+ (обратите внимание, что (?:…) - это группа без захвата)
- Затем переместите взгляд в эту не захватывающую группу
- Обратите внимание, что теперь мы должны "пропустить"
a*, прежде чем мы сможем "увидеть" b+, поэтому измените шаблон соответственно
Итак, теперь у нас есть следующее:
$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
# │ │ └──┘ │ │
# │ │ 1 │ │
# │ └───────────┘ │
# │ lookahead │
# └───────────────────┘
# non-capturing group
Вывод такой же, как и раньше (, как видно на ideone.com ), поэтому никаких изменений в этом отношении нет. Важно то, что теперь мы делаем утверждение на каждой итерации + «цикла». В нашем текущем паттерне это не обязательно, но затем мы сделаем для группы 1 «счет», используя собственную ссылку.
Урок : Вы можете захватывать внутри группы без захвата. Lookarounds можно повторять.
Шаг 4: Это шаг, с которого мы начинаем считать
Вот что мы собираемся сделать: мы перепишем группу 1 так, чтобы:
- В конце первой итерации
+, когда сопоставляется первая a, она должна захватить b
- В конце второй итерации, когда сопоставляется другой
a, он должен захватить bb
- В конце третьей итерации она должна записать
bbb
- ...
- В конце n -й итерации группа 1 должна захватить b n
- Если не хватает
b для записи в группу 1, тогда утверждение просто не выполняется
Таким образом, группа 1, которая теперь называется (b+), должна быть переписана в нечто вроде (\1 b). То есть мы пытаемся «добавить» b к группе 1, захваченной на предыдущей итерации.
Здесь есть небольшая проблема в том, что в этом шаблоне отсутствует «базовый случай», т. Е. Случай, когда он может совпадать без самоссылки. Базовый случай необходим, потому что группа 1 начинает "неинициализированный"; он еще ничего не захватил (даже пустую строку), поэтому попытка самоссылки всегда будет неудачной.
Есть много способов обойти это, но сейчас давайте просто сделаем сопоставление с собственной ссылкой необязательным , т.е. \1?. Это может или не может работать идеально, но давайте просто посмотрим, что это делает, и если есть какие-то проблемы, то мы перейдем этот мост, когда придем к нему. Кроме того, мы добавим еще несколько тестов, пока мы на нем.
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
# │ │ └─────┘ | │
# │ │ 1 | │
# │ └──────────────┘ │
# │ lookahead │
# └──────────────────────┘
# non-capturing group
Вывод теперь ( как видно на ideone.com ):
aaa 0
aaab 1 aaa|b # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b # yes!
aabb 1 aa|bb # YES!!
aaabbbbb 1 aaa|bbb # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....
A-ха! Похоже, мы действительно близки к решению сейчас! Нам удалось заставить группу 1 «подсчитать», используя самоссылку! Но подождите ... что-то не так со вторым и последним тестами! Не хватает b с, и почему-то это считается неправильно! Мы рассмотрим, почему это произошло на следующем шаге.
Урок : Один из способов «инициализации» группы, ссылающейся на себя, состоит в том, чтобы сделать сопоставление с самообращением необязательным.
Шаг 4½: Понимание того, что пошло не так
Проблема в том, что, поскольку мы сделали опцию сопоставления с собственной ссылкой необязательной, «counter» может «сбросить» обратно на 0, когда не хватает b. Давайте внимательно рассмотрим, что происходит на каждой итерации нашего шаблона с aaaaabbb в качестве входных данных.
a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
_
a a a a a b b b
↑
# 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
# so it matched and captured just b
___
a a a a a b b b
↑
# 2nd iteration: Group 1 matched \1b and captured bb
_____
a a a a a b b b
↑
# 3rd iteration: Group 1 matched \1b and captured bbb
_
a a a a a b b b
↑
# 4th iteration: Group 1 could still match \1, but not \1b,
# (!!!) so it matched and captured just b
___
a a a a a b b b
↑
# 5th iteration: Group 1 matched \1b and captured bb
#
# No more a, + "loop" terminates
A-ха! На нашей 4-й итерации мы все еще могли соответствовать \1, но мы не могли соответствовать \1b! Поскольку мы допускаем опциональное сопоставление со ссылками на \1?, двигатель возвращается и выбирает вариант «нет, спасибо», что позволяет нам сопоставлять и захватывать только b!
Заметьте, однако, что, за исключением самой первой итерации, вы всегда можете сопоставить только самоссылку \1. Это очевидно, конечно, поскольку это то, что мы только что записали на нашей предыдущей итерации, и в нашей настройке мы всегда можем сопоставить его снова (например, если мы захватили bbb в прошлый раз, мы гарантируем, что все еще будет bbb, но в этот раз может быть или не быть bbbb.
Урок : Остерегайтесь возврата. Движок регулярных выражений будет выполнять столько откатов назад, сколько вы позволите, пока данный шаблон не совпадет. Это может повлиять на производительность (т. Е. катастрофический откат ) и / или правильность.
Шаг 5: Самообладание на помощь!
«Исправление» теперь должно быть очевидным: объедините необязательное повторение с собственническим квантификатором. То есть вместо простого ? используйте вместо него ?+ (помните, что повторение, которое количественно определяется как притяжательное, не возвращается, даже если такое «взаимодействие» может привести к совпадению общей схемы).
В очень неформальной форме это то, что ?+, ? и ?? говорят:
?+
- (необязательно) "Там не должно быть"
- (притяжательно) «но если оно есть, ты должен взять его и не отпускать!»
?
- (необязательно) "Это не должно быть там",
- (жадный) ", но если это так, вы можете взять его сейчас,«
- (возвращение)», но вас могут попросить отпустить позже! »
??
- (необязательно) "Его там не должно быть",
- (неохотно) ", и даже если это так, вам еще не нужно его принимать,"
- (возврат) «но вас могут попросить принять его позже!»
В нашей настройке \1 будетне будет там в первый раз, но это будет всегда после того, как это произойдет, и мы всегда захотим соответствовать ему тогда.Таким образом, \1?+ будет выполнять именно то, что мы хотим.
$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
# │ │ └──────┘ │ │
# │ │ 1 │ │
# │ └───────────────┘ │
# │ lookahead │
# └───────────────────────┘
# non-capturing group
Теперь вывод (, как видно на ideone.com ):
aaa 0
aaab 1 a|b # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb # Hurrahh!!!
Voilà!!!Задача решена!!!Теперь мы считаем правильно, именно так, как мы хотим!
Урок : Узнайте разницу между жадным, неохотным и притяжательным повторением.Факультативно-притяжательное может быть мощной комбинацией.
Шаг 6: Последние штрихи
Итак, сейчас у нас есть шаблон, который неоднократно совпадает с a и для каждого a при совпадении существует соответствующий b, захваченный в группе 1. + завершается, когда больше нет a, или если утверждение не выполнено из-за отсутствия соответствующего b для a.
Чтобы закончить работу, нам просто нужно добавить наш шаблон \1 $.Теперь это обратная ссылка на сопоставляемую группу 1, за которой следует конец якоря строки.Якорь гарантирует, что в строке нет лишних b;другими словами, что на самом деле у нас есть a n b n .
Вот окончательный вариант шаблона с дополнительными тестовыми примерами, включая одиндлина 10 000 символов:
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
'', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
str_repeat('a', 5000).str_repeat('b', 5000)
);
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
# │ │ └──────┘ │ │
# │ │ 1 │ │
# │ └───────────────┘ │
# │ lookahead │
# └───────────────────────┘
# non-capturing group
Находит 4 совпадения: ab, aabb, aaabbb и a 5000 b 5000 .Требуется всего 0,06 с для запуска на ideone.com .
Шаг 7. Тест Java
Таким образом, шаблон работает в PHP, но конечная цельэто написать шаблон, который работает в Java.
public static void main(String[] args) {
String aNbN = "(?x) (?: a (?= a* (\\1?+ b)) )+ \\1";
String[] tests = {
"", // false
"ab", // true
"abb", // false
"aab", // false
"aabb", // true
"abab", // false
"abc", // false
repeat('a', 5000) + repeat('b', 4999), // false
repeat('a', 5000) + repeat('b', 5000), // true
repeat('a', 5000) + repeat('b', 5001), // false
};
for (String test : tests) {
System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN));
}
}
static String repeat(char ch, int n) {
return new String(new char[n]).replace('\0', ch);
}
Шаблон работает как ожидалось (, как видно на ideone.com ).
А теперьмы приходим к выводу ...
Надо сказать, что a* в предвкушении и, действительно, "главная + петля", оба позволяют откат назад.Читателям рекомендуется подтвердить, почему это не является проблемой с точки зрения правильности, и почему одновременно может работать и притяжательное как притяжательное (хотя, возможно, смешивание обязательного и необязательного притяжательного квантификатора в одном и том же шаблоне может привести к неправильному восприятию).
Следует также сказать, что, хотя это и понятно, что существует шаблон регулярного выражения, который будет соответствовать a n b n , это не всегда«лучшее» решение на практике.Гораздо лучшим решением будет просто сопоставить ^(a+)(b+)$, а затем сравнить длину строк, захваченных группами 1 и 2. на языке программирования хостинга.
В PHP это может выглядеть примерно так ( как видно на ideone.com ):
function is_anbn($s) {
return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
(strlen($groups[1]) == strlen($groups[2]));
}
Цель этой статьи - НЕ , чтобы убедить читателей, что регулярное выражение может делать практически все;он явно не может, и даже для вещей, которые он может сделать, следует рассмотреть хотя бы частичное делегирование языку хостинга, если это приведет к более простому решению.
Как упоминалось выше, хотя эта статья обязательно помечена как [regex] для stackoverflow, возможно, речь идет о чем-то большем. Хотя, безусловно, полезно узнать об утверждениях, вложенных ссылках, собственнических квантификаторах и т. Д., Пожалуй, самый большой урок здесь - это творческий процесс, с помощью которого можно попытаться решить проблемы, решительность и тяжелая работа, которые часто требуются, когда вы подвергаетесь различные ограничения, систематический состав из различных частей для создания рабочего решения и т. д.
Бонусный материал! PCRE рекурсивный шаблон!
Поскольку мы действительно поднимали PHP, нужно сказать, что PCRE поддерживает рекурсивный шаблон и подпрограммы. Таким образом, следующий шаблон работает для preg_match (, как видно на ideone.com ):
$rRecursive = '/ ^ (a (?1)? b) $ /x';
В настоящее время регулярное выражение Java не поддерживает рекурсивный шаблон.
Еще больше бонусного материала! Соответствие a n b n c n !!
Итак, мы увидели, как сопоставлять a n b n , что является нерегулярным, но все же не зависящим от контекста, но можем ли мы также сопоставить a n b n c n , что даже не зависит от контекста?
Ответ, конечно, ДА! Читателям рекомендуется попытаться решить эту проблему самостоятельно, но решение предоставлено ниже (с реализацией на Java на ideone.com ).