2. Praktické regulárne výrazy 2

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Michalovi “Žabovi” Anderlemu na

V minulej sérii sme sa prvýkrát stretli s regulárnymi výrazmi v tejto úlohe¹. Opäť sa k nim však vrátime. Ako sme videli, pomocou regulárnych výrazov sa dajú hľadať alebo akceptovať rôzne zaujímavé reťazce, ktoré spĺňajú isté vlastnosti. Napríklad môžete ľahko napísať regulárny výraz, ktorý vám overí, či je zadaný reťazec e-mailová adresa. Niekedy však potrebujeme overovať aj zložitejšie vlastnosti. Napríklad deliteľnosť.

A práve o tom bude celá táto séria. Budeme sa snažiť akceptovať reťazce cifier 0 až 9, ktoré reprezentujú čísla a naviac musia byť deliteľné nejakým konkrétnym číslom. Deliteľnosť niektorými číslami sa overuje ľahko, napr. 2, 4, 5, 8 alebo 10. Inými je to o niečo zložitejšie. V rámci tohto zadania postupne vytvoríme regulárny výraz akceptujúce čísla deliteľné troma. Nemusíte sa však báť, pôjdeme na to krok po kroku. Začneme tým, že si pripomenieme ako také regulárne výrazy vytvárame.

Základy použitia regulárnych výrazov

Pre jednoduchosť sa dohodneme, že všetky objekty, ktoré budeme hľadať, budú reťazce tvorené obmedzenou množinou znakov. Povolené znaky budú len písmená anglickej abecedy a cifry ("a"-"z", "A"-"Z", "0"-"9").²

Vyhľadávať budeme tak, že napíšeme regulárny výraz – teda nejakú vzorku (pattern). Vzorka popisuje ako vyzerajú reťazce, ktoré nás zaujímajú. Presnejšie, o každom reťazci vieme povedať, či vzorke zodpovedá (matches the pattern) a naším cieľom pri vyhľadávaní bude napísať vzorku tak, aby jej zodpovedali práve tie reťazce, ktoré chceme nájsť a žiadne iné. Ako uvidíme nižšie, vo vzorke sa budú môcť vyskytovať aj niektoré iné znaky ako v reťazcoch.

Teraz si popíšeme základy tvorby vzoriek – teda povieme si, z čoho sa taká vzorka môže skladať a ktoré reťazce jej potom zodpovedajú.

• Základným stavebným kameňom vzoriek sú samotné znaky z vyššie uvedeného zoznamu. Vzorke tvorenej jediným znakom zodpovedá reťazec tvorený dotyčným znakom a nič iné.

• Základná operácia so vzorkami je zreťazenie. Keď napíšeme dve vzorky za sebou, dostaneme novú vzorku. Tej zodpovedajú reťazce zložené z dvoch častí, pričom prvá zodpovedá prvej vzorke a druhá druhej. Zreťaziť samozrejme môžeme ľubovoľne veľa vzoriek. Napr. vzorke "jablko" zodpovedá len reťazec "jablko".

• Vzorky môžeme uzatvárať do obyčajných zátvoriek. Napr. vzorke "(jablko)" zodpovedá len reťazec "jablko" a nič iné.

• Logický or (alebo) je označovaný symbolom "|". Ak ním spojíme dve vzorky, dostaneme novú, ktorej zodpovedajú aj reťazce zodpovedajúce prvej, aj reťazce zodpovedajúce druhej vzorke. Napr. vzorke "jabl(k|ck)o" zodpovedajú reťazce "jablko" a "jablcko".

  Zreťazenie má vyššiu prioritu ako or. Napr. vzorke "aaa|bbb" zodpovedajú len reťazce "aaa" a "bbb".

• Inú možnosť, ako dať vo vzorke na výber predstavuje množina znakov, ktoré sa na danom mieste môžu vyskytnúť. Tú zapisujeme "[znaky]". Napríklad vzorke "jablk[oa]" zodpovedajú reťazce "jablko" a "jablka".

  Množina všetkých dostupných znakov sa skrátene zapisuje ".". Teda vzorke "j....a" zodpovedá každý 6-znakový reťazec začínajúci na "j" a končiaci na "a".

  Zložitejšie množiny znakov môžeme zapísať pomocou rozsahov, napr. "[a-z0-9]" je ľubovoľné malé písmeno alebo číslica. Ak popis množiny znakov začína znakom "^", znamená to negáciu: danej množine zodpovedajú všetky znaky okrem vymenovaných. Napríklad vzorke "[a-z][^a-zA-Z]" zodpovedajú všetky dvojznakové reťazce, ktorých prvý znak je malé písmeno a druhý znak nie je ani malé, ani veľké písmeno.

• Ak chceme, aby sa mohla časť vzorky v reťazci zopakovať, použijeme kvantifikátor. Základné kvantifikátory sú "?" (nulakrát alebo jedenkrát) a "*" (ľubovoľne veľakrát, aj nulakrát).

  Napríklad vzorka "jablc?ko" je ekvivalentná so vzorkou "jabl(k|ck)o". Vzorke "pe*s" zodpovedajú okrem iného reťazce "ps", "pes", "pees"… Vzorke "(ab)*c" nezodpovedá reťazec "aabbc", len reťazce "c", "abc", "ababc", atď.

  Pri opakovaní vzorky jej nemusí zakaždým zodpovedať ten istý reťazec. Napríklad vzorke "j.*a" zodpovedá nielen reťazec "jxxxa", ale aj reťazec "jahoda".

  Vzorke "<[^>]*>" zodpovedá každý XML tag – reťazec začína znakom "<", za ním nasleduje ľubovoľne veľa znakov iných od ">" a za nimi nasleduje znak ">".

Súťažná úloha

Táto úloha má niekoľko podúloh. V každej podúlohe budete mať slovne popísanú nejakú skupinu reťazcov. Vaším cieľom bude napísať vzorku, ktorej zodpovedajú všetky popísané reťazce a žiadne iné!

1. (1 bod) Začneme zľahka. Napíšte regulárny výraz, ktorý akceptuje čísla deliteľné piatimi, ktoré nezačínajú zbytočnými nulami. To znamená, že má akceptovať reťazce "0", "15", ale nemá akceptovať reťazce "015" alebo "11111".

V ďalších podúlohách budeme riešiť problémy zlodejov z filmu Sám doma. Stoja na začiatku vysokých schodov, dá sa povedať že nekonečných, a chcú vyjsť hore. Každým krokom môžu buď výjsť o schod vyššie (1) alebo jeden schod prekročia, čím sa dostanú o dva schody vyššie (2). Ich cesta hore schodmi sa teda dá zapísať ako reťazec z "1" a "2". Nemusia dokonca výjsť ani úplne navrch, je možné, že na niektorom schode zastanú a zostanú tam proste stáť.

Ak by sme chceli napísať regulárny výraz, ktorý akceptuje všetky reťazce, ktoré zodpovedajú ich cestám hore schodmi, vyzeral by takto: "[12]*". Kevin však na nich prichystal pascu a niektoré schody natrel lepidlom. Tým sa chcú zlodeji väčšinou vyhnúť, lebo ak na ne stúpia, prilepia sa a ostanú tam stáť.

2. (2 body) Kevin potrel lepidlom tretí a šiesty schod. Napíšte regulárny výraz, ktorý akceptuje všetky cesty po schodoch, pri ktorých sa zlodej nenalepí na žiadny schod a vyjde aspoň na siedmy schod. To znamená, že treba akceptovať reťazce "1121222" alebo "11212", ale nemôžete akceptovať napríklad "111", "22" alebo "2112".

3. (3 body) Tentokrát sú lepidlom natreté všetky schody, ktorých číslo je deliteľné tromi. Vytvorte regulárny výraz, ktorý akceptuje všetky cesty hore schodmi, pri ktorých sa zlodej nikdy neprilepí. To znamená, že reťazec "11222212" nemáte akceptovať, lebo zlodej sa prilepí na schode číslo \(6\) (po tom, čo urobí "1122"). Dobré reťazce sú napríklad "11" alebo "1121212".

4. (2 body) Lepidlom sú stále natreté schody deliteľné tromi. Lepidlo je však neviditeľné a zlodeji o ňom nevedia. Preto sa počas toho, ako išli hore nalepili na jednom schode. Spravte regulárny výraz, ktorý popisuje práve tie cesty hore schodmi, ktoré skončia na schode deliteľnom troma. Správne reťazce sú napríklad "112122" alebo "111", ale nie "2212", lebo pri ňom sa zlodej nenalepil a ani "22111122", lebo zlodej sa nalepil už na schode šesť, po tom čo prešiel "2211" a teda nemohol pokračovať.

5. (1 bod) Zadanie je rovnaké ako v podúlohe d), akurát zlodej má na sebe viacero vrstiev ponožiek a keď sa nalepí na nejaký schod, najvrchnejšiu vrstvu si môže vyzuť a pokračovať v ceste. Skončiť ale musí aj tak na schode deliteľnom tromi. To znamená, že reťazec "22111122" je správny, v poriadku ale nie je reťazec "12212221", lebo takáto cesta neskončí na zalepidlovanom schode.

Odteraz to už bude veľmi podobné podúlohe e). Budeme chcieť také cesty hore schodmi, ktoré skončia na schode deliteľnom tromi, pričom medzitým sa môže prilepiť koľkokrát chce. Uvedomme si, že to zodpovedá číslam skladajúcim sa z cifier "1" a "2", ktorých ciferný súčet je deliteľný troma.

6. (1 bod) Hľadáme regulárny výraz akceptujúci čísla s ciferným súčtom deliteľným troma, ktoré môžu naviac obsahovať aj cifru "0". Napríklad teda reťazec "01200201".

7. (3 body) A pokúsme sa pridať aj zvyšné cifry. Hľadáme čísla s ciferným súčtom deliteľným trojkou, ktoré môžu obsahovať ľubovoľnú cifru "0" až "9".

8. (2 body) Regulárny výraz z podúlohy g) je takmer presne to čo hľadáme – čísla deliteľné tromi. Lebo práve tie majú ciferný súčet deliteľný tromi. Jediné, čo je naviac je, že dovoľujeme, aby číslo začínalo prebytočnými nulami. Pokúste sa opraviť tento nedostatok a vytvorte regulárny výraz, ktorý naozaj akceptuje iba čísla deliteľné troma.

V riešení týchto úloh neodovzdajte iba hľadaný regulárny výraz, ale vysvetlite, ako ste našli daný regulárny výraz a prečo vášmu regulárnemu výrazu zodpovedajú iba správne reťazce a žiadne iné.

Pomôcka

Existuje množstvo online nástrojov, kde si viete vyskúšať prácu s regulárnymi výrazmi a testovať riešenia tejto úlohy. Medzi ne patrí napríklad aj https://regex101.com/. Ak na tejto stránke napíšete do okienka “regular expression” svoju vzorku a do okienka “tesst string” nejaký text, stránka vo vami zadanom texte , ktorý zadanej vzorke zodpovedá. Vyskúšajte si napr. zadať vzorku "jabl(k|ck)o" a text "mak jablko jahoda". Ak si chcete vynútiť test, či celý zadaný text zodpovedá vašej vzorke, dopíšte na jej začiatok znak "^" a na jej koniec znak "$". Tieto dva špeciálne znaky predstavujú začiatok a koniec celého textu, v ktorom hľadáme.