Soutěž: Machr na algoritmy - Regulární výrazy

V dnešním machrovi si zkusíme implementovat funkcionalitu, kterou využíváme téměř v každé aplikaci. Budou to regulární výrazy. Regulární výraz je sekvence znaků, podle kterých vyhledáváme v zadaném textu shodu.

Rozhraní

Pogram dostane na standardním vstupu zadaný text ukončený znakem nového řádku. Dále dostane regulární výraz, opět ukončený znakem nového řádku. Program vrací hodnotu 0, jestliže byla nalezena shoda. V případě, že shoda nalezena nebyla, program vrátí hodnotu 1. Jestliže regulární výraz nebude validní, program vrátí hodnotu 2. To jsou případy, kdy bude obsahovat znaky, které nemají žádný význam, nebo formát regulárního výrazu nebude správný (například nebude ukončena závorka). Na standardní výstup program nic nevypisuje, pouze vrátí návratový kód.

Implementace

Regulární výrazy budou rozděleny do několika kategorií. Doporučuji implementovat funkcionalitu postupně, jak je vypsána.

• Pouze jednotlivé znaky. Prakticky se kontroluje pouze to, zda je vzor totožný s textem. Text i vzor bude obsahovat pouze číslice, malé a velké písmena bez diakritiky a mezeru. To platí pro všechny následující body. Pokud bude ve vzoru nebo textu znak, který do této skupiny nepatří (například "č"), program vrátí hodnotu 2.
• Vzor bude obsahovat množiny, které se zapisují mezi hranaté závorky. Například pro vzor [agt] je shoda v řetězci, který obsahuje pouze jeden ze znaků "a", "g", "t". Jestliže nebude hranatá závorka ukončena, program vrátí hodnotu 2.
• Vzor bude obsahovat operátory, kontrolující počet výskytů předchozího znaku. Je to znak * (předchozí znak se nemusí vyskytovat, nebo se může libovolně opakovat), + (předchozí znak se musí vyskytovat minimálně jednou) a znak ? (předchozí znak se nemusí vyskytovat, nebo se vyskytuje právě jednou).
• Množiny můžou být zapsány i rozpětím. Tedy [a-z] jsou všechna malá písmena, [a-zA-Z] jsou všechna písmena, [0-9] jsou všechny číslice. Kromě toho lze množinu zadat speciálním tvarem [:alpha:] pro všechna písmena, [:upper:] pro velká písmena, [:lower:] pro malá písmena, [:num:] pro číslice a [:alnum:] pro všechny znaky kromě mezery.
• Do tohoto bodu musel regulární výraz pojmout celý text. To je důležité. V dalším kroku se bude kontrolovat, jestli bude nalezen regulární výraz kdekoliv v textu. Při prvním výskytu se program ukončí a vrátí hodnotu 0.
• Předposlední varianta přidává znak "^" do množin a obrací význam. Jestliže [abc] pasuje na text, který obsahuje "a", "b" nebo "c", [^abc] pasuje na text, který obsahuje libovolný znak kromě "a" "b" nebo "c".
• V poslední iteraci program bude umět zpracovat znak "^" mimo množinu (značí začátek slova) a znak "$" (značí konec slova). Například regulární výraz "^aha" vrátí 0 (úspěch) pro slovo "aha", ale 1 (neúspěch) pro slovo "dlaha".

Hodnocení
Jsou povoleny jazyky C++, C#, Java a PHP. Další jazyky po domluvě.
Bude samozřejmě hodnocena funkcionalita, ale i kvalita kódu!

Nakonec bych chtěl napsat pár rad pro snadnější implementaci.

• Dodržte rozhraní. Program nemá výstup, vrací pouze návratový kód, do konzole nic nevypisujte.
• Regulární výrazy se zpravidla řeší konečným stavovým automatem. Jeden zdroj můžete najít na Itnetwork. Kromě toho je na internetu spousta materiálu k tomuto tématu.

EDIT: Pro úspěšné řešení je nutné mít řešení otestované! V odevzdaném řešení tedy musí být i projekt s testy.

Níže uvedené příklady předpokládají kompletně splněné zadání. nejdřív je uveden vzor, poté text.

"Petr" "Vcera jsem byl s Petrou"
"[a-z]k" "trakar"
"vr+" "vrrrrr" i "vratnice" ale ne "vana"
"vr?a" "vrah" i "vana" ale ne "vrrrrr"
"m[^h-z]" "mazat", ale ne "umucit"
"^stre" "na strese" ale ne "prostredi"
"[a-zA-Z0-9 ]*" vyhovuje všemu