Zadanie
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").1
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é!
(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 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".(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 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".(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.
V skutočných regulárnych výrazoch môžeme samozrejme používať aj všetky ostatné znaky vrátane medzier. Našim obmedzením sa však vyhneme vysvetľovaniu mnohých technických detailov.↩
Podúloha a.
Vytvoriť telefónne číslo nie je ťažké. Stačí postupne naskladať všetko, čo bolo popísané v zadaní. Vieme, že čísla začínajú kombináciou "09", túto časť teda môžeme nechať tak, ako je. Nasleduje dvojčíslie udávajúce operátora. Jedna možnosť je pomocou "|" poskladať všetky možnosti. Vyzeralo by to takto: "05|06|07|08|15|16|17|18". Môžeme si to však skrátiť, ak si všimneme, že tieto čísla začínajú buď na "0" alebo "1" a pokračujú jednou z cifier "5", "6", "7" a "8". A ľubovoľné takto vzniknuté číslo je dobré. Dostávame teda regulárny výraz "(0|1)[5678]".
Nasleduje šesť ľubovoľných cifier. Jednu ľubovoľnú cifru spravíme jednoducho pomocou "[0-9]". Opakovať však vieme iba neurčitý počet krát. Ak chceme niečo zopakovať práve šesť krát, nezostáva nám nič iné, ako tento vzor nalepiť šesťkrát za sebou.
Výsledný regulárny výraz, ktorý akceptuje telefónne čísla je:
"09(0|1)[5678][0-9][0-9][0-9][0-9][0-9][0-9]".
Podúloha b.
Táto úloha je ešte jednoduchšia. Stačí si uvedomiť, že ak máme reťazec zložený iba z písmen "a" a tento počet je deliteľný tromi, tak tieto a-čka sa dajú rozdeliť do trojíc. Keď si teda zoberieme regulárny výraz, ktorý vyzerá ako "(aaa)*", dostaneme práve to, čo potrebujeme. Ak hviezdička zopakuje daný reťazec \(k\)-krát, výsledný reťazec bude mať \(3k\) a-čok. A hviezdička môže zopakovať reťazec ľubovoľne, aj nulakrát.
Podúloha c.
Máme vytvoriť regulárny výraz, ktorý akceptuje reťazce nepárnych dĺžok, ktoré sa skladajú iba z písmena "a". Keby bola úloha vytvoriť párne dlhé reťazce, použili by sme riešenie podobné podúlohe b. Dostali by sme regulárny výraz "(aa)*". No a získať z párnych reťazcov nepárne je jednoduché. Pridáme na koniec ešte jedno "a". Takže hľadaný regulárny výraz je "(aa)*a".
Podúloha d.
V tejto podúlohe bolo najdôležitejšie nezabudnúť na nejaké špeciálne prípady. Napríklad, reťazec zo samých "c" spĺňa podmienku zo zadania. Takisto reťazec, v ktorom sa nevyskytuje písmeno "b" je korektný. Je dobrým zvykom pozrieť sa na tieto špeciálne prípady a keď úlohu vyriešime, overiť si, že náš regulárny výraz funguje aj pre ne.
Každý výsledný reťazec si vieme rozdeliť na dve časti. Začiatočná časť, v ktorej sa nevyskytuje písmeno "b" a koncová časť, v ktorej sa nevyskytuje písmeno "a". Toto rozdelenie vyplýva z toho, že žiadne "b" nie je pred žiadnym "a".
Vytvoriť regulárny výraz pre prvú časť je jednoduché. Je to ľubovoľný reťazec, v ktorom sa nachádzajú iba písmená "a" a "c". Všetky takéto reťazce môžeme generovať tak, že začneme prázdnym slovom a postupne na koniec priliepame jedno z povolených písmen. A toto môžeme pomocou regulárnych výrazov zapísať ako "[ac]*" (rovnako dobré môže byť použitie "(a|c)*").
Rovnakým postupom vieme druhú časť generovať pomocou "[bc]*". Takže vo výslednom regulárnom výraze nám stačí tieto dva reťazce zreťaziť a dostaneme: "[ac]*[bc]*". Vidíme, že to naozaj generuje výrazy, kde sú všetky "a" pred "b". Teraz sa pozrime, či to spĺňa aj všetky špeciálne prípady, ktoré sme si spomenuli na začiatku. Vieme dostať reťazce tvorené iba písmenami "c". Proste sa nikdy nevyberie žiadne iné písmeno. Reťazce neobsahujúce "b" vzniknú tak, že druhá hviezdička sa nezopakuje ani raz. A naopak to platí pre reťazce neobsahujúce "a".
Podúloha e.
Táto podúloha bola samozrejme najťažšia. Postupne sa preto pustíme do jej riešenia. Keby sme mali úlohu, kde môžeme použiť iba písmená "a" a "b" a žiadne dve za sebou idúce písmená nemôžu byť rovnaké, úloha by sa výrazne zjednodušila. Tieto písmená by totiž museli ísť nastriedačku za sebou. To vieme dosiahnuť napríklad pomocou "(ab)*". Problém ale je, že toto nepokrýva všetky možnosti. Všetky tieto reťazce totiž začínajú na "a" a končia na "b". My však potrebujeme rátať aj s takými, ktoré začínajú na "b" alebo končia na "a". Na začiatok teda možno pridáme "a" a na koniec možno pridáme "b". Na niečo také nám predsa slúži znak "?". Dostaneme teda regulárny výraz "b?(ab)*a?".
Teraz však do toho potrebujeme pridať ešte písmená "c". Zoberme si ľubovoľný platný reťazec, ktorý môže obsahovať všetky tri písmená a žiadne dve za sebou idúce písmená nie sú rovnaké. Pozrime sa teraz na všetky výskyty písmena "c". Uvedomme si, že medzi dvoma za sebou idúcimi c-čkami v reťazci je neprázdny reťazec, ktorý obsahuje iba písmená "a" a "b" a žiadne dve za sebou idúce písmená nie sú rovnaké. A to je predsa úloha, ktorú sme už riešili v predchádzajúcom odseku.
Teda takmer. V predchádzajúcom riešení sme dovoľovali, aby vzniknutý reťazec bol aj prázdny, v tomto prípade to však tak nemôže byť. Upravme teda regulárny výraz "b?(ab)*a?" tak, aby akceptoval iba neprázdne reťazce z "a" a "b", kde žiadne dve za sebou idúce písmená nie sú rovnaké. Ak chceme, aby boli tieto reťazce neprázdne, musíme zaručiť, že sa vytvorí aspoň jeden znak. Napríklad ten prvý. Ak by tento reťazec začínal na písmeno "b", môže za ním nasledovať ľubovoľne veľa (aj nula) dvojíc "ab" a následne sa možno skončí na "a". Takému niečomu zodpovedá regulárny výraz "a(ba)*b?". No a ak tento reťazec začína na "b", tak za ním nasleduje ľubovoľne veľa dvojíc "ab" a na konci je možno ešte "a". Teda máme regulárny výraz "b(ab)*a?". A aby som generoval všetky reťazce, ktorým vyhovuje prvý alebo druhý spomenutý regulárny výraz, spojím ich pomocou "|". Výsledný výraz bude teda "(a(ba)*b?)|(b(ab)*a?)".
Práve vytvorený regulárny výraz budeme často potrebovať v našom ďalšom postupe. Označme si ho teda veľkým písmenom "F". Keď teraz v regulárnom výraze napíšem "F", znamená to, že tam chcem vložiť celý výraz "(a(ba)*b?)|(b(ab)*a?)". Ako teraz vyzerajú všetky reťazce prvých troch písmen abecedy, kde sa žiadne dve za sebou idúce neopakujú?
Tak ako v predchádzajúcom riešení, rozoberieme si dve možnosti. Môžeme začať písmenom "c". Po ňom bude nasledovať nejaká dobrá postupnosť a-čok a b-čok, opäť "c" atď, až kým to neskončí buď na tom c-čku alebo ešte jednou postupnosťou a-čok a b-čok. Toto zapíšeme ako "c(Fc)*F?". Alebo začnem nejakými a-čkami alebo b-čkami, potom pôjde "c", opäť "a" a "b" atď, a na koniec sa možno ešte pridá jedno "c". To nám dá regulárny výraz "F(cF)*c?". Tým sme rozobrali všetky možnosti ako môže dané slovo vyzerať. Jediné čo nám uniká je prázdny reťazec. Ten však vieme pridať veľmi jednoducho tak, že na koniec pridáme ešte jednu "|", za ktorou už nebude nič – teda prázdny reťazec. Dostaneme "(c(Fc)*F?)|(F(cF)*c?)|".
A ak to rozpíšeme poriadne (a každé "F" ešte dáme do zátvorky a pre prehľadnosť to dáme do dvoch riadkov):
"(c(((a(ba)*b?)|(b(ab)*a?))c)*((a(ba)*b?)|(b(ab)*a?))?)|
(((a(ba)*b?)|(b(ab)*a?))(c((a(ba)*b?)|(b(ab)*a?)))*c?)|"Nepôsobí to síce najkrajšie a dajú sa vymyslieť aj mierne jednoduchšie výrazy1, napríklad: "b?(ab)*a?(c((a(ba)*b?)|(b(ab)*a?)))*c?", ale je pomerne jednoduché naň prísť.
Môžete sa zamyslieť, ako vznikol tento konkrétny. Všimnite si, že obsahuje časti spomínané v tomto vzorovom riešení, akurát ich naskladá šikovnejšie.↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.