Newsgroup: it.scienza.informatica
Titolo: cercare lettere in una stringa in C

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).
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


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.

 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


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 )



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.

 {
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.

 semplice esercizio... :-)
Grazie mille :))
Luchino

 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

>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.

~\/~ "Giovanni" == Giovanni Resta <g.r...@iit.cnr.it.nospam> writes:
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

 il modulo regexp.h, non so se sia il caso di scomodarlo... ma luchino,
giusto perche dovremmo farlo?

 writes:
       > > 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
