Jak możemy dopasować a^n b^N z wyrażeniem regularnym Java?

Odpowiedź brzmi, nie trzeba dodawać, tak! z całą pewnością możesz napisać Java regex pattern pasujący a ⁿ b ⁿ. Używa dodatniego spojrzenia do twierdzenia i jednego zagnieżdżonego odniesienia do "liczenia".

Zamiast natychmiastowego podawania wzorca, ta odpowiedź poprowadzi czytelników przez proces wyprowadzania go. Różne wskazówki są podane, ponieważ rozwiązanie jest powoli konstruowane. W tym aspekcie, mam nadzieję, że ta odpowiedź będzie zawierać znacznie więcej niż tylko kolejny schludny wzór regex. Mam nadzieję, że czytelnicy nauczą się również ,jak "myśleć w wyrażeniach regularnych" i jak harmonijnie łączyć różne konstrukcje, aby mogli czerpać więcej wzorców samodzielnie w przyszłości.

Językiem używanym do opracowania rozwiązania będzie PHP ze względu na jego zwięzłość. Ostateczny test po zakończeniu wzorca zostanie wykonany w Javie.

---

Krok 1: poszukaj twierdzenia

Zacznijmy od prostszego problemu: chcemy dopasuj a+ na początku łańcucha, ale tylko wtedy, gdy następuje bezpośrednio b+. Możemy użyć ^ do anchor naszego dopasowania, a ponieważ chcemy dopasować tylko a+ BEZ b+, możemy użyć lookahead twierdzenia (?=…).

Oto nasz wzór z prostą uprzężą testową:

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);

Wyjście to (jak widać na ideone.com):

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

To jest dokładnie wyjście, które chcemy: dopasowujemy a+, tylko jeśli jest na początku ciągu i tylko wtedy, gdy po nim następuje b+.

Lekcja: możesz używać wzorców w lookarounds do tworzenia twierdzeń.

---

W 2007 roku, w 2009 roku, w ramach programu "Horyzont 2020", w ramach programu "Horyzont 2020", w 2009 roku, w ramach programu "Horyzont 2020" - programu ramowego w zakresie badań naukowych i innowacji (2014-2020), zrealizowano]}

Powiedzmy teraz, że chociaż nie chcemy, aby b+ był częścią meczu, chcemy przechwycić i tak do grupy 1. Ponadto, ponieważ przewidujemy posiadanie bardziej skomplikowanego wzoru, użyjmy modyfikatora x dla wolnego odstępu , abyśmy mogli uczynić nasz regex bardziej czytelnym.

Bazując na naszym poprzednim fragmencie PHP, mamy teraz następujący wzór:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead

testAll($r2, $tests);

Wyjście jest teraz (jak widać na ideone.com):

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

Zauważ, że np. aaa|b jest wynikiem join-ING tego, co każda grupa uchwyciła z '|'. W tym przypadku Grupa 0 (tzn. to, co pasowało do wzorca) przechwyciła aaa, a grupa 1 przechwyciła b.

Lekcja: możesz przechwytywanie wewnątrz lookaround. Możesz użyć odstępów swobodnych, aby zwiększyć czytelność.

---

[[107]}Krok 3: Refaktoryzacja lookahead do "pętli"

Zanim będziemy mogli wprowadzić nasz mechanizm liczenia, musimy zrobić jedną modyfikację naszego wzoru. Obecnie lookahead znajduje się poza powtórzeniem + "pętla". Na razie jest to w porządku, ponieważ chcieliśmy tylko stwierdzić, że istnieje b+ po naszym a+, ale to, co naprawdę chcemy zrobić, to stwierdzić, że dla każda a, którą dopasujemy wewnątrz "pętli", jest odpowiednia b.

Nie martwmy się na razie mechanizmem liczenia i wykonajmy refaktoryzację w następujący sposób:]}

• pierwszy refaktor a+ do (?: a )+ (zauważ, że (?:…) jest grupą nie przechwytywającą)
• następnie przenieś lookahead wewnątrz tej Nie przechwytywanej grupy
  • zauważ, że musimy teraz "pominąć" a* zanim będziemy mogli "zobaczyć" b+, więc zmodyfikuj wzór odpowiednio

Mamy więc teraz:

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

Wyjście jest takie samo jak wcześniej (jak widać na ideone.com ), więc nie ma żadnej zmiany w tym względzie. Ważne jest to, że teraz robimy twierdzenie przy każdej iteracji + "pętli". Przy naszym obecnym wzorze nie jest to konieczne, ale następnie zrobimy grupę 1 "liczymy" dla nas za pomocą samooceny.

Lekcja: możesz uchwycić wewnątrz grupy nie przechwytywanej. Lookarounds można powtórzyć.

---

Krok 4: jest to krok, w którym zaczynamy liczyć

Oto co zrobimy: przepiszemy grupę 1 taką, że:

• na końcu pierwszej iteracji +, gdy pierwsza a zostanie dopasowana, powinna przechwycić b
Na końcu drugiej iteracji, gdy inna iteracja zostanie dopasowana, powinna przechwycić]}
• pod koniec Trzeciej iteracji, to should capture bbb
• ...
• na końcu N-tej iteracji, Grupa 1 powinna przechwycić b ⁿ
• jeśli nie ma wystarczająco dużo b, aby przechwycić do grupy 1, wtedy twierdzenie po prostu nie powiedzie się

Więc grupa 1, która jest teraz (b+), będzie musiała zostać przepisana na coś w rodzaju (\1 b). Oznacza to, że staramy się" dodać " b do grupy 1 przechwyconej w poprzedniej iteracji.

Jest tu mały problem w tym, że w tym wzorze brakuje "przypadku podstawowego", tzn. przypadku, w którym może on pasować bez samo-odniesienia. Przypadek podstawowy jest wymagany, ponieważ Grupa 1 zaczyna się "niezinicjalizowana"; nie przechwyciła jeszcze niczego (nawet pustego ciągu znaków), więc próba samodzielnego odniesienia zawsze się nie powiedzie.

Jest wiele sposobów na obejście tego, ale na razie zróbmy dopasowanie self-reference opcjonalne , tzn. \1?. To może, ale nie może działać idealnie, ale zobaczmy, co to robi, a jeśli jest w razie problemów przejdziemy przez ten most. Przy okazji dodamy jeszcze kilka przypadków testowych.

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

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

Wyjście jest teraz (jak widać na 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-ha! Wygląda na to, że jesteśmy naprawdę blisko rozwiązania! Udało nam się zmusić grupę 1 do "liczenia" za pomocą samooceny! Ale czekaj... coś jest nie tak z drugim i ostatnim przypadkiem testowym!! Nie ma wystarczająco dużo bs, a jakoś źle się to liczyło! Sprawdzimy, dlaczego tak się stało. w następnym kroku.

Lekcja: jednym ze sposobów "inicjalizacji" grupy samo-referencji jest opcjonalne dopasowanie samo-referencji.

---

Krok 4½: zrozumienie, co poszło nie tak

Problem polega na tym, że ponieważ zrobiliśmy self-reference matching opcjonalnie, "licznik" może "zresetować" z powrotem do 0, gdy nie ma wystarczającej liczby b ' s.

 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-ha! W naszej czwartej iteracji wciąż mogliśmy dopasować \1, ale nie mogliśmy dopasować \1b! Ponieważ pozwoliliśmy, aby dopasowanie SELF-reference było opcjonalne z \1?, Silnik cofał się i przyjął opcję "NIE dzięki", która następnie pozwala nam dopasować i przechwycić tylko b!

Należy jednak pamiętać, że z wyjątkiem pierwszej iteracji, zawsze można dopasować tylko samo odniesienie \1. Jest to oczywiście oczywiste, ponieważ właśnie to uchwyciliśmy w naszej poprzedniej iteracji, a w naszej konfiguracji zawsze można dopasować go ponownie (np. jeśli przechwyciliśmy bbb ostatnim razem, mamy gwarancję, że nadal będzie bbb, ale może być lub nie być bbbb tym razem).

Lekcja: uważaj na cofanie. Silnik regex wykona tyle cofania, ile pozwoli, dopóki dany wzór się nie dopasuje. Może to mieć wpływ na wydajność (np. katastroficzne cofanie) i/lub poprawność.

---

Krok 5: samo posiadanie na ratunek!

The "fix" powinien być teraz oczywisty: połączyć opcjonalne powtórzenie z dzierżawczym kwantyfikatorem. Oznacza to, że zamiast po prostu ?, użyj ?+ zamiast (pamiętaj, że powtórzenie, które jest wymierne jako dzierżawcze, nie cofnie się, nawet jeśli taka "współpraca" może doprowadzić do dopasowania ogólnego wzoru).

W bardzo nieformalnych terminach, to jest to, co ?+, ? i ?? mówi:

?+

• (opcjonalnie) " nie musi tam być,"
  [162]}(zaborczy) "ale jeśli tam jest, musisz go wziąć i nie puścić!"

?

• (opcjonalnie) " nie musi tam być,"
  • (chciwy) "ale jeśli to jest można wziąć go na teraz,"
    • (backtracking) "ale możesz zostać poproszony, aby odpuścić później!"

??

• (opcjonalnie) " nie musi tam być,"
  • (2) " i nawet jeśli to jest, nie musisz go jeszcze brać,"
    • (backtracking) "ale możesz zostać poproszony, aby wziąć go później!"

W naszym zestawieniu, \1 nie będzie tam za pierwszym razem, ale zawsze będzie tam lada moment, a my {91]} zawsze {92]} będziemy chcieli dopasować to wtedy. W ten sposób osiągnęlibyśmy dokładnie to, czego chcemy.

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

Teraz wyjście jest (jako widziane na 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!!!

Voila!!! Problem rozwiązany!!! Teraz liczymy właściwie, dokładnie tak, jak chcemy!

Lekcja: Poznaj różnicę między chciwym, niechętnym i zaborczym powtarzaniem. Opcjonalny-dzierżawczy może być potężną kombinacją.

---

Krok 6: wykończenia

Więc to, co mamy teraz, to wzór, który pasuje a wielokrotnie, i dla każdego a, który został dopasowany, jest odpowiadające b uchwycone w grupie 1. + kończy się, gdy nie ma więcej a, lub jeśli twierdzenie nie powiodło się, ponieważ nie ma odpowiadającego b dla a.

Aby zakończyć zadanie, po prostu musimy dołączyć do naszego wzoru \1 $. Jest to teraz powrót do tego, co pasuje do grupy 1, a następnie koniec kotwicy linii. Anchor zapewnia, że nie ma żadnych dodatkowych b'S w łańcuchu; innymi słowy, że w rzeczywistości mamy a ⁿ b ⁿ.

Oto gotowy wzór, z dodatkowymi przypadkami testowymi, w tym jednym o długości 10 000 znaków:

$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

Znajduje 4 Mecze: ab, aabb, aaabbb, i a⁵⁰⁰⁰b⁵⁰⁰⁰. To trwa tylko 0.06 s, aby uruchomić na ideone.com .

---

Krok 7: Test Javy

Więc wzorzec działa w PHP, ale ostatecznym celem jest napisanie wzorca, który działa w 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);
}

Wzór działa zgodnie z oczekiwaniami (jak widać na ideone.com).

---

I teraz dochodzimy do wniosku...

[[90]}należy powiedzieć, że a* w lookahead, a nawet "main + loop", oba pozwalają na backtracking. Czytelnicy są zachęcani do potwierdzenia, dlaczego nie jest to problem pod względem poprawności, i dlaczego w tym samym czasie dokonywanie obu zaborczych również zadziała (choć być może mieszanie zaborczych obowiązkowych i nieobowiązkowych kwantyfikator w tym samym wzorze może prowadzić do nieporozumień).

Należy również powiedzieć, że chociaż jest schludne, że istnieje wzór regex, który będzie pasował a ⁿ b ⁿ, nie zawsze jest to "najlepsze" rozwiązanie w praktyce. Znacznie lepszym rozwiązaniem jest po prostu dopasowanie ^(a+)(b+)$, a następnie porównanie długości łańcuchów przechwyconych przez grupy 1 i 2 w języku programowania hostingu.

W PHP może wyglądać mniej więcej tak (jak widać w ideone.com):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

Celem tego artykułu jest Nie aby przekonać czytelników, że regex może zrobić prawie wszystko; najwyraźniej nie może, a nawet dla rzeczy, które może zrobić, przynajmniej częściowa Delegacja do języka hostingu powinna być rozważona, jeśli prowadzi do prostszego rozwiązania.

Jak wspomniano na górze, chociaż ten artykuł jest koniecznie oznaczony [regex] dla stackoverflow, być może chodzi o coś więcej. Choć z pewnością warto się uczyć o twierdzenia, zagnieżdżone odniesienia, dzierżawczy kwantyfikator itp., być może większą lekcją jest tutaj proces twórczy, w którym można próbować rozwiązać problemy, determinacja i ciężka praca, której często wymaga, gdy jesteś poddawany różnym ograniczeniom, systematyczny skład z różnych części, aby zbudować rozwiązanie robocze, itp.

---

Materiał bonusowy! PCRE recursive pattern!

Ponieważ poruszyliśmy PHP, trzeba powiedzieć, że PCRE obsługuje rekurencyjny wzorzec i podprogramy. Tak więc następujący wzór działa dla preg_match (jak widać na ideone.com):

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

Obecnie regex Javy nie obsługuje wzorca rekurencyjnego.

---

Jeszcze więcej materiałów bonusowych! Dopasowanie a ⁿ b ⁿ c ⁿ !!

Więc widzieliśmy jak dopasować a ⁿ b ⁿ który jest nieregularny, ale nadal bez kontekstu, ale możemy również dopasować a ⁿ b ^N c ⁿ , co nie jest nawet pozbawione kontekstu?

Odpowiedź brzmi, oczywiście, tak! czytelnicy są zachęcani do prób rozwiązania tego problemu na własną rękę, ale rozwiązanie jest podane poniżej (Z implementacją w Javie na ideone.com).

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