Împărțirea șirurilor de caractere – teorie + practica = ❤️

Quote

Suna cunoscut? Mai mult ca sigur. Problema impartirii sirurilor de caractere dupa anumiti separatori este una foarte des intalnita atat in probleme scolare cat si in practica.

Simpla la prima vedere, problema vine insa cu o provocare ascunsa, provocare adesea constientizata abia cand se incepe implementarea: ce returnam?

• Un vector de siruri de caractere mai mici? Cate? Trebuie determinat. Cine aloca/dezaloca memoria? Copiem sirul sau returnam doar pointeri din sirul initial?
  
• Cate un sir odata precum strtok? Unde pastram starea intre apeluri?
  
• Ce facem daca avem doi separatori succesivi? Ignoram sau returnam un sir gol?

Eh... cam multe intrebari.

Abordarea prezentata mai jos va fi una cu accent mai mare pe functii, si-l va ajuta pe cititor sa inteleaga mai bine urmatoarele:

• Lucrul cu pointeri
  
• Lucrul cu functii
  
• Separarea codului pentru a fi mai usor de inteles ce face fiecare bucata
  
• Refactoring - modernizarea treptata a codului

Ce se cere?

Dat fiind sirul "Are Ana mere? Da!" sa extragem cuvintele: "Are", "Ana", "mere", "Da".

Cum obtinem asta?

Algoritmul e simplu: iteram prin caracterele ce compun sirul iar cat timp avem o litera, inca nu s-a terminat cuvantul curent; cand dam de un separator (spatiu, semn de punctuatie, etc) stim ca e gata cuvantul precedent iar ce urmeaza va face parte din alt cuvant.

Pasul 1 – Cum transmitem datele de intrare?

In C, sirul de caractere e deobicei un vector de caractere asezate unul dupa altul in memorie, si cu valoarea 0 in final. Acea valoare 0 indica finalul sirului. Fara ea n-am stii cat de mult se intinde sirul in memorie (ar fi fost nevoie sa pastram separat dimensiunea).

 Untitled.png   17.41K   7 downloads

Pasul 2 – Cum izolam cuvintele?

Iteram o singura data prin sir, si pastram un contor suplimentar. Consideram, deocamdata, caracterele ' ', '?' si '!' drept separatori. In cod am folosit termenul segment, mai generic decat cuvant.

void imparteSirul(const char* sir)
{
	unsigned int startSegment = 0, i = 0;
	for (i = 0; sir[i] != 0; ++i)
	{
		if (sir[i] == ' ' || sir[i] == '?' || sir[i] == '!')
		{
			unsigned int lungimeSegmentCurent = i - startSegment;
			if (lungimeSegmentCurent > 0)
			{
				const char* segment = sir + startSegment;
				//fa ceva cu segmentul gasit
			}
			startSegment = i + 1;
		}
	}
}

int main()
{
	imparteSirul("Are Ana mere? Da!");
}

Pasul 3 – Ce facem cu rezultatele gasite?

Ce facem cu fiecare cuvant/segment gasit? Hai sa-l dam inapoi celui ce ne-a cerut. Cum? Folosind un callback, codul ce ne cere sa impartim sirul ne va oferi si o functie pe care o vom apela pentru fiecare cuvant gasit. Functia va primi doua argument:

• Un pointer din sirul initial, indicand unde incepe sirul
  
• Lungimea cuvantului curent (nu ne mai putem baza pe 0'ul de la final deoarece la finalul sirului initial, nu la finalul fiecarui cuvant)

Functia respectiva poate face orice cu fiecare cuvant:

#include <stdio.h>

typedef void(*PrimesteUnSegment)(const char* sir, unsigned int lungime);

void afiseazaSegmentul(const char* sir, unsigned int lungime)
{
	printf("Am primit un nou segment de lungime %d: ", lungime);

	for (unsigned int i = 0; i < lungime; ++i)
	{
		printf("%c", sir[i]);
	}

	printf("\n");
}

void imparteSirul(const char* sir, PrimesteUnSegment daSegmentulMaiDeparte)
{
	unsigned int startSegment = 0, i = 0;
	for (i = 0; sir[i] != 0; ++i)
	{
		if (sir[i] == ' ' || sir[i] == '?' || sir[i] == '!')
		{
			unsigned int lungimeSegmentCurent = i - startSegment;
			if (lungimeSegmentCurent > 0)
			{
				const char* segment = sir + startSegment;
				daSegmentulMaiDeparte(segment, lungimeSegmentCurent);
			}
			startSegment = i + 1;
		}
	}
	//daca sirul nu se termina cu un separator, sa nu uitam de ultimul segment
	unsigned int lungimeSegmentCurent = i - startSegment;
	if (lungimeSegmentCurent > 0)
	{
		const char* segment = sir + startSegment;
		daSegmentulMaiDeparte(segment, lungimeSegmentCurent);
	}
}

int main()
{
	imparteSirul("Are Ana mere? Da!", afiseazaSegmentul);
}

Quote

Pasul 4 – Daca vrem sa folosim si alti separatori?

Cele 3 caractere alese drept separatori sunt suficiente pentru exemplul curent, dar nu sunt suficiente. Ce putem face pentru a generaliza si mai mult solutia? Cerem celui ce ne apeleaza inca o functie, o functie pe care o vom apela pentru fiecare caracter pentru a afla daca sa-l tratam ca un separator sau nu.

In codul de mai jos, orice caracter ce nu e o litera mica sau mare (ASCII) e considerat un separator.

#include <stdio.h>

typedef void(*PrimesteUnSegment)(const char* sir, unsigned int lungime);
typedef int(*DeterminareLungimeSeparator)(const char* sir);

void afiseazaSegmentul(const char* sir, unsigned int lungime)
{
	printf("Am primit un nou segment de lungime %d: ", lungime);

	for (unsigned int i = 0; i < lungime; ++i)
	{
		printf("%c", sir[i]);
	}

	printf("\n");
}

int determinareLungimeSeparatorLitere(const char* sir)
{
	return (*sir >= 'a' && *sir <= 'z') || (*sir >= 'A' && *sir <= 'Z') ? 0 : 1;
}

void imparteSirul(const char* sir, PrimesteUnSegment daSegmentulMaiDeparte, DeterminareLungimeSeparator catESeparatorulDeLung)
{
	unsigned int startSegment = 0, i = 0;
	for (i = 0; sir[i] != 0; ++i)
	{
		int lungimeSeparator = catESeparatorulDeLung(sir + i);
		if (lungimeSeparator > 0)
		{
			unsigned int lungimeSegmentCurent = i - startSegment;
			if (lungimeSegmentCurent > 0)
			{
				const char* segment = sir + startSegment;
				daSegmentulMaiDeparte(segment, lungimeSegmentCurent);
			}
			i += (lungimeSeparator - 1);
			startSegment = i + 1;
		}
	}
	//daca sirul nu se termina cu un separator, sa nu uitam de ultimul segment
	unsigned int lungimeSegmentCurent = i - startSegment;
	if (lungimeSegmentCurent > 0)
	{
		const char* segment = sir + startSegment;
		daSegmentulMaiDeparte(segment, lungimeSegmentCurent);
	}
}

int main()
{
	imparteSirul("Are Ana mere? Da!", afiseazaSegmentul, determinareLungimeSeparatorLitere);
}

Quote

Deoarece un separator poate avea mai mult de o litera. In acest caz e nevoie de lungimea separatorului gasit pentru a stii peste cate caractere sa sarim.

De exemplu, putem avea "A<>B<>C" ce se vrea impartit dupa separatorul "<>".

int separatorComplex(const char* sir)
{
	return (sir[0] == '<' && sir[1] == '>') ? 2 : 0;
}

int main()
{
	imparteSirul("A<>B<>C", afiseazaSegmentul, separatorComplex);
}

Quote

Tema de casa

Cum ne poata ajuta C++ sa scriem codul mai generic?

Edited by dani.user, 06 December 2017 - 21:53.

se pot folosi si bibliotecile string si cstring

Biblioteci sunt multe, considerabil mai bune decat strtok din cstring.