Fórum studentů MFF UK

neccheš to hodit na wiki.matfyz.cz?

// 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);
}

// 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;
}

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 [i]grepu[/i] s různě silnými regulárními výrazy. Proto jsem si cvičně zkusil něco naimplementovat a napadlo mě toto:

[code]// 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);
}
[/code]
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 [i]wildcardů[/i] se speciálními znaky '*' a '?':

[code]// 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;
}
[/code]
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ší.

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

treba ti to k necemu bude:D

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);
	}
}

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"):

[code]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);
}
}[/code]

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