Čtěte prosím tuto stránku celou a pozorně.

Zadání

Napište program grep, který vybere jen ty řádky vstupního souboru, které odpovídají zadanému regulárnímu výrazu a tyto řádky zapíše do výstupního souboru.

Regulární výraz je speciální řetězec, který se skládá z normálnách znaků 'a'..'z', 'A'..'Z', '0'..'9' a speciálních znaků '?', '(', ')', '*', '{', '}', '|'. Každý regulární výraz odpovídá množině řetězců.

Znak '?' odpovídá jednomu libovolnému znaku.

Část výrazu, která je ohraničena kulatými závorkami a následována hvězdičkou, odpovídá libovolnému (i nulovému) počtu opakování výrazu v závorce.

Část výrazu, která je ohraničena množinovými závorkami odpovídá několika variantám, které jsou uvnitř závorek odděleny znakem '|'.

Příklady:

Regulární výraz	Obyčejný řetězec	Odpovídá ?
AAA	AAA	Ano
AA	AAA	Ne
AA	aa	Ne
A?A	AbA	Ano
A?A	AbbA	Ne
?AA	AA	Ne
(Ab)*	AbAbAb	Ano
()*AA	AA	Ano
()*bAA	AA	Ne
A(?)*B	AahojB	Ano
A()*B	AB	Ano
Zacatek{Ahoj|Nazdar}Konec	ZacatekAhojKonec	Ano
Zacatek{Ahoj|Nazdar}Konec	ZacatekAhojNazdarKonec	Ne
X{A|}Y	XY	Ano
X({A|B})*Y	XBABAY	Ano

Jak je vidět z příkladů v tabulce, jednotlivé speciální prvky mohou být vnořené do sebe.

Formát vstupu a výstupu

Program bude mít na vstupu dva soubory: vyraz.txt a vstup.txt.

Vstupní soubor vyraz.txt má na jediném prvním řádku regulární výraz. Tento výraz není delší než 50 znaků a je vždy korektní.

Vstupní soubor vstup.txt obsahuje řetězce, které se mají porovnat s regulárním výrazem. Na každém řádku je umístěný jeden řetězec. Žádný řádek není delší než 255 znaků.

Výstupní soubor vystup.txt by měl po skončení programu obsahovat právě ty řádky ze vstupního souboru, které odpovídají regulárnímu výrazu.

Ukázkové vstupní a výstupní soubory si můžete stáhnout zde: data.tar.gz, nebo zde: data.zip.

Soubory ve formátu .tar lze rozbalit například Total Commanderem, nebo pomocí programu tar.exe příkazem "C:\>tar.exe xvf data.tar". Více informací o použití programu tar najdete zde.

Algoritmus

Algoritmus spočívá v postupném procházení řetězce a regulárního výrazu. V řetězci i ve výrazu budeme pozici značit tečkou. Narozdíl od řetězce může být v regulárním výrazu více pozic, které jsou dosažitelné pomocí určitého počátečního úseku řetězce. Například:

{LAM.INO|LAM.A}		LAM.ANI

Vlevo je regulární výraz a vpravo je řetězec.

Základní krok algoritmu spočívá v posunutí tečky v řetězci o jeden znak. Během základního kroku je také potřeba odpovídajícím způsobem "posunout" tečky v regulárním výrazu. Každá tečka regulárního výrazu se může buď obyčejně posunout, nebo rozmnožit, anebo může zaniknout. Algoritmus je zkonstruovaný tak, aby po dokončení každého základního kroku byly všechny tečky ve výrazu buď před obyčejným písmenem, nebo před otazníkem, nebo na konci řetězce.

Příklady:

{L.AMINO|L.AMA}		L.AMANI
{LA.MINO|LA.MA}		LA.MANI

X.X{A|B|C}Y		X.XZ
XX{.A|.B|.C}Y		XX.Z

{A.BX|A.CX}			A.BX
{AB.X|ACX}			AB.X

Jak určit "posunutí" teček regulárního výrazu

Posunutí teček v regulárním výrazu není zcela triviální. Opět je potřeba manipulovat s tečkami, dokud nejsou všechny tečky před nějakým písmenem, nebo otazníkem. Aby se předešlo zacyklení, je potřeba označit křížkem pozice, které už byly označeny tečkou. Na pozici označenou křížkem se už tečka nikdy neumísťuje. Algoritmus probíhá podle následujícího schématu:

1. Pro každou tečku nejprve proveď toto: Je-li za tečkou otazník, pak ji posuň o jeden znak vpravo. Je-li za tečkou písmeno, které se zrovna přeskakuje v řetězci, pak také posuň tečku vpravo. Je-li za tečkou jiné písmeno, než právě přeskakované, pak tečku vymaž. Je-li tečka na konci, tak ji vymaž. V tomto kroku se žádné křížky nepřidávají.
2. Jsou-li všechny tečky před písmenem, nebo otazníkem, nebo na konci, pak pokračuj krokem 6., jinak pokračuj následujícím krokem.
3. Vyber si libovolnou tečku, která není před písmenem či otazníkem a není na konci.
4. Tuto tečku nahraď křížkem a umísti nové tečky podle níže uvedených instrukcí pro jednotlivé případy. Pokud tyto instrukce vedou k umístění tečky na pozici označenou křížkem, pak tečku neumísťuj (příslušnou část instrukce ignoruj).
   1. Byla-li tečka před kulatou závorkou (je jedno jakou), pak ji rozdvoj. První z dvojice umísti za levou závorku, druhou umísti za hvězdičku za pravou závorkou.
   2. Byla-li tečka před levou složenou závorkou, pak ji rozmnož. Jednu její kopii umísti za levou složenou závorku, další kopie umísti za každý znak '|', který přísluší dané levé složené závorce.
   3. Byla-li tečka před znakem '|', pak ji posuň za příslušnou pravou složenou závorku.
   4. Byla-li tečka před pravou složenou závorkou, pak ji posuň o jeden znak vpravo.
5. Pokračuj krokem 2.
6. Smaž všechny křížky.

Příklad:

.A({{}|(?)*})*.A
A.({{}|(?)*})*A.
A+(.{{}|(?)*})*.A.
A+(.{{}|(?)*})*.A.
A+(+{.{}|.(?)*})*.A.
A+(+{+{.}|.(?)*})*.A.
A+(+{+{+}.|.(?)*})*.A.
A+(+{+{+}+|.(?)*}.)*.A.
A+(+{+{+}+|+(.?)*.}.)*.A.
A+(+{+{+}+|+(.?)*+}.)*.A.
A+(+{+{+}+|+(.?)*+}+)*.A.
A+(+{+{+}+|+(.?)*+}+)*.A.
A({{}|(.?)*})*.A.

Posunutí teček je možné na začátku programu spočítat pro každou pozici zvlášť a do tabulky poznamenat pro každou pozici seznam pozic na které tečka přejde. V dalším průběhu algoritmu je možné používat jen tuto tabulku.

Celkový algoritmus

1. Umísti právě jednu tečku na začátek řetězce (před první písmeno, pokud existuje).
2. Umísti právě jednu tečku na začátek regulárního výrazu (klidně i před závorku) a proveď "posunutí teček" v regulárním výrazu.
3. Je-li tečka na konci řetězce, tak skonči (řetězec odpovídá regulárnímu výrazu právě když je tečka na konci regulárního výrazu). Není-li tečka na konci řetězce, tak pokračuj dalším krokem.
4. Posuň tečku o jedno písmeno v řetězci, proveď "posunutí teček" v regulárním výrazu. Tento bod odpovídá základnímu kroku.
5. Pokračuj krokem 3.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program by kromě vstupních textových souborů neměl požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - grep a s přiloženým souborem grep.pas.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 8.11.2005.
Termín odevzdání: do 20.11.2005 včetně.
Termín odevzdání oprav: do 27.11.2005 včetně.