cercare lettere in una stringa in C
luchino
Vorrei creare, in linguaggio C, un programmino che faccia le seguenti cose:
in un file di testo, cercare tutte le stringhe che contengano tre lettere
che inserisco da input (es con una scanf).
per esempio, se io inserisco le lettere
"a" "e" "o"
il programma mi ritorna le stringhe "albero", "adesso" (che sono ovviamente
contenute nel file).
Ora, non ho problemi nel manipolare file, ma il problema è che non riesco a
trovare un modo per fare questa ricerca all'interno della stringa. Da quanto
ho visto, non esiste nessuna funzione della libreria standard del C che mi
permetta di fare ciò! Mi servirebbe una funzione "contraria" alla strtok, se
esiste!
Non mi va bene neppure la strstr, che ricerca una sottostringa.
Grazie anticipate a chiunque voglia darmi una mano o sa indicarmi una
funzione che faccia quanto richiesto :)
Luchino
Giovanni Resta
> Salve a tutti
> Vorrei creare, in linguaggio C, un programmino che faccia le seguenti cose:
> in un file di testo, cercare tutte le stringhe che contengano tre lettere
> che inserisco da input (es con una scanf).
> per esempio, se io inserisco le lettere
> "a" "e" "o"
> il programma mi ritorna le stringhe "albero", "adesso" (che sono ovviamente
> contenute nel file).
>
se sai manipolare i files, il problema e' banale.
Supponi che i tuoi tre caratteri da cercare siano
char A,B,C;
allora apri il file, e leggi via via le stringhe,
e per ogni stringa letta, (chiamiamola S)
controlli
if (strchr(S,A) && strchr(S,B) && strchr(S,C))
{
// le tre lettere compaiono nella stringa
}
else
{
// almeno una delle lettere NON compare nella stringa
}
strchr si trova in string.h
ciao,
g.
luchino
> {
> // le tre lettere compaiono nella stringa
> }
> else
> {
> // almeno una delle lettere NON compare nella stringa
> }
>
> strchr si trova in string.h
Ti ringrazio innanzitutto per avermi risposto! A parte che ho altri problemi
(che posto su it.comp.lang.c), ma cosě ad occhio mi sembra che controlli
solo se le tre lettere fanno parte della stringa, in qualunque ordine!
Se io dessi le lettere "b" "l" ed "a", il sistema mi tornerebbe comunque
"albero", che io invece non vorrei...
grazie mille!!
Luchino
franco
Beh. Nel descrivere il problema non l'avevi specificato.
Comunque, tenendo conto che la strchr ritorna un puntatore al carattere
di matching basta modificare il programma
if ( (p1=strchr(S,A)) && (p2=strchr(S,B)) && (p3=strchr(S,C))
&& p1<p2 && p2<p3 )
Giovanni Resta
Prima di tutto: qui siamo OFF TOPIC.
Quindi questa e' l'ultima risposta che ti do in questo gruppo.
Secondo, non avevi specificato in nessuna parte del messaggio che
volevi che le tre lettere fossero contenute nell'ordine specificato....
Allora:
ora non ho tempo di studiare il problema,
comunque una soluzione molto semplice, anche se
presumo che ce ne siano di molto piu' efficienti, e'
questa.
Assumiamo come prima che i tre caratteri siano in
char A,B,C;
e che la stringa sia S.
Chiaramente non basta trovare la prima occorrenza
di A, B e C in S, perche', ad esempio,
la prima occorrenza di B in S potrebbe essere prima
di quella di A, ma potrebbe esserci una seconda
occorrenza di B dopo A, etc.etc.
useremo 4 variabili intere:
int i,j,k; // indici
int n; // lunghezza di S
int Ok; // lo poniamo a 1 se la parola soddisfa.
n = strlen(S); // calcola la lunghezza di S
Ok=0; // non abbiamo ancora trovato nulla
for (i=0; i<(n-2) && Ok==0; i++)
if (S[i]==A)
for (j=i+1; j<(n-1) && Ok==0; j++)
if (S[j]==B)
for (k=j+1; k<n && Ok==0; k++)
if (S[k]==C) Ok=1;
if (Ok==1)
{
// ho trovato le tre lettere nell'ordine
}
else
{
// non ho trovato le tre lettere nell'ordine
}
la comprensione dell'algoritmo e' lasciata come
semplice esercizio... :-)
ciao,
g.
Giovanni Resta
> Beh. Nel descrivere il problema non l'avevi specificato.
> Comunque, tenendo conto che la strchr ritorna un puntatore al carattere
> di matching basta modificare il programma
>
> if ( (p1=strchr(S,A)) && (p2=strchr(S,B)) && (p3=strchr(S,C))
> && p1<p2 && p2<p3 )
> {
Non funziona.
infatti se la parola e' BABBO e le lettere sono
A='A', B='B', C='O',
la parola dovrebbe passare il test, in quanto contiene le lettere
nell'ordine : bABbO ,
ma nel tuo modo
p2 puntera' alla prima B (che precede la A) e quindi il test fallisce.
Vedi l'altro mio post per un metodo che dovrebbe funzionare.
ciao,
g.
luchino
> Quindi questa e' l'ultima risposta che ti do in questo gruppo.
Hai ragione, avrei dovuto postare su it.comp.lang.c e chiedo venia!
> Secondo, non avevi specificato in nessuna parte del messaggio che
> volevi che le tre lettere fossero contenute nell'ordine specificato....
Anche qui chiedo venia :)
[CUT]
> Allora:
> ora non ho tempo di studiare il problema,
Ma mi sei stato utilissimo: ora il mio programmino funziona alla perfezione
:)
> la comprensione dell'algoritmo e' lasciata come
> semplice esercizio... :-)
Grazie mille :))
Luchino
franco
Giovanni Resta wrote:
> franco wrote:
>
>> Beh. Nel descrivere il problema non l'avevi specificato.
>> Comunque, tenendo conto che la strchr ritorna un puntatore al
>> carattere di matching basta modificare il programma
>>
>> if ( (p1=strchr(S,A)) && (p2=strchr(S,B)) && (p3=strchr(S,C))
>> && p1<p2 && p2<p3 )
>> {
>
>
> Non funziona.
> infatti se la parola e' BABBO e le lettere sono
> A='A', B='B', C='O',
>
> la parola dovrebbe passare il test, in quanto contiene le lettere
> nell'ordine : bABbO ,
> ma nel tuo modo
> p2 puntera' alla prima B (che precede la A) e quindi il test fallisce.
Corretto. Pero' dalla formulazione del problema avevo erroneamente
capito che le tre lettere fossero uniche
Giovanni Resta
> Giovanni Resta wrote:
>>Prima di tutto: qui siamo OFF TOPIC.
>>Quindi questa e' l'ultima risposta che ti do in questo gruppo.
mi contraddico subito da solo....
e' che il primo programmino che ho buttato giu' era
corretto ma poteva (in casi particolari) richiedere un
numero di operazioni quadratico rispetto alla lunghezza
n della stringa S.
In realta' (come mi e' venuto poi subito in mente
guidando verso casa) si puo' fare con
un metodo che nel caso peggiore ha un costo
lineare in n ed e' quindi ottimale da un punto di vista
asintotico.
basta fare cosi' (le variabili Ok,A,B,C,S sono
definite nell'altro messaggio).
char *p, *pA, *pC;
Ok=0; // non va bene
// pA punta alla prima occorrenza di A in S
pA = strchr(S,A);
// pC punta all'ultima occorrenza di C in S
pC = strrchr(S,C);
if (pA && pC && pA<pC)
// controllo se tra la prima A e l'ultima C c'e' una B
for (p=pA+1; p<pC && Ok==0; p++)
if ((*p) == B) Ok=1;
ciao
g.
Usenet MARco 16567.14981
Giovanni> luchino wrote:
> Giovanni Resta wrote:
Giovanni> >>Prima di tutto: qui siamo OFF TOPIC.
....
Giovanni> il primo programmino che ho buttato giu' era corretto
Giovanni> ma poteva (in casi particolari) richiedere un numero di
Giovanni> operazioni quadratico rispetto alla lunghezza n della
Giovanni> stringa S.
Giovanni> In realta' (come mi e' venuto poi subito in mente guidando
Giovanni> verso casa) si puo' fare con un metodo che nel caso peggiore
Giovanni> ha un costo lineare in n ed e' quindi ottimale da un punto
Giovanni> di vista asintotico.
queste cose impieghiamo piu` a descriverle che a pensarle.. :)
Giovanni> basta fare cosi' (le variabili Ok,A,B,C,S sono definite
Giovanni> nell'altro messaggio).
Giovanni> char *p, *pA, *pC;
Giovanni> Ok=0; // non va bene
Giovanni> // pA punta alla prima occorrenza di A in S
Giovanni> pA = strchr(S,A); // pC punta all'ultima occorrenza di C in S
Giovanni> pC = strrchr(S,C);
Giovanni> if (pA && pC && pA<pC) // controllo se tra la prima A e
Giovanni> l'ultima C c'e' una B
Giovanni> for (p=pA+1; p<pC && Ok==0; p++)
Giovanni> if ((*p) == B) Ok=1;
Giovanni> ciao g.
visto la lunghezza del thread off topic.. aggiungo:
in perl si sarebbe cercato tramite solo una regular expression tipo /A.*B.*C/
che restituisce direttamente vero o falso se la stringa in input
(presa opzionalmente per default da stdin) contiene in sequenza
A <qualsiasi cosa> B <qualsiasi cosa> C
Nota: se si vuole che il primo <qualsiasi cosa> (ossia .*)
sia espanso al minimo, cioe` non comprenda eventuali pattern
che proseguano dentro .* con successo la valutazione della
regexp, bisogna postporre un punto interrogativo quindi i
tratti .* della regexp sarebbe piu` appropriato sostituirli con .*?
pensa ad esempio quante occorrenze di A,B,C interessano per la stringa
AqAxByCwBzC
-------
Se avessi avuto un po' piu` di tempo qualche anno fa l'avrei
scritto io li libro "Mastering Regular Expression" edito dalla
O'Reilly che mi limito a segnalare, ma quando usci` mi
dispiacque che era un po' elementare.
[ ad essere poi pignoli fuori da questo esempio se si vogliono usare
variabili sarebbe meglio quotarle con /\Q$a\E.*?\Q$b\E.*?\Q$c\E/o
oppure piu` in generale, valutando dinamicamente un array (@lettere),
cosi`: $regexp=join('.*?',map{"\Q$_\E"}@lettere); if (/$regexp/) ... ]
Non c'e` solo perl, molti sistemi unix hanno ormai preinstallato per C
il modulo regexp.h, non so se sia il caso di scomodarlo... ma luchino,
visto cio` che hai scomodato..
v. le funzioni regcomp, regexec, regerror, regfree
conformi allo standard IEEE Std 1003.2 (``POSIX.2'')
Saluti,
MARco Munari
--
xref: http://mar.i.am/~u16567.14981/it.scienza.informatica/regexp1,it
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1 ; 0<t<14
cerealz
> in perl si sarebbe cercato tramite solo una regular expression tipo /A.*B.*C/
e che c'entra???
> scritto io li libro "Mastering Regular Expression" edito dalla
> O'Reilly che mi limito a segnalare, ma quando usci` mi
e quindi?
> Non c'e` solo perl, molti sistemi unix hanno ormai preinstallato per C
> il modulo regexp.h, non so se sia il caso di scomodarlo... ma luchino,
giusto perche dovremmo farlo?
Usenet MARco 16635.41738
> > in perl si sarebbe cercato tramite solo una regular
> > expression tipo /A.*B.*C/
cerealz> e che c'entra???
Il perl e` scritto in C; "cosa centra?" e` una domanda da rivolgere
ai tuoi soli due interventi in it.scienza.informatica
per di piu` polemici e a mio avviso un po' scorretti, approvati.
[...half sentence cutted omitted...]
cerealz> e quindi?
Non citar scorrettaente, e` incredibile cosa e` concesso a degli
anonimi utenti di telecom in questo newgroup italiano scientifico moderato.
> > Non c'e` solo perl, molti sistemi unix hanno ormai
> > preinstallato per C il modulo regexp.h, non so se sia il
> > caso di scomodarlo... ma luchino,
cerealz> giusto perche dovremmo farlo?
Fare cosa? (non ho la piu` pallida idea di quale fosse il
pensiero che ha portato alla tua domanda, che a sua volta e` troppo
sintetica e sgrammaticata per trovrci un aggancio logico),
Io non approverei questi post (il mio compreso perche` non ci sarebbe
bisogno di scriverlo).
Saluti,
MARco
--
xref: http://mar.i.am/~u16635.41738/it.scienza.informatica/polemicacperl,it