2. Praktické regulárne výrazy 2 vzorové riešenie

Podúloha a)

Prvou podúlohou bolo napísať regulárny výraz, ktorý akceptuje všetky reťazce predstavujúce čísla deliteľné \(5\). Vieme, že číslom 5 sú deliteľné tie čísla, ktoré majú na konci cifru "0" alebo "5". Podľa zadania si však máme dať pozor na to, aby nami akceptované čísla nemali na začiatku zbytočné nuly. Môžeme napísať regulárny výraz, ktorý bude mať na prvom mieste nenulovú cifru, za ktorou bude nasledovať niekoľko ľubovoľných cifier a následne cifra 0 alebo 5. Tento výraz vyzerá takto: "[1-9][0-9]*[05]".

Samozrejme, takýto výraz neakceptuje dve výnimky – číslo 0 a číslo 5. Tieto pridáme pomocou "|", takže výsledný regulárny výraz má tvar "([1-9][0-9]*[05])|0|5".

Delenie číslom 5 bolo ľahké. Museli sme sa trochu pohrať s nulami na začiatku, ale inak nám stačilo splniť jedinú podmienku – 0 alebo 5 na konci čísla. Aj pre čísla deliteľné 3 platí jednoduchá podmienka: ciferný súčet týchto čísel musí byť deliteľné troma. Takáto podmienka sa však nedá zapísať pomocou regulárnych výrazov takým jednoduchým spôsobom. Nasledujúce podúlohy preto slúžili na to, aby sme postupne mohli vytvárať finálne riešenie.

Podúloha b)

V tejto podúlohe bolo treba napísať regulárny výraz, ktorý obsahuje iba cifry 1 a 2 predstavujúce chodenie po schodoch. Má pritom platiť, že tento regulárny výraz popisuje všetky cesty na schod vyšší ako šiesty, ktoré nestúpia na schod 3 ani na schod 6.

Keď zlodej stojí na schode číslo 0 (teda na spodku schodišťa), má dve možnosti. Buď spraví krok dĺžky 1 alebo dĺžky 2. Pozrime sa, čo sa stane ak najskôr spraví krok dĺžky 1. Týmto krokom sa dostane na schod 1, z ktorého ale nemôže spraviť krok dlhý 2, lebo by sa dostal na zalepidlovaný schod 3. Musí teda spraviť krok dĺžky 1, čím sa ocitne na schode číslo 2. Následne musí prekročiť schod 3 pomocou dlhšieho kroku dĺžky 2, čím sa dostane na schod 4. Odtiaľ má opäť iba jednu možnosť, krok dĺžky 1, lebo dlhším krokom by sa ocitol na schode 6. No a z piateho schodu musí spraviť krok dĺžky 2, aby prekročil zalepidlovaný schod. V tomto momente už pred ním nie sú žiadne zalepené schody a môže pokračovať ľubovoľne. Tento postup vieme zapísať ako regulárny výraz "11212[12]*".

Čo ak sa však na začiatku rozhodne spraviť krok dĺžky 2? Ocitne sa na schode 2, čo znamená, že opäť musí spraviť krok dĺžky 2, aby prekročil schod 3. Tak ako predtým, keď sa ocitol na schode 4, musí spraviť krok dĺžky 1 a potom dĺžky 2. Tým sa dostane na schod 7, odkiaľ je to opäť bezpečné. Tento postup popisuje regulárny výraz "2212[12]*".

Vidíme, že kým sa zlodej dostal na siedmy schod, rozhodoval sa iba na úplnom začiatku a zvyšok cesty bol presne určený. Výsledný regulárny výraz teda dostaneme spojením týchto dvoch regulárnych výrazov, čo vieme urobiť napríklad tak, že ich oddelíme "|". Ak sa však trochu zamyslíme, nájdeme aj kratší spôsob: "(11|2)212[12]*".

Podúloha c)

Všimnime si, že v podúlohe b) sme mali na výber len na úplnom začiatku, keď sme boli na schode číslo 0 a potom až keď sme sa dostali na schod 7, kde už neboli žiadne schody potreté lepidlom. Uvedomme si, že schody môžeme rozdeliť na tri skupiny podľa toho, či ich číslo dáva po delení 3 zvyšok 0, 1 alebo 2.

Takisto si všimnime, že ak stojíme na schode, ktorého zvyšok po delení 3 je 1, tak nemôžeme spraviť krok dĺžky 2, lebo by sme sa dostali na schod pokrytý lepidlom. Musíme teda spraviť krok dĺžky 1, čím sa dostaneme na schod, ktorého zvyšok po delení 3 je 2. Ak stojíme na schode so zvyškom 2, musíme spraviť krok dĺžky 2, ktorým sa dostaneme na schod so zvyškom 1.

Ak teda ako prvý spravíme krok dlžky 1, následne budeme musieť striedavo robiť kroky dlžky 1 a 2, lebo iba tak nikdy nestúpime na schod deliteľný číslom 3. Ak ako prvý spravíme krok dlžky 2, budeme musieť dookola opakovať postupnosť krokov 2 a 1. Toto vieme ľahko zapísať pomocou regulárneho výrazu ako "1(12)*1?|2(21)*2?". Na koniec každej časti sme museli pridať ešte jeden znak s otáznikom, aby reťazce začínajúce na 1 mohli končiť 1 a reťazce začínajúce 2 mohli končiť 2. Bez nich by sme napríklad neakceptovali reťazec "11" alebo "2212", ktoré sú oba správne.

Otázkou je, či by náš regulárny výraz mal akceptovať aj prádzny reťazec. Zo zadania to nie je úplne jasné¹. Môžeme sa teda dohodnúť, že prázdny reťazec za cestu považovať nebudeme. Ak by sme ho tam veľmi chceli mať, ľahko ho môžeme pridať jedným or-om.

Podúloha d)

V tejto podúlohe máme napísať regulárny výraz, ktorý zodpovedá tomu, že zlodeji nejakú dobu kráčali po schodoch a potom stúpili na schod deliteľný 3, prilepili sa a ostali stáť. Všimnime si, že táto podúloha silno súvisí s podúlohou c). Keďže sa zlodeji nemohli prilepiť počas cesty, museli sa nejakú dobu vyhýbať schodom s lepidlom až kým to potom na konci nepokazili. A časť ich cesty, kým sa polepeným schodom úspešne vyhýbali, predsa popisuje regulárny výraz z podúlohy c).

Ostáva zistiť, čo musí zlodej spraviť, aby stúpil na schod, ktorého číslo je deliteľné 3. Ak stojí na schode, ktorého zvyšok po delení 3 je 1, tak ak spraví kroky "11" alebo "2", skončí na schode s lepidlom. Ak schod, na ktorom stojí má zvyšok 2, tak sa zalepí ak spraví krok "1". Predstavme si, že zlodej išiel najskôr podľa regulárneho výrazu "1(12)*". Ocitol sa teda na schode so zvyškom 1 a preto musel spraviť buď postupnosť "11" alebo "2". Ak išiel najskôr podľa "2(21)*" tak sa ocitol na schode so zvyškom 2 a teda musel spraviť krok "1".

V podúlohe c) sme však museli pridať aj reťazce "1?" a "2?" aby sme ošetrili všetky možnosti. A tu ich tiež istým spôsobom potrebujeme. V prvom prípade to nemusíme riešiť, lebo ak zlodej po ceste typu "1(12)*" spraví ešte na konci krok 1, tak potom musí spraviť opäť krok 1 aby sa prilepil, čo sme pokryli v možnosti "1(12)*11". V druhom prípade však neriešime situáciu, ak zlodej po ceste typu "2(21)*" urobil krok 2 a potom sa chce prilepiť. Okrem možnosti "1" teda musíme za "2(21)*" pridať aj možnosť "22", ktorá zodpovedá presne tomuto prípadu. Spojením tohto všetkého dostaneme regulárny výraz "1(12)*(11|2)|2(21)*(1|22)".

Podúloha e)

Asi najľahšia podúloha, ak sme vyriešili podúlohu d). Ak sa zlodej prilepí, musí sa mu to stať na schode deliteľnom troma. Ak si teda vyzuje ponožky a pokračuje ďalej, je to to isté, ako keby začínal na schode 0 (ktorý je tiež deliteľný 3). Takže celá jeho cesta je len viacero ciest, pri ktorých sa vyhýba schodom deliteľným 3, až kým sa nenalepí a potom začína akoby odznova. Toto vieme docieliť pridaním "*" na koniec výrazu z podúlohy d), teda "(1(12)*(11|2)|2(21)*(1|22))*". Takto sme povolili aj prázdny reťazec. Ak by sme ho chceli zakázať, môžeme riešenie podúlohy d) zopakovať dvakrát a "*" dať iba za druhé opakovanie.

Podúloha f)

Ak zlodej zostane chvíľu stáť na mieste, nič sa na jeho situácii nezmení. Ak by sme odstránili nuly zo vstupného reťazca, musíme dostať reťazec, ktorý je vhodný pre podúlohu e). To znamená, že chceme robiť to isté, čo v podúlohe e) akurát hocikde môžeme pridať ľubovoľne veľa núl. Pridanie ľubovoľného množstva núl nám zabezpečí reťazec "0*" a jediné čo potrebujeme spraviť, je vložiť ho na všetky možné miesta reťazca z podúlohy e).

Je tu však ešte jeden háčik. Až po podúlohu d) sme státie na schode 0 (teda prázdny reťazec) netolerovali, teraz by sme však chceli akceptovať aj reťazce zložené iba zo samých núl. Preto na koniec nášho výrazu pridáme ešte "|0*".

Výsledok vyzerá trochu neprehľadne, ale uvedomte si, že je to naozaj len riešenie z podúlohy e) s množstvom núl, ktoré nič nerobia (a pridaným špeciálnym prípadom na konci). Možno by sme vedeli nejaké nuly ušetriť, keby sme náš regulárny výraz poriadne rozanalyzovali, jednoduchšie a bezpečnejšie však bude vložiť "0*" medzi každé dva znaky.

"(0*10*(0*10*20*)*(0*10*10*|0*20*)|0*20*(0*20*10*)*(0*10*|0*20*20*))*|0*"

Podúloha g)

Táto podúloha vyzerá na prvý pohľad najodstrašujúcejšie. Bolo ťažké poradiť si s ciframi 0, 1 a 2 a zrazu nám pribudne ďalších sedem. Budeme musieť urobiť tú istú úvahu celú od začiatku, akurát s toľkými rôznymi možnosťami? Našťastie nie.

Pozrime sa napríklad na cifru 3. Ak stojíme na zalepenom schode a posunieme sa o tri schody vyššie, opäť sa ocitneme na schode pokrytom lepidlom. Čo je v podstate to isté, ako keby sme zostali stáť na mieste. Áno, posunuli sme sa o tri schody vyššie, ale nás väčšinou nezaujíma ako vysoko sme, len to, kde pred nami sú ďalšie zalepené schody, poprípade to, aký zvyšok po delení 3 dáva schod na ktorom stojíme. A toto sa pri cifre 3 nemení.

Skúsme na to hľadieť nie cez schody, ale cez čísla. Hľadali sme čísla, ktorých ciferný súčet je deliteľný troma. Pridanie ľubovoľného množstva cifier 3 nám síce zmení ciferný súčet, ale nie jeho deliteľnosť číslom 3. Cifra 3 sa preto správa úplne rovnako ako cifra 0. Môžeme ju dať kam len chceme a koľkokrát len chceme. A toto isté platí aj pre cifry 6 a 9, ktoré sú tiež deliteľné troma.

Teraz snáď už začínate tušiť, ako to bude pokračovať. Ak si zoberieme cifru 4, použitie tejto cifry má na zvyšok po delení 3 rovnaký efekt, ako použitie cifry 1. A takisto cifra 7 má rovnaký efekt. To znamená, že tieto cifry sú navzájom zameniteľné. Všade, kde sme v pôvodnom regulárnom výraze použili cifru 1, môžeme teraz použiť cifry 4 alebo 7 bez toho, aby sa čokoľvek pokazilo. No a samozrejme, cifry 5 a 8 sú rovnaké ako cifra 2.

Dostať regulárny výraz, pre podúlohu g) je potom vskutku jednododuché. Zoberieme si výraz z podúlohy f) a každý výskyt "0" nahradíme "[0369]", každý výskyt "1" nahradíme "[147]" a každý výskt "2" nahradíme "[258]". To boli totiž skupiny rovnako sa správajúcich cifier, pri ktorých je jedno, ktorú z nich použijeme.

Výsledný reťazec je už taký dlhý, že sme ho museli rozdeliť do viacerých riadkov. Opäť to však nie je nič strašné, ak si uvedomíme, akým spôsobom vznikol.

"([0369]*[147][0369]*([0369]*[147][0369]*[258][0369]*)*
([0369]*[147][0369]*[147][0369]*|[0369]*[258][0369]*)|
[0369]*[258][0369]*([0369]*[258][0369]*[147][0369]*)*
([0369]*[147][0369]*|[0369]*[258][0369]*[258][0369]*))*|
[0369]*"

Podúloha h)

Zostáva už len odstrániť prebytočné nuly na začiatku. Našťastie, toto sa dá urobiť pomerne jednoducho. Najprv úplne zakážeme, aby na začiatku čísla bola ktorákoľvek z cifier 0, 3, 6, 9. To urobíme tak, že zmažeme "|[0369]*" z konca výrazu a v oboch možnostiach veľkého or-u zmažeme zo začiatku "[0369]*".

Tu by mohol vzniknúť problém, keďže veľký or sa v reťazci môže opakovať a my chceme zmazať "[0369]*" iba zo začiatku prvého opakovania. Našťastie pre nás, aj na konci každej možnosti nášho veľkého or-u máme "[0369]*". O tom, čo je na začiatku druhého opakovania, teda môžeme prehlásiť, že je to v skutočnosti ešte na konci prvého opakovania. To znamená, že náš upravený výraz naozaj robí to, čo pôvodné riešenie podúlohy g), akurát nedovoľuje, aby číslo začínalo niektorou z cifier 0, 3, 6, 9.

Teraz naspäť povolíme, aby reťazec začínal niekoľkými (možno žiadnymi) ciframi 0, 3, 6 alebo 9, pričom ale prvá nemôže byť nula. Tomu zodpovedá regulárny výraz "[369][0369]*|", ktorý (v zátvorke) stačí napísať pred zvyšok nášho výrazu. Nakoniec ešte musíme pridať jeden špeciálny prípad – samotné číslo 0.

"([369][0369]*|)
([147][0369]*([0369]*[147][0369]*[258][0369]*)*
([0369]*[147][0369]*[147][0369]*|[0369]*[258][0369]*)|
[258][0369]*([0369]*[258][0369]*[147][0369]*)*
([0369]*[147][0369]*|[0369]*[258][0369]*[258][0369]*))*|0"