Regulární výrazy , c# (Regex)

Bojlerik
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 16. 3. 2007 19:44

Regulární výrazy , c# (Regex)

Příspěvek od Bojlerik »

Neni tu náhoudou někdo, kdo má napsanej kód na jednoduchý vyhodnocovač regulárních výrazů v podobě konzolově orientované aplikace, vytvořený
na platformě .NET (v jazycích C# nebo Boo). Vím, že existuje fukce regex už v c# , ale ja ji potřebuju napsat sám :/ Všem, kteří poskytnou nějaký info moc díky
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Zdrojak mam, ale v Prologu :-). Hodne to zalezi na tom, co vsechno maji ty regularni vyrazy umet. Docela dost se da ale udelat s jednoduchou rekurzi. Jako zdrojak v C mam jen matchovani wildcardu ("*zd*.c" matchne s "nazdar.c"):

Kód: Vybrat vše

int match(char *pat, char *str)
{
	switch(*pat) {
	case '\0':  return !*str;
	case '*':   return match(pat+1, str) ||
				*str && match(pat, str+1);
	case '?':   return *str && match(pat+1, str+1);
	default:    return *pat == *str && match(pat+1, str+1);
	}
}
Naposledy upravil(a) Lukas Mach dne 17. 3. 2007 11:49, celkem upraveno 1 x.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Mno je to sice s kanonem na vrabecka, ale pripomel's mi material co jsem kdysi studoval: http://atrey.karlin.mff.cuni.cz/~0rfely ... zaver.html

treba ti to k necemu bude:D
Xerxes
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Typ studia: Informatika Bc.
Bydliště: Zlínský kraj / Kolej 17. listopadu
Kontaktovat uživatele:

Univerzální pattern matching

Příspěvek od Xerxes »

Omlouvám se za oživení starého tématu, ale doufám, že by to mohlo někomu pomoct. Všiml jsem si, že v zadání céčkovských zápočťáků často bývá nějaká forma grepu s různě silnými regulárními výrazy. Proto jsem si cvičně zkusil něco naimplementovat a napadlo mě toto:

Kód: Vybrat vše

// Struktura jedne polozky vzoru
struct TPattern
{
	int Min, Max;          // Minimalni a maximalni pocet vyskytu
	unsigned int Mask[8];  // Bitova maska povolenych znaku (256 bitu)
	struct TPattern *Next; // Dalsi polozka ve spojaku vzoru
};

// Vrati TRUE, pokud pasuje znak na polozku vzoru
// Pokud ch == 0, vraci vzdy FALSE kvuli detekci konce retezce
bool MatchChar(TPattern *pat, unsigned char ch)
{
	return ch && (pat->Mask[ch / 32] & (1 << (ch % 32)));
}

// Vrati TRUE, pokud retezec pasuje na zadany spojak vzoru
bool Match(TPattern *pat, const char *str)
{
	// Pokud vzor skoncil, uspesne se matchuje pouze konec retezce
	if(!pat)
		return *str == 0;

	// Napred musi pasovat prave Min znaku vzoru
	for(int i = 0; i < pat->Min; i++, str++)
		if(!MatchChar(pat, *str))
			return false;

	// Potom muze volitelne pasovat (Max - Min) znaku
	for(int i = pat->Min; i < pat->Max; i++, str++)
	{
		// Pokud by zbytek matchoval i bez volitelneho znaku, neni treba zkouset dal
		if(Match(pat->Next, str))
			return true;

		// Preskakovany volitelny znak musi byt zadaneho typu, jinak uz nic nenamatchujem
		if(!MatchChar(pat, *str))
			return false;
	}

	// Volitelne znaky preskoceny, matchuje zbytek?
	return Match(pat->Next, str);
}
Je to podle mého názoru docela jednoduchý, pochopitelný a snadno reprodukovatelný univerzální systém matchování vzorů. Zadaný řetězec matchuje se speciální strukturou, která je tvořena spojákem položek typu TPattern. Jedna polozka spojáku reprezentuje množinu povolených znaků a rozsah, kolikrát se může/musí v řetězci objevit. Doufám, že nic horšího (tedy nic, co by vyžadovalo silnější systém) se na zápočtech neobjeví.

Spoják vzorů je nutné vytvořit z původního řetězce vzoru. To už se zadání od zadání liší. Zde je pro ilustraci kód, který spoják vytvoří ze standardních wildcardů se speciálními znaky '*' a '?':

Kód: Vybrat vše

// Vytvori vzor matchujici zadany wildcard podle standardnich pravidel
TPattern *CompileWildcard(const char *wildcard)
{
	TPattern *first, *last;

	// Projde cely wildcard znak po znaku
	for(first = 0; *wildcard; wildcard++)
	{
		// Vytvori novou polozku vzoru
		TPattern *pat = new TPattern;
		memset(pat, 0, sizeof(TPattern));

		// Na zaklade znaku wildcardu vyplni polozku daty
		switch(*wildcard)
		{
		case '*':
			// Hvezdicka matchuje 0 az INT_MAX vyskytu jakehokoliv znaku
			pat->Min = 0;
			pat->Max = INT_MAX;
			memset(pat->Mask, 0xFF, 32);
			break;

		case '?':
			// Otaznik matchuje prave jeden vyskyt jakehokoliv znaku
			pat->Min = 1;
			pat->Max = 1;
			memset(pat->Mask, 0xFF, 32);
			break;

		default:
			// Cokoliv jineho matchuje prave jednou sebe sama
			pat->Min = 1;
			pat->Max = 1;
			pat->Mask[(unsigned char)*wildcard / 32] = (1 << ((unsigned char)*wildcard % 32));
		}
		
		// Zaradi polozku vzoru do spojaku
		if(!first)
		{
			first = pat;
			last = pat;
		}
		else
		{
			last->Next = pat;
			last = pat;
		}
	}

	// Vrati vytvoreny spojak
	return first;
}
Udělat takový spoják z něčeho se silnější syntaxí je sice pracnější, ale v zásadě nezáludné.

Díky za upozornění na případné chyby.

Poznámka: Poslední rekurze v Match() jde velmi jednoduše předělat na cyklus, ale takto mi to přijde pochopitelnější.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

neccheš to hodit na wiki.matfyz.cz?
Odpovědět

Zpět na „2006“