2. Praktické regulárne výrazy

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

Každý z nás pri práci s počítačom občas hľadá nejaký text – či už je to na webstránke alebo v dokumente. Častokrát stačí, ak stlačíme Ctrl+F, napíšeme hľadaný výraz a program nám nájde všetky jeho výskyty. Ak však potrebujeme vyhľadať viacero synoným toho istého slova, všetky mená začínajúce veľkým písmenom a končiace na "ka" alebo platnú e-mailovú adresu, bežné nástroje prestávajú stačiť. Vtedy môžeme siahnuť po regulárnych výrazoch.

Regulárne výrazy patria medzi najpoužívanejšie nástroje na vyhľadávanie v texte. V tomto zadaní si popíšeme základy ich tvorby postačujúce na riešenie súťažných úloh. Pokojne si toho ale o regulárnych výrazoch prečítajte aj viac, takmer určite sa vám získané vedomosti ešte budú hodiť praxi.

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 seba, 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, vrátane 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. (3 body) Napíšte vzorku, ktorej zodpovedajú slovenské mobilné čísla patriace operátorovi Pomaranč. Slovenské telefónne čísla majú 10 cifier. Prvé dve sú čísla "09" nasledované ďalšou dvojicou, ktorá udáva operátora (do úvahy neberieme prenesené čísla). Sieť Pomaranč používa nasledovné dvojice: "05", "06", "07", "08", "15", "16", "17" a "18". Zvyšných 6 cifier môže byť ľubovoľných.

2. (2 body) Napíšte vzorku, ktorej zodpovedajú iba reťazce skladajúce sa z písmena "a" a dĺžka tohto reťazca je deliteľná tromi. To znamená, že má prijímať reťazce ako "aaaaaa" alebo "" (prázdny reťazec o dĺžke 0), ale nemá prijímať reťazce ako "aaaa".

3. (2 body) Napíšte vzorku, ktorej zodpovedajú iba reťazce skladajúce sa z písmena "a" a dĺžka tohto reťazca je nepárna.

4. (4 body) Napíšte vzorku, ktorej zodpovedajú iba reťazce zložené z písmen "a", "b" a "c", pričom všetky písmená "a" sa v reťazci nachádzajú pred všetkými písmenami "b".

5. (4 body) Napíšte vzorku, ktorej zodpovedajú iba reťazce zložené z písmen "a", "b" a "c" a žiadne dve za sebou idúce písmená reťazca nie sú rovnaké.

V riešení týchto úloh neodovzdaj iba hľadaný regulárny výraz, ale vysvetli, ako si našiel daný regulárny výraz a prečo tvojmu 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 “test 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.