Algoritmus pro substituci – C / C++ – Fórum – Programujte.com

Ahoj,

prosím o pomoc - potřeboval bych vymyslet s jednou funkcí v jazyku C. Jedná se v podstatě o algoritmus představující substituci.

Mám buffer, který má například tyto prvky: {S:aS S:a}

Já potřebuji provést substituci na {S:aA A:S A:@} (S se přepíše na A, tudíž v dalším řádku je A = S, v dalším řádku se A nemá na co přepsat, tak se tam dá symbol @)

Příklady substitucí:

{A:bxc A:yc A:bxzd A:yzd} -> {A:bxB A:yC B:c B:zd C:c C:zd}

{A:aB A:aCB} -> {A:aX A:bBB X:B X:CB}

{X:a X:abCa C:c C:cBC} -> {X:aD D:@ D:bCa C:cF F:@ F:BC}

Co se týče písmenek, které mají nahradit původní, je na ně pouze požadavek, aby byla velká a nebyla stejná jako ty které už jsou použita.

Děkuji

Tak už sem něco vyřešil, zasekl jsem se ale u cyklu, který má porovnávat slova.

Mám například tyto slova {A:bxc A:yc A:bxzd A:yzd}. Jedná se o výběr slov, která mají stejný znak na první a třetí pozici.

No a cyklus by měl umět vytisknout v každým kroku slova, která jsou shodná na třetí až n-té pozici (a vypsat, index, kam až jsou prvky shodné).

1. krok = A:bxc A:bxzd (shoda: bx = až k čtvrté pozici)

2. krok = A:yc A:yzd (shoda: y = až ke třetí pozici)

Pokud by nastal případ, že slova by byla tyto {A:a A:abc A:abx}, tak by krok měl vypadat:

1. krok = A:a A:abc A:abx (shoda: a = až ke třetí pozici)

Zatím mám udělané procházení mezi slovy.. ale nevím jak udělat to porovnávání "do N"

int i;
	char temp_buffer [strlen(buffer)+1];
	char working_buffer [strlen(buffer)+1];
	strcpy(temp_buffer, buffer);
	strcpy(working_buffer, buffer);
	for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
	{
		for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
		{
			if (token_b[2] == token_c[2])
			{
				printf("TOken {%s}\n", token_b);
			}
		}	
	}

To "do N" bude další cyklus. Nevím, jestli to bude dělat přesně to, co chceš, ale zhruba takhle:

int N = ?;

for (token_b...
{
    for (token_c...
    {
        int shoda = 0;
        for (int i = 2/*0*/; i < N-1 && token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
        {
            shoda = i;
        }
        if (shoda > 2)
        {
            printf("{%s}{%s}{%d}\n", token_b, token_c, shoda);
        }
    }
}

#3 zlz
A k čemu je tam to N? Nepochopil jsem jakou hodnotu mám za něj dosadit..

#4 Sprinter
Jo jasný, délka slova :-)

Já nevím, ty jsi psal o nějakém N  

No myslel jsem jako procházení slovem po znacích tak dlouho, dokud jsou znaky stejné.

Pro vstup: {A:bxc A:yc A:bxzd A:yzd} by to tedy mělo vytisknout:

{A:bxc}{A:bxzd}{4}

{A:yc}{A:yzd}{3}

Momentálně to vypisuje toto:

S tím, že kód jsem upravil o ten for cyklus s podmínkou

int N;
char temp_buffer [strlen(buffer)+1];
char working_buffer [strlen(buffer)+1];
strcpy(temp_buffer, buffer);
strcpy(working_buffer, buffer);
for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
{
	N = strlen(token_b);
	for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
	{
		int shoda = 0;
		for (int i = 2/*0*/; i < N-1 && token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
		{
			shoda = i;
		}
		if (shoda > 2)
		{
			printf("{%s}{%s}{%d}\n", token_b, token_c, shoda);
		}
	}	
}

• test konce tokenů tam je, to N nepotřebuješ
• strtok vrací ukazatel uvnitř původního řetězce, takže do něj taky vkládá ukončovač tokenu
• shoda je poslední shodný index - počítaný od 0 - při výpisu přičti 1
• testuje se všechno se vším, asi tam budeš chtít přidat ještě nějakou logiku, co s čím testovat. Např. netestovat token se sebou samým (pokud tam nebudou duplicity, tak stačí porovnat obsah), nebo já nevím co...

for (token_b...
{
    strcpy(working_buffer, buffer);
    for (token_c...
    {
        if (!strcmp(token_b, token_c))
            continue;

        int shoda = 0;
        for (int i = 2/*0*/; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
        {
            shoda = i;
        }
        if (shoda >= 2)
        {
            printf("{%s}{%s}{%d}\n", token_b, token_c, shoda + 1);
        }
    }
}

{A:bxc}{A:bxzd}{4}
{A:yc}{A:yzd}{3}
{A:bxzd}{A:bxc}{4}
{A:yzd}{A:yc}{3}

#8 zlz
Jojo děkuju. To testování všechno se vším bych mohl udělat tak, že bych ty shodný ukládal do pomocného pole a pak prorovnával obsah...

Akorát teď když testuju ten kód, tak vypisuje jen:

{A:bxc}{A:bxzd}{4}

{A:bxzd}{A:bxc}{4}

Něvíte, kde by mohla být chyba?

To nevím. Nemáš tam něco jinak? Třeba to >= 2 ?

A tykej...

#10 zlz
Ok :-) No kód jsem zkopíroval, takže by to mělo být stejné.

Buffer = {A:bxc A:yc A:bxzd A:yzd}

char temp_buffer [strlen(buffer)+1];
	char working_buffer [strlen(buffer)+1];
	strcpy(temp_buffer, buffer);
	strcpy(working_buffer, buffer);
	for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
	{
		for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
		{
			if (!strcmp(token_b, token_c))
			continue;

			int shoda = 0;
			for (int i = 2/*0*/; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
			{
				shoda = i;
			}
			if (shoda >= 2)
			{
				printf("{%s}{%s}{%d}\n", token_b, token_c, shoda + 1);
			}
		}	
	}

Tak jsem to nakonec udělal takto:

int accord;
int last;
int length = strlen(buffer)+1;
int shift = 0;
bool computation;
char temp_buffer [length];
char help [length];
char used_rules [length];
	
help[0] = '\0';
used_rules[0] = '\0';
strcpy(temp_buffer, buffer);
for (token_b = strtok_r(temp_buffer, " ", &next_token_b); token_b; token_b = strtok_r(NULL, " ", &next_token_b))
{		
	char working_buffer [length];
	strcpy(working_buffer, buffer);
	for (token_c = strtok_r(working_buffer, " ", &next_token_c); token_c; token_c = strtok_r(NULL, " ", &next_token_c))
	{
		if (strstr(used_rules ,token_b)) computation = false;
		else
		{
			accord = 0;
			for (int i = 2; token_b[i] && token_c[i] && token_b[i] == token_c[i]; i++)
			{
				accord = i;
			}	
			if (strlen(help) == 0)
			{
				strcpy(help, token_b);
				strcat(help, " ");
			}
			if (accord >= 2 && !strstr(help, token_c))
			{
				strcat(help, token_c);
				strcat(help, " ");
				last = accord;
			}
			computation = true;
			
		}
	}
	strcat(used_rules, help);
	if (computation == true)
	{
		printf("Vysledek: {%s}{%i}{%c}\n", help, last, elements[shift]);
		shift++;
	}
	help[0] = '\0';
}

Potřeboval jsem ještě aby mi to v jednom kroce vypsalo všechny shodné slova (takže třeba i tři - ne jen vždy dvě)..