[C] Parola più lunga da stringa

[kwb]

Ciao a tutti!
Devo scrivere un programma in c in grado di predendere in input una stringa di testo ( massimo 132 caratteri ), leggerla, e stampare a schermo la parola più lunga presente nella stringa.
Nel caso in cui ci fossero due o più parole con la stessa massima lunghezza, il programma deve stamparle.

Per ora ho scritto questo:

/*
 Write a C program that reads a line of text from keyboard and then writes the longest word in the line.
 If more than one word has longest length, the program will output all of them.
 The program should work with lines up to 132 characters long and ignore characters in excess.
*/

#include <stdio.h>
#include <string.h>
#define MAX 133

int get_line ( char str_line[MAX] );
void erase_array ( char array[MAX]);
void search_in_string ( char str_line[MAX], int str_len);

int main (void)
{
	int get_line_result=0; //This gets the lenght of the array and checks if there's any error
	char str_line[MAX];
	
	erase_array( str_line );
	printf("Insert a line of text\n");
	printf("The line cannot exceed 132 characters\n");
	if ((get_line_result = get_line ( str_line )) == -1)
	{	
		printf("Error in reading the line");
		return -1;
	}
	else 
	{
		search_in_string ( str_line, get_line_result );
	}

	return 0;
}

void erase_array (char array[MAX])
{
	int i;
	
	for ( i=0; i < MAX; i++ )
		array[i]=0;
}

int get_line ( char str_line[MAX] )
{ 
	int max_str_lenght = MAX - 1; //We reserve the last slot for \0
	int i=0;
	
	if ( fgets( str_line, max_str_lenght, stdin)== NULL )
		return -1;
	else
		i = strlen(str_line);
	printf("Array has lenght: %d\n", i-1); // i-1 because it counts also \0 and we don't want this
	return i-1;
}

void search_in_string ( char str_line[MAX], int str_len)
{
	int i=0, temp=-1; //Indexes
	char word[MAX];
	char longest_word[MAX];
	int max_len=0;
	
	erase_array( word );
	erase_array( longest_word );
	do
	{
		for ( i= temp ; str_line[i] != ' '; i++)
			;
		temp = i + 1;
		strncpy (word, str_line, i+1);
		
		max_len = i;
			
			
	}while ( str_line[i] != '\n' || str_line[i] !='\0');
}

Come si vede dal codice, faccio uso di due array:
- Il primo che contiene tutta la stringa
- Il secondo che dovrà contenere tutti le parole di massima lunghezza.

Quello che non riesco a fare è dire al programma, memorizzata la prima parola nel vettore ( che ovviamente, essendo la prima, sarà certamente la più lunga di quelle fino ad ora controllate ) di riprendere il vettore stringa, escludere la prima parola, e passare a quella successiva.
Penso che questo non sia il modo corretto di operare ( e nemmeno il più semplice ) ma l'unica altra idea che mi è venuta in mente è stata quella di fare così:

1. Leggo la stringa
2. Ad ogni spazio mi fermo e guardo quanto è lunga la parola
3. Memorizzo da qualche parte le lunghezze di ogni singola parola
4. Se ci sono delle lunghezze uguali uso la funzione per concatenare le stringhe, altrimenti copio solo n caratteri con strncpy.
5. Memorizzo le/la parole/a nel vettore apposito
6. Stampo il vettore

Mi sembra possa funzionare, però non ho idea di come:

• Memorizzare tutte le lunghezze: dovrei creare un vettore di non si sa che dimensione...
• Tornare nel vettore stringa a prendere le singole parole per metterle nel vettore che stamperò...

Penso di essermi perso in un bicchier d'acqua perchè sono sicuro ci sia una soluzione molto più semplice... Ma non mi viene in mente niente altro di meglio...

Vorrei cercare di capire come fare più che avere il codice fatto. Ovvio, non mi offendo se mettete piccole righe di codice...

[tuccio`]

è molto più semplice (ma di complessità equivalente) prima cercare quale sia la lunghezza massima e poi stampare quelle che hanno quella lunghezza

per semplificarti la vita potresti, nella prima "passata", sostituire gli spazi con '\0', così da poter usare puts e strlen

memorizzare la dimenisone di ogni singola parola può essere un'ottimizzazione valida anche procedendo come ho descritto, puoi farlo usando realloc

aggiungendo prima di tutto:

int *len_v = NULL, size = 0;

e poi, dopo aver calcolato la lunghezza di una parola:

len_v = realloc(len_v, sizeof(int) * (++size));
len_v[size-1] = /* LUNGHEZZA */;

[fero86]

banalissimo:

#include <iostream>
#include <string>

using namespace std;


int main() {
	string strLongestWord;
	while (!cin.eof()) {
		string strWord;
		cin >> strWord;
		if (strWord.length() > strLongestWord.length()) {
			strLongestWord = strWord;
		}
	}
	cout << strLongestWord << endl;
	return 0;
}

[ndakota]

barooooo non fero

[DanieleC88]

Originariamente inviato da fero86

banalissimo:

#include <iostream>
#include <string>

using namespace std;


int main() {
	string strLongestWord;
	while (!cin.eof()) {
		string strWord;
		cin >> strWord;
		if (strWord.length() > strLongestWord.length()) {
			strLongestWord = strWord;
		}
	}
	cout << strLongestWord << endl;
	return 0;
}

Non funziona se ci sono più parole della stessa lunghezza (massima).

@kwb: usa strtok() se vuoi restare sul C, altrimenti usa C++ e campa felice.

[cionci]

E' un esercizio, non credo che possa usare C++

Se vuoi fare in due passaggi:
- trovi la lunghezza massima
- riparti da capo e trovi tutte le parole di lunghezza pari a quella massima e le stampi direttamente

Se vuoi fare in un solo passaggio:
- ti serve un vettore di interi contenente la posizione delle parole più lunghe, un intero che ti dice quante posizioni sono valide nel vettore precedente, un intero che ti indica la lunghezza massima
- se trovi una parola più lunga della lunghezza massima già trovata (inizializzata a 0), metti ad uno il contatore delle posizioni e inserisci la posizione nel vettore
- se trovi una parola lunga uguale alla lunghezza massima, incrementi il contatore e inserisci al posizione in cui si trova nel vettore.

Alla fine avrai la lunghezza massima e le posizioni all'interno del vettore in cui si trovano le parole di lunghezza massima.
A questo punto ci sono modi furbi per stamparle e modi meno furbi, lascio a te l'onere di trovare il modo più furbo.

PS: usare strtok è un po' difficile in questo caso. Una parola è una sequenza di caratteri alfabetici, quindi andrebbero inserite in strtok tutte i caratteri diversi da quelli alfabetici. Imho ti conviene di più usare una scansione carattere per carattere. La parola inizia appena trovi un carattere alfabetico (isalpha in C standard) e termina quanto trovi un carattere diverso.

[kwb]

Originariamente inviato da tuccio`

è molto più semplice (ma di complessità equivalente) prima cercare quale sia la lunghezza massima e poi stampare quelle che hanno quella lunghezza

per semplificarti la vita potresti, nella prima "passata", sostituire gli spazi con '\0', così da poter usare puts e strlen

memorizzare la dimenisone di ogni singola parola può essere un'ottimizzazione valida anche procedendo come ho descritto, puoi farlo usando realloc

aggiungendo prima di tutto:

int *len_v = NULL, size = 0;

e poi, dopo aver calcolato la lunghezza di una parola:

len_v = realloc(len_v, sizeof(int) * (++size));
len_v[size-1] = /* LUNGHEZZA */;

Il fatto è che quando ci sono stati assegnati questi esercizi la storia dell'allocazione della memoria non era stata ancora spiegata, quindi non ne potevamo fare uso.

Originariamente inviato da fero86

banalissimo:

#include <iostream>
#include <string>

using namespace std;


int main() {
	string strLongestWord;
	while (!cin.eof()) {
		string strWord;
		cin >> strWord;
		if (strWord.length() > strLongestWord.length()) {
			strLongestWord = strWord;
		}
	}
	cout << strLongestWord << endl;
	return 0;
}

Ma non ho la più pallida idea di cosa faccia questa cosa... Ma è C?

Originariamente inviato da DanieleC88

Non funziona se ci sono più parole della stessa lunghezza (massima).

@kwb: usa strtok() se vuoi restare sul C, altrimenti usa C++ e campa felice.

Uhmm... Ho provato a leggere sui manuali e a capire cosa faccia questa funzione, ma non mi è molto chiaro, mi spiegate?

[DanieleC88]

Originariamente inviato da cionci

PS: usare strtok è un po' difficile in questo caso. Una parola è una sequenza di caratteri alfabetici, quindi andrebbero inserite in strtok tutte i caratteri diversi da quelli alfabetici. Imho ti conviene di più usare una scansione carattere per carattere. La parola inizia appena trovi un carattere alfabetico (isalpha in C standard) e termina quanto trovi un carattere diverso.

Sinceramente non penso che l'esercizio si spinga fino a questo punto, credo voglia un semplice programma che spezza le parole in base agli spazi. Però ci servirebbe una conferma o smentita da kwb.

@kwb: se usi Linux o un altro sistema Unix-like puoi dare man 3 strtok per leggere la documentazione di strtok(). Qui ci sono alcuni esempi (e non capisco perché un'enciclopedia dovrebbe mai interessarsene, comunque).

[DanieleC88]

Faccio io un esempio veloce, va', che forse è meglio.
La funzione strtok() serve a spezzare una stringa composta da più sottostringhe (token) intervallate da alcuni caratteri particolari (delimitatori).
Se hai una stringa di questo tipo:

char *s ="a ab abc abcd abcde";

vedi subito che è una stringa formata da alcune sottostringhe alfabetiche, intervallate a spazi.

La funzione strtok() riceve in input il puntatore alla stringa da esaminare e il puntatore ad una stringa che contiene tutti i delimitatori. Banalmente, la funzione parte dall'inizio della stringa e va avanti finché non incontra un delimitatore (o finché non finisce la stringa, vabbe'). Quando viene trovato un delimitatore, questo viene sostituito col carattere '\0' (quindi strtok() modifica la stringa!) e viene restituito il puntatore all'inizio della stringa. Le successive chiamate non hanno bisogno del primo parametro (che dovrà essere NULL), e partiranno dal prossimo carattere non esaminato, continuando allo stesso modo finché non si incontra un delimitatore o la fine della stringa. Al termine della stringa viene restituito un NULL.

Per esempio, per la stringa precedente sulla chiamata strtok(s, " ") avresti queste modifiche:

s ="a ab abc abcd abcde";

/* prima chiamata, viene restituito &s[0] */
s ="a\0ab abc abcd abcde";

/* seconda chiamata, viene restituito &s[2] */
s ="a\0ab\0abc abcd abcde";

/* terza chiamata, viene restituito &s[5] */
s ="a\0ab\0abc\0abcd abcde";

/* quarta chiamata, viene restituito &s[9] */
s ="a\0ab\0abc\0abcd\0abcde";

/* quinta chiamata, viene restituito &s[14] */
s ="a\0ab\0abc\0abcd\0abcde";

/* sesta chiamata, viene restituito NULL */
s ="a\0ab\0abc\0abcd\0abcde";

Una velocissima implementazione potrebbe essere:

char *strtok(char *str, const char *delim)
{
    static char *ptr = NULL;
    char *start;

    if (str != NULL) {
        ptr = str;
    }

    for (start = ptr; *ptr != '\0'; ++ptr) {
        if (strchr(delim, *ptr) != NULL)) {
            *ptr++ = '\0';
            return start;
        }
    }

    return NULL;
}

L'ho scritta sul momento senza testarla, quindi prendila con le pinze. Per di più l'ho scritta di fretta, perché sto andando a mangiare.

ciao

[cionci]

Originariamente inviato da DanieleC88

Sinceramente non penso che l'esercizio si spinga fino a questo punto, credo voglia un semplice programma che spezza le parole in base agli spazi. Però ci servirebbe una conferma o smentita da kwb.

Imho per uno non avvezzo ai puntatori è più semplice usare una scansione carattere per carattere che strtok
Tra l'altro la realizzazione è semplicissima...

[kwb]

Voglio provare ad implementare il suggerimento di tuccio` , mi sembra il più semplice...
Se non va passerò a quello di cionci, che magari l'utilizzo di queste funzioni ( isAlpha ecc... ) può sempre tornare utile!
Vi faccio sapere!

[cionci]

realloc però non importa che tu la usi, il numero di parole non può essere maggiore di MAX / 2

[cionci]

isAlpha non è un'alternativa all'algoritmo, serve per limitare i caratteri che appartengono alla parola...

if(isalpha(c[i]))

equivale a

if((c[i] >= 'A' && c[i] <= 'Z') || (c[i] >= 'a' && c[i] <= 'z'))

Quindi scorrendo la stringa, la prima volta che isalpha è vero la parola è iniziata, la prima volta in cui diventa falso la parola è finita.
Con lo spazio sarebbe: la prima volta che il carattere non è un spazio la parola è inziata, la prima volta in cui trovo uno spazio la parola è finita.
Cambia solo il modo in cui una parola è delimitata, l'algoritmo è lo stesso.

[kwb]

Si ma adesso sto cercando di implementare il tuo metodo usando isalpha perchè con quello di sostituire gli ' ' con '\0' si creano casini nell'array...
Per ora sono riuscito a determinare la lunghezza massima nella stringa ( la lunghezza della parola più lunga insomma ).
Domani mi metto a scrivere l'ultima parte di codice per stampare la relativa parola.

[cionci]

Originariamente inviato da kwb

Si ma adesso sto cercando di implementare il tuo metodo usando isalpha perchè con quello di sostituire gli ' ' con '\0' si creano casini nell'array...

Non sono comunque alternativi, quello quello che ti volevo far capire era questo. E' solo un modo diverso per considerare la parola. Se sostituisci '\0' ad ogni lettera che ritorna isalpha falso, l'algoritmo è perfettamente identico

[kwb]

Originariamente inviato da cionci

Non sono comunque alternativi, quello quello che ti volevo far capire era questo. E' solo un modo diverso per considerare la parola. Se sostituisci '\0' ad ogni lettera che ritorna isalpha falso, l'algoritmo è perfettamente identico

Il fatto è che sostituendo ' ' con '\0' succede questo:
Stringa inserita: "Ciao oggi è nuvoloso"
Parte la funzione
1° giro: "Ciao\0"
2° giro: "Ciao\0"
ecc.. così fino a non so quando...

[cionci]

E' chiaro che tu debba ricominciare a considerare la stringa dal carattere successivo allo \0 e non dall'inizio

[kwb]

Originariamente inviato da cionci

E' chiaro che tu debba ricominciare a considerare la stringa dal carattere successivo allo \0 e non dall'inizio

Allora... Sono riuscito a scrivere il codice completo questo è:

/*
 Write a C program that reads a line of text from keyboard and then writes the longest word in the line.
 If more than one word has longest length, the program will output all of them.
 The program should work with lines up to 132 characters long and ignore characters in excess.
*/

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 133

int get_line ( char str_line[MAX] );
void erase_array ( char array[MAX]);
int longest_word ( char str_line[MAX], int str_len);
void get_word ( char str_line[MAX], char word[MAX], int max_lenght, int str_len);

int main (void)
{
	int string_lenght=0; //This gets the lenght of the array and checks if there's any error
	char str_line[MAX];
	char word[MAX];
	int max_lenght=0;
	
	erase_array( str_line );
	printf("Insert a line of text\n");
	printf("The line cannot exceed 132 characters\n");
	if ((string_lenght = get_line ( str_line )) == -1)
	{	
		printf("Error in reading the line");
		return -1;
	}
	else 
	{
		max_lenght = longest_word ( str_line, string_lenght );
		printf("The logest word has %d characters\n", max_lenght);
		get_word ( str_line, word, max_lenght, string_lenght);
		printf("and it is: ");
		puts(word);
	}

	return 0;
}

void erase_array (char array[MAX])
{
	int i;
	
	for ( i=0; i < MAX; i++ )
		array[i]=0;
}

int get_line ( char str_line[MAX] )
{ 
	int max_str_lenght = MAX - 1; //We reserve the last slot for \0
	int i=0;
	
	if ( fgets( str_line, max_str_lenght, stdin)== NULL )
		return -1;
	else
		i = strlen(str_line);
	printf("Array has lenght: %d\n", i-1); // i-1 because it counts also \0 and we don't want this
	return i-1;
}

int longest_word ( char str_line[MAX], int str_len)
{
	int i=0;
	int temp_len=0; //Stores temporary lenght
	int max_len=0; //Stores maximum lenght
	
	for ( i=0; i < str_len; i++)
	{	temp_len = 0;
		while ( str_line[i] != ' ' && str_line[i] != '\0' && str_line[i] != '\n')
		{
			if ( isalpha(str_line[i])  )
			{	
				temp_len++;
				i++;
			}
		
		}
		if ( temp_len >= max_len )
			max_len = temp_len;
	}
	return max_len;
}

void get_word ( char str_line[MAX], char word[MAX], int max_lenght, int str_len)
{
	int i, temp_i=0, j, temp_j=0;
	int temp_len=0;
	int flag=0; //Checks if vector word has been ever filled
	
	erase_array(word);
	while( str_line[i] != '\n' && str_line[i] !='\0')
	{	for ( i=temp_i; i < str_len && isalpha(str_line[i]); i++)
		{	
			temp_len++;
		}
		if ( temp_len == max_lenght && flag == 0)
		{	i -= max_lenght;
			for(j=0; j< max_lenght; j++)
			{	
				word[j] = str_line[i];
				i++;
			}
			flag = 1;
			temp_j= j;
			word[j+1] = ' ';
		}
		else if ( temp_len == max_lenght && flag == 1)
		{
			temp_j += 2;
			i -= max_lenght;
			for ( j = 0; j < max_lenght; j++, temp_j++, i++)
			{	
				word[temp_j] = str_line[i];
			}
		}
		temp_len = 0;
		temp_i = i;
		temp_i++;
	}
}

Tuttavia, se come stringa di input do:
"Programmo i programmi"
Il programma ( ) riesce a prendere correttamente la parola 'programmo' e la mette nell'array word.
Poi salta 'i' e passa a 'programmi'.
Qua però, viene eseguito il codice per caricare la parola dentro il vettore, facendo attenzione a non sovrascrivere quella esistente, però non viene caricato nulla e l'array sembra inalterabile....
Perchè?
( La parte in rosso quella incriminata )

[kwb]

Nessuno?
Se può servire, il problema sta in word[j+1] = ' ';
Non si sa perchè non aggiunge nulla... Ho provato pure con un carattere, ma niente...

[cionci]

Non mi torna questo:

int longest_word ( char str_line[MAX], int str_len)
{
	int i=0;
	int temp_len=0; //Stores temporary lenght
	int max_len=0; //Stores maximum lenght
	
	for ( i=0; i < str_len; i++)
	{	temp_len = 0;
		while ( str_line[i] != ' ' && str_line[i] != '\0' && str_line[i] != '\n')
		{
			if ( isalpha(str_line[i])  )
			{	
				temp_len++;
				i++;
			}
		
		}
		if ( temp_len >= max_len )
			max_len = temp_len;
	}
	return max_len;
}

Non mi torna quel controllo, non serve a molto.
Basta che controlli che i sia minore di str_len e che isalpha sia vero per il carattere corrente.

Consiglio: estraiti una funzione che dato un punto di partenza cerca l'inizio e la fine della parola corrente.
La utilizzeresti in entrambe le funzioni. Scrivila così vediamo se permette di chiarirti un po' le idee