Как мы можем сопоставить a^n b^n с регулярным выражением Java?

ответ, само собой разумеется,да! вы можете, безусловно, написать шаблон регулярного выражения Java, чтобы соответствовать aⁿbⁿ. Он использует положительный внешний вид для утверждения и одну вложенную ссылку для "подсчета".

вместо того, чтобы сразу выдавать шаблон, этот ответ проведет читателей через процесс получения его. Различные подсказки даются по мере того, как решение медленно строится. В этом аспект, надеюсь, этот ответ будет содержать гораздо больше, чем просто еще один аккуратный шаблон регулярного выражения. Надеюсь, читатели также узнают, как" думать в регулярном выражении " и как гармонично сочетать различные конструкции, чтобы в будущем они могли получить больше шаблонов самостоятельно.

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

---

Шаг 1: Lookahead для утверждение

давайте начнем с более простой проблемы: мы хотим, чтобы соответствовать 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);

выход (как видно on ideone.com):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

это именно тот результат, который мы хотим: мы соответствуем a+, только если он находится в начале строки, и только если за ним сразу же следует b+.

урок: вы можете использовать шаблоны в lookarounds, чтобы сделать утверждения.

---

Шаг 2: захват в lookahead (и F r e e - s p A C i N G mode)

теперь давайте скажем, что даже если мы не хотим 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 - ing то, что каждая группа захватила с '|'. В этом случае группа 0 (т. е. то, что соответствует шаблону) захватила aaa, и группа 1 захвачена b.

урок: вы можете захватить внутри lookaround. Вы можете использовать свободное расстояние для повышения читаемости.

---

Шаг 3: рефакторинг lookahead в "петлю"

прежде чем мы сможем ввести наш подсчитывая механизм, нам нужно сделайте одно изменение к нашей картине. В настоящее время lookahead находится за пределами + повторение "цикл". Это нормально до сих пор, потому что мы просто хотели утверждать, что есть b+ следуя a+, но то, что мы действительно хотите сделать в конце концов это утверждать, что для каждого a что мы совпадаем внутри "петли", есть соответствующий b, чтобы пойти с ним.

давайте не будем беспокоиться о механизме подсчета и делать рефакторинг как следует:

• первый рефакторинг a+ до (?: a )+ (заметим, что (?:…) является группой без захвата)
• затем переместите lookahead внутри этой группы без захвата
  • обратите внимание, что теперь мы должны "пропустить" a* прежде чем мы сможем "увидеть"b+, поэтому измените шаблон соответственно

Итак, теперь у нас есть следующее:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

выход такой же, как и раньше (как видно на ideone.com), так что никаких изменений в этом отношении нет. Важно то, что теперь мы делаем утверждение в шаг на + "петля". С нашим текущим шаблоном это не обязательно, но затем мы сделаем группу 1 "count" для нас, используя само-ссылку.

урок: вы можете захватить внутри группы без захвата. Lookarounds можно повторить.

---

Шаг 4: это шаг, где мы начинаем считать

вот что мы собираемся сделать: мы перепишем группу 1 таким образом, что:

• в конце первой итерации +, когда первый a соответствует, он должен захватить b
• в конце второй итерации, когда другой a соответствует, он должен захватить bb
• в конце третьей итерации, он должен захватить bbb
• ...
• в конце n-ой итерации, группа 1 должна захватить bⁿ
• если не хватает b чтобы захватить в группу 1, то утверждение просто не

Итак, группа 1, которая теперь (b+), придется переписать на что-то вроде ( b). То есть мы стараемся добавить b к какой группе 1 захватили в предыдущей итерация.

здесь есть небольшая проблема в том, что в этом шаблоне отсутствует "базовый случай", т. е. случай, когда он может совпадать без самореференции. Базовый случай необходим, потому что группа 1 запускает "неинициализированный"; она еще ничего не захватила (даже пустую строку), поэтому попытка самореференции всегда будет неудачной.

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

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);

$r4 = '/ ^ (?: a (?= a* (? 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....

а-ха! Похоже, мы действительно близки к решению сейчас! Нам удалось получить группу 1 для "подсчета" с помощью self-reference! Но подождите... что-то не так со вторым и последним тестовые случаи!! Там не хватает bs, и как-то это посчитали неправильно! Мы рассмотрим, почему это произошло в следующем шаге.

урок: один из способов "инициализировать" группу самореференции-сделать необязательным сопоставление самореференции.

---

шаг 4½: понимание того, что пошло не так

проблема в том, что, поскольку мы сделали самоназвание соответствия необязательным, "счетчик" может "сбросить" обратно в 0, когда там не хватает b's. давайте внимательно рассмотрим, что происходит на каждой итерации нашего шаблона с 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  since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match , but not b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched b and captured bb
          #
          # No more a, + "loop" terminates

а-ха! На нашей 4-й итерации мы все еще могли бы соответствовать , но мы не смогли подобрать b! Поскольку мы разрешаем сопоставление самореференции быть необязательным с ?, двигатель отступает и взял опцию" Нет спасибо", которая затем позволяет нам сопоставлять и захватывать только b!

заметьте, однако, что за исключением самого первого итерация, вы всегда можете соответствовать только само-ссылка . Это очевидно, конечно, так как это то, что мы только что захватили на нашей предыдущей итерации, и в нашей настройке мы всегда можем сопоставить его снова (например, если мы захватили bbb в прошлый раз, мы гарантируем, что все еще будет bbb, но может быть или не быть bbbb в этот раз).

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

---

Шаг 5: самообладание на помощь!

теперь "исправление" должно быть очевидным: объедините необязательное повторение с собственницей Квантор. То есть, вместо просто ? используйте ?+ вместо этого (помните, что повторение, которое количественно определяется как притяжательное, не отступает, даже если такое "сотрудничество" может привести к совпадению общей картины).

в очень неформальном плане, это то, что ?+,? и ?? говорит:

?+

• (необязательно) " это не должно быть там,"
  • (притяжательно) " но если он есть, вы должны взять его и не отпускать!"

?

• (необязательно) " это не так должен быть там,"
  • (жадный) ", но если вы можете взять его сейчас,"
    • (отступление) "но вас могут попросить отпустить его позже!"

??

• (необязательно) " это не должно быть там,"
  • (неохотно) " и даже если это так, вам пока не нужно его принимать,"
    • (откат) "но вы можете быть попросил взять его позже!"

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

$r5 = '/ ^ (?: a (?= a* (?+ 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!!!

вуаля!!! Проблема решено!!! Теперь мы считаем правильно, именно так, как мы этого хотим!

урок: узнайте разницу между жадным, неохотным и собственническим повторением. Необязательный-притяжательный может быть мощной комбинацией.

---

Шаг 6: последние штрихи

так что у нас сейчас есть шаблон, который соответствует a неоднократно, и для каждого a что было сопоставлено, есть соответствующий b захватили в 1-й группе. Элемент + завершается, когда больше нет a, или если утверждение не удалось, потому что нет соответствующего b на a.

чтобы закончить работу, нам просто нужно добавить на наш шаблон $. Теперь это обратная ссылка на то, что соответствует группе 1, за которой следует конец якоря линии. Якорь гарантирует, что нет никаких дополнительных bв строке; другими словами, что на самом деле нас aⁿbⁿ.

вот окончательный шаблон с дополнительными тестовыми случаями, в том числе с длиной 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* (?+ b) ) )+  $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

он находит 4 матча:ab,aabb,aaabbb и a⁵⁰⁰⁰b⁵⁰⁰⁰. Это займет только 0.06 s для запуска 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('', ch);
}

шаблон работает, как ожидалось (как видно на ideone.com).

---

и теперь мы приходим к выводу...

надо сказать, что a* в lookahead, и действительно " главный + петля", оба позволяют отследить. Читателям предлагается подтвердить, почему это не проблема с точки зрения правильности, и почему в то же время создание обоих притяжательных также будет работать (хотя, возможно, смешивание обязательного и необязательного притяжательного квантора в одном и том же шаблоне может привести к ошибочным восприятиям).

следует также сказать, что, хотя это аккуратно, что есть шаблон регулярного выражения, который будет соответствовать aⁿbⁿ, это не всегда "лучшее" решение на практике. Гораздо лучшее решение - просто соответствовать ^(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 может делать почти все; он явно не может, и даже для того, что он может делать, следует рассмотреть хотя бы частичное делегирование на язык хостинга, если это приводит к более простому решению.

как говорили в верхах, а эта статья обязательно помечена[regex] для stackoverflow, это, пожалуй, больше, чем это. Хотя, конечно, есть ценность в изучении утверждений, вложенных ссылок, притяжательного квантора и т. д., возможно, больший урок здесь-это творческий процесс, с помощью которого можно попытаться решить проблемы, решимость и тяжелая работа, которые часто требуются, когда вы подвергаетесь различным ограничениям, систематическая композиция из разных частей для создания рабочего решения, так далее.

---

бонусный материал! PCRE рекурсивный шаблон!

поскольку мы подняли PHP, нужно сказать, что PCRE поддерживает рекурсивный шаблон и подпрограммы. Таким образом, следующий шаблон работает для preg_match (как видно на ideone.com):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

в настоящее время регулярное выражение Java не поддерживает рекурсивный шаблон.

---

еще больше бонусных материалов! Совмещение aⁿbⁿcⁿ !!

так что мы видели, как соответствовать aⁿbⁿ который является нерегулярным, но все еще контекстно-свободным, но можем ли мы также соответствовать aⁿbⁿcⁿ, который даже не контекстно-свободной?

ответ, конечно, да! читателям рекомендуется попытаться решить эту проблему самостоятельно, но решение приведено ниже (с реализация на Java ВКЛ ideone.com).

^ (?: a (?= a* (?+ b) b* (?+ c) ) )+ $