Porównywanie łańcuchów

0

Witam jestem raczej początkujący jeśli chodzi o programowanie. Mam do napisania funkcję która ustala zgodność wzorca z łańcuchem. Znak ’ ?’ we wzorcu oznacza zgodność z dowolnym innym znakiem. Znak ’’ oznacza zgodność z dowolnym, również pustym, ciągiem znaków w łańcuchu. Znak różny od ’ ?’ i ’’ oznacza zgodność tylko z samym sobą.
Próbowałem napisać to w taki sposób:

Bool match(char* model, char* string)
{
	int model_lenght = strlen(model);
	int string_lenght = strlen(string);

	while(model_lenght>0 && string_lenght>0)
	{
		if((model[model_lenght-1]==string[string_lenght-1])||(model[model_lenght-1]=='?')||(string[string_lenght]=='?'))
		{
			model_lenght--;
			string_lenght--;
		}
		else
			if(model[model_lenght-1]=='*')
			{
				model_lenght--;
				string_lenght=model_lenght;
			}
			else
				if(string[string_lenght-1]=='*')
				{
					string_lenght--;
					model_lenght=string_lenght;
				}
				else
					return 0;
	}

	if(model_lenght==0 && string_lenght==0)
		return 1;
	else
		return 0;
}

Ale niestety nie działa prawidłowo dla '*'. Szczerze nie mam pomysłu jak ten algorytm ma działać w przypadku gwiazdki :(

0
bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {
        if (*pattern == '*')
        {
            matchAny = true;
            ++pattern;
        }

        char curr = *str++;
        if (!curr)
        {
            return !*pattern;
        }

        if (*pattern == curr)
        {
            matchAny = false;
            ++pattern;
        }
        else if (!matchAny)
        {
            return false;
        }
    } 
}

Zadanie domowe:

  1. Dopisz obsluge wielu gwiazdek pod rzad np. a***b***
  2. Dopisz obsluge patternu ?

Powinna byc zmiana dwoch linijek.

0

Przepraszam że tak późno odpisuję, ale dopiero mogłem się tym zająć.
Wpisałem ten kod do kompilatora i mam wrażenie że nadal nie do końca działa, wszysko jest ok tylko gdy ** jest na końcu.
aaaaaa - a* - true
ale już
aaaaaa - *a - false
Dodatkowo nie rozumiem niektórych fragmentów kodu.

0

Rozwiazanie z backtrackingiem obsluguje takie rodzaj wzorcow. Jak nie rozumiesz kodu to pytaj konkrety. Polecam najpierw zrozumiec poprzedni kod bo jest prostszy.

bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {
        if (*pattern == '*')
        {
            matchAny = true;
            ++pattern;
        }

        if (!*str)
        {
            return !*pattern;
        }

        if (*pattern == *str)
        {
            if (matchAny)
            {
                if (match(str, pattern))
                {
                    return true;
                }
            }
            else
            {
                ++pattern;
            }
        }
        else if (!matchAny)
        {
            return false;
        }
        ++str;
    } 
}
0

Wiem że to pewnie głupie pytania ale staram się to dokładnie zrozumieć.
I czy while(true) nie można zastąpić czymś "ładniejszym" ?

 bool match(char* str, char* pattern)
{
    bool matchAny = false;
    while (true)
    {

        if (*pattern == '*')
		//*pattern to wskazanie na pierwszy znak łańcucha ?
        {
            matchAny = true;
            ++pattern;
			//przejście do następnego znaku ? jeżeli tak to czym to się różni od pattern++ ?
        }
 
        char curr = *str++;
		//zapamiętujemy pierwszy znak z str i przechodzimy do następnego ?
        if (!curr)
        {
            return !*pattern;
        }
 
        if (*pattern == curr)
        {
            matchAny = false;
            ++pattern;
        }
        else if (!matchAny)
        {
            return false;
        }
    } 
}

0

Nieskonczona petle da sie zastapic petla z warunkiem ale w tym przypadku moze to byc ciezkie a powstaly kod moze byc dluzszy i mniej czytelny.
Co do reszty pytan to poczytaj o arytmetyce wskaznikow oraz post- i pre-inkrementacji. W tym kodzie kazda preinkrementacje mozesz zastapic postinkrementacja i bedzie dzialac tak samo.
*ptr to pierwszy znak na co obecnie wskazuje zmienna ptr. Alternatywnie mozna to zapisac ptr[0]·
++ptr to przejscie do kolejnego znaku.
*ptr++ to odczyt pierwszego znaku a nastepnie przejscie do kolejnego.

0

Poczytałem i już rozumiem tę arytmetykę, ale nie do końca rozumiem jeszcze tylko ten kawałek

            if (matchAny)
            {
                if (match(str, pattern))
                {
                    return true;
                }
            }
            else
            {
                ++pattern;
            }
0

To jest technika zwana backtrackingiem (w przypadku parserów także zwana recursive descent). Powiedzmy, że masz łańcuch ababb oraz wzorzec a*b . Jak próbujesz dopasować ten wzorzec to masz wybór:

  1. Dopasuj łańcuch ab do wzorca a*b
  2. Dopasuj łańcuch abab do wzorca a*b
  3. Dopasuj łańcuch ababb do wzorca a*b

Tylko 3 opcja daje poprawne dopasowanie. Ale gdy przetwarzasz wzorzec i łańcuch po jednym znaku to nie masz pojęcia, którą opcje wybrać (nawet nie wiesz, że opcja 2 i 3 istnieje gdy jestes na drugim znaku). Dlatego pierwszy algorytm działa niepoprawnie dla takiego wzorca i łańcucha bo zachłannie wybiera zawsze pierwszą opcje. Backtracking rozwiązuje ten problem próbując wszystkie możliwe dopasowania.

        if (*pattern == curr)
        {
            if (matchAny)
            {
                //Tutaj mamy wybór: albo kończymy dopasowanie gwiazdki i wybieramy kolejny znak wzorca albo kontynujemy dopasowywanie gwiazdki
                //Nie wiemy co zrobić więc próbujemy co się stanie jeżeli zakończymy matchowanie gwiazdki
                if (match(str, pattern))
                {
                    //Nasza decyzja okazała się poprawna wzorzec jest dopasowany więc kończymy
                    return true;
                }
                // Decyzja okazała się niepoprawna więc kontynuujemy matchowanie gwiazdki
            }
            else
            {
                //Nie było gwiazdki więc nie ma problemu, nie mamy żadnego wyboru z którym trzeba by się zmagać
                ++pattern;
            }
        }
0

Dzięki wielkie za pomoc, chyba w miarę to zrozumiałem i cieszę się że czegoś się nauczyłem ;)

0

Testowałem tę funkcję jeszcze raz i wydaje mi się że nie wykrywa ona zgodności '*" z pustym łańcuchem

1 użytkowników online, w tym zalogowanych: 0, gości: 1