Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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

Soutěž již skončila

Zadání

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

Výhra

Vítěz dostane placku Machr, pár samolepek a ocenění do portfolia.

Výhra

Výsledky

Jméno bodů Řešení ( Stáhnout vše )
tomisoka 90 Stáhnout řešení
pocitac770 85 Stáhnout řešení
dave_23 70 Stáhnout řešení
Aktivity
Avatar
Patrik Valkovič:22.2.2016 21:26

Kdo by měl zájem, zde jsou všechna testovací data: http://1drv.ms/1QW4Gy7
Nejsou tam složitější situace, ty se mi nechtělo vymýšlet.

Druhá otázka, měli byste zájem o miniseriál na tento konkrétní příklad? Praktickou implementaci?

Odpovědět
22.2.2016 21:26
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
tomisoka:22.2.2016 21:57

Aha, tak tím pádem jsem nepochopil co vše se bere jako stavový automat a odvolávát tu zmínku o nepřehlednosti.
K těm ^ $ jsem to ani zase tak nepitval a udělal jsem to tam jak jsem to pochopil z dřívějšího používání regexů. To by vysvětlovalo proč mi tyto znaky přišly jako skoro nepoužitelné...
Jinak názvy tříd mi přijdou celkem jasné, tak nevím.

 
Nahoru Odpovědět
22.2.2016 21:57
Avatar
Odpovídá na tomisoka
Patrik Valkovič:23.2.2016 18:24

Stavový automat je posloupnost stavů, které na sebe navazují. U tebe je stav třeba porovnání písmene. Pokud znak odpovídá, přechází se na další objekt, pokud ne, tak vrací 1 (konečný stav) a automat končí (v tomto případě nevalidním vstupem). Automat může být ještě rozvětvený (do jednoho stavu se lze dostat několika cestami), v takovém případě by si návrh, jak ho máš ty, s tím neporadil (to ale nebyl případ této úlohy).

Nahoru Odpovědět
23.2.2016 18:24
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 53.