RISOLTO Esercizio di ricerca espressioni regolari in C

[Ledriana]

Salve, mi è stato assegnato un laboratorio, di cui allego di seguito il testo:

Una espressione regolare (o regexp) è una sequenza di simboli (quindi una stringa) che identifica un
insieme di stringhe. Si scriva una funzione in C in grado di individuare (cercare) eventuali occorrenze di
una data regexp all'interno di una stringa di input.
La funzione sia caratterizzata dal seguente prototipo:

char *cercaRegexp(char *src, char *regexp);
dove :
 il parametro src rappresenta la stringa sorgente in cui cercare.
 il parametro regexp rappresenta l'espressione regolare da cercare.
 il valore di ritorno della funzione è un puntatore alla prima occorrenza di regexp in src (NULL
se non trovata).

Ai fini dell'esercizio si consideri di valutare solamente stringhe composte da caratteri alfabetici. Si
considerino inoltre solamente espressioni regolari composte da caratteri alfabetici e dai seguenti
metacaratteri:
 . trova un singolo carattere (cioè qualunque carattere può corrispondere a un punto)
 [] trova un singolo carattere contenuto nelle parentesi (cioè uno qualsiasi dei caratteri tra parentesi
va bene)
 [^ ] trova ogni singolo carattere non contenuto nelle parentesi (cioè tutti i caratteri tra parentesi
non vanno bene)
 \a trova un carattere minuscolo
 \A trova un carattere maiuscolo

Esempi di espressioni regolari:
.oto corrisponde a ogni stringa di quattro caratteri terminante con “oto”, es. "voto", "noto",
"foto", ...
[mn]oto rappresenta solamente "moto" e "noto"
[^f]oto rappresenta tutte le stringhe terminanti in “oto” ad eccezione di "foto"
\aoto rappresenta ogni stringa di quattro caratteri (come "voto", "noto", "foto", ... ) iniziante per
lettere minuscola e terminante in “oto”
\Aoto rappresenta ogni stringa di quattro caratteri (come "Voto", "Noto", "Foto", ...) iniziante per
lettere maiuscola e terminante in “oto”.

Ho cercato di risolverlo con dei costrutti if-else e poi la strstr, ma la funzione mi ritorna sempre NULL. Sto letteralmente impazzendo!
Metto come esempio l'if dell'occorenza '.'
Qualcuno saprebbe propormi una soluzione?

char *cercaRegexp(char *src, char *regexp) {
    char *ris;
        while (*regexp != '\0') {
            if (*regexp == '.') {
                while(*src!='\0'){
                    if(*(regexp+1)==*src){
                        printf("%c", *(src-1));
                        return strstr(src,regexp);
                    }
                    src++;
                }

            } else if (*regexp == '[') {

            } else if (*regexp == '[' && *(regexp + 1) == '^') {

            } else if (*regexp == '\\') {

            }

        }
        regexp++;
        return ris;
    }

 

[ilfe98]

Ciao, benvenuta sul forum.
Credo che la sintassi else if sia molto meno pratica in questo contesto. Ti consiglio anzitutto l' utilizzo di un costrutto di switch.

cercaregex....(){
switch (*src){
case '\.':
vector_size();
if(checking_pattern())
//do something

;;
default : //something
}
}

Dopodiché mettiamo un po' di ordine mentalmente. In questo contesto non ti viene passata la dimensione del vettore stringa. Pertanto potremmo scorrere l'intero vettore o nel caso in cui non sia dinamicamente allocato utilizzare:
size_t size=sizeof(src) / sizeof(char);
a questo punto ci serve soltanto un'ultima funzione ausiliaria che ritorna true in caso in cui la stringa combaci.
il pattern è .oto
ipotizziamo la stringa pallanuoto
ci allineiamo con i puntatori alle celle e confrontiamo i valori. Soltanto se combaceranno tutti potro terminare il ciclo e arrivare al return true. altrimenti lo interrompiamo prima con un break ed un return false!

 

[Ledriana]

Ciao, benvenuta sul forum.
Credo che la sintassi else if sia molto meno pratica in questo contesto. Ti consiglio anzitutto l' utilizzo di un costrutto di switch.

cercaregex....(){
switch (*src){
case '\.':
vector_size();
if(checking_pattern())
//do something

;;
default : //something
}
}

Dopodiché mettiamo un po' di ordine mentalmente. In questo contesto non ti viene passata la dimensione del vettore stringa. Pertanto potremmo scorrere l'intero vettore o nel caso in cui non sia dinamicamente allocato utilizzare:
size_t size=sizeof(src) / sizeof(char);
a questo punto ci serve soltanto un'ultima funzione ausiliaria che ritorna true in caso in cui la stringa combaci.
il pattern è .oto
ipotizziamo la stringa pallanuoto
ci allineiamo con i puntatori alle celle e confrontiamo i valori. Soltanto se combaceranno tutti potro terminare il ciclo e arrivare al return true. altrimenti lo interrompiamo prima con un break ed un return false!

Ti ringrazio! Proverò in questo modo

 

[ilfe98]

Ti ringrazio! Proverò in questo modo

Se posti il codice completo possiamo aiutare molto di più, con solo uno spezzone viene difficile capire se è un errore logico

 

[Ledriana]

Se posti il codice completo possiamo aiutare molto di più, con solo uno spezzone viene difficile capire se è un errore logico

Oltre a quello che ho postato c'è solo il main, posso postarlo ma ho proprio difficoltà a capire come procedere.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

char *cercaRegexp(char *src, char *regexp);

int main() {

    char src[10], regexp[10], *result;

        printf("Inserisci la stringa in cui cercare (solo valori alfabetici):\n");

        scanf("%s", src);

        printf("Inserisci le occorrenze da cercare:\n");

        scanf("%s", regexp);

        result = cercaRegexp(src, regexp);

        printf("%s", result);

}



char *cercaRegexp(char *src, char *regexp) {

    char *ris;

    while (*regexp != '\0') {

        if (*regexp == '.') {

            if (*(regexp + 1) == *src) {

                ris= *(src - 1);

            }

        }

        else if (*regexp == '[') {

            if (*(regexp + 1) == *src) {

                ris=strchr(src, *(regexp+1));

            }



        }

        else if (*regexp == '[' && *(regexp + 1) == '^') {

            if (*(regexp + 2) != *src) {

                ris=src;

            }

        }

        else if (*regexp == '\\') {

            if(islower(*(regexp+1))!=0 && islower(src)!=0){

                ris=src;

            }

        }
        regexp++;
        return ris;

    }

}

 

[Andretti60]

Implementare una funzione che faccia un "pattern matching" non e' per nulla semplice, non te la cavi con una sequenza di if() e si switch()

La prima cosa da fare e' di fare un parser della espressione regolare, cosi' da controllare anche se e' formattata giustamente (per esempio manca una parentesi quadra chiusa) per memorizzare il tipo di confronti da fare in un vettore di "operazioni" (confronti) da eseguire. Trattandosi del linguaggio C, tali "confronti" vengono descritti da una struct (essendo formati da dati diversi).

Prima devi definire una enumerazione, per definire che tipo di operazioni da fare. Nel tuo caso, e' molto semplice:
Qualunque (che corrisponde al punto .)
Carattere (deve essere esattamente quel carattere, per esempio 'o')
Appartiene (un insieme di caratteri definiti dal costrutto [])
NonAppartiene (come sopra)
Minuscola (qualunque lettera minuscola)
Maiuscola (qualunque lettera maiuscola)

Poi definisci una struttura con due campi: Operazione (uno dei valori definiti dalla enumerazione) e Valore (una stringa). Se vuoi fare le cose per bene, tale struttura deve fare parte di una "linked list", per cui occorre un terzo campo: Next (il puntatore alla struttura seguente) Se vuoi fare le cose più semplici, usa un vettore invece di una lista. Definisce la massima lunghezza, e se hai bisogno di più elementi termina con un messaggio di errore.

A questo punto puoi iniziare a fare la scansione della espressione regolare:

1. Alloca lo spazio per una struttura dati.
   1. Se il primo carattere e' una parentesi quadra aperta, guarda se il secondo carattere e' il '^', se lo e' assegna alla Operazione il codice NonAppartiene, altrimenti il codice Appartiene. Nel campo Valore inserisci la stringa presente prima della parentesi quadra chiusa. Se non trovi la parentesi chiusa, segnala errore.
   2. Se il primo carattere e' un '.' assegna come operazione il valore Qualunque.
   3. Se il primo carattere e' un '\', assegna l'operazione Minuscola o Maiuscola, a seconda del carattere successivo.
   4. Altrimenti usa l'operazione Carattere e assegna il carattere nel campo Valore
   5. L'operazione sopra descritta la puoi fare con uno Switch() o con una serie di if() (la mia preferenza e' sempre di usare uno switch() )
2. aggiorna il puntatori Next dell'ultimo elemento della lista e aggiungi la struttura alla fine (la lista deve essere di tipo FIFO).
3. A questo punto se non sei alla fine della stringa, ritorna al primo punto, aggiornando il puntatore del "primo carattere"

A questo punto la sequenza di confronti e' memorizzata nella lista. Operazione analoga se usi un vettore invece di una lista, devi solo tenere aggiornato l'indice dell'elemento corrente (partendo da zero)

Prima di passare al confronto vero e proprio, controlla che la lista sia corretta, inserendo diverse espressioni regolari. Per facilitare il controllo scrivi un metodo che stampa gli elementi della lista.

L'operazione di confronto parte dal puntatore del primo carattere della stringa sorgente, fai il confronto usando il primo elemento della lista. Se il confronto ha successo, basandosi sul campo Operazione e Valore, passa al successivo carattere e al secondo elemento della lista. Se tutti le operazioni hanno successo, hai finito. Appena un confronto fallisce, incrementa il puntatore della stringa sorgente e rifai il processo ripartendo dal primo elemento della lista. Se arrivi alla fine della stringa sorgente, ritorna NULL

Questo e' la classica implementazione di parsing, e' estremamente flessibile perche' e' facile aggiungere altre espressioni regolari, mi stupisce non ve la abbiano insegnata. In questo modo si può fare il parsing di qualunque cosa, per esempio di una operazione matematica. Ovviamente la cosa e' estremamente più facile in C++, usando una class invece di una struttura, in quanto l'operazione di confronto viene fatta all'interno della classe (ma lasciamo perdere a questo punto)

Sono stato vago nei dettagli, volutamente. Come hai visto non esiste un modo unico per implementare tale algoritmo.

Questo articolo e' famoso.

 

[Ledriana]

Implementare una funzione che faccia un "pattern matching" non e' per nulla semplice, non te la cavi con una sequenza di if() e si switch()

La prima cosa da fare e' di fare un parser della espressione regolare, cosi' da controllare anche se e' formattata giustamente (per esempio manca una parentesi quadra chiusa) per memorizzare il tipo di confronti da fare in un vettore di "operazioni" (confronti) da eseguire. Trattandosi del linguaggio C, tali "confronti" vengono descritti da una struct (essendo formati da dati diversi).

Prima devi definire una enumerazione, per definire che tipo di operazioni da fare. Nel tuo caso, e' molto semplice:
Qualunque (che corrisponde al punto .)
Carattere (deve essere esattamente quel carattere, per esempio 'o')
Appartiene (un insieme di caratteri definiti dal costrutto [])
NonAppartiene (come sopra)
Minuscola (qualunque lettera minuscola)
Maiuscola (qualunque lettera maiuscola)

Poi definisci una struttura con due campi: Operazione (uno dei valori definiti dalla enumerazione) e Valore (una stringa). Se vuoi fare le cose per bene, tale struttura deve fare parte di una "linked list", per cui occorre un terzo campo: Next (il puntatore alla struttura seguente) Se vuoi fare le cose più semplici, usa un vettore invece di una lista. Definisce la massima lunghezza, e se hai bisogno di più elementi termina con un messaggio di errore.

A questo punto puoi iniziare a fare la scansione della espressione regolare:

1. Alloca lo spazio per una struttura dati.
   1. Se il primo carattere e' una parentesi quadra aperta, guarda se il secondo carattere e' il '^', se lo e' assegna alla Operazione il codice NonAppartiene, altrimenti il codice Appartiene. Nel campo Valore inserisci la stringa presente prima della parentesi quadra chiusa. Se non trovi la parentesi chiusa, segnala errore.
   2. Se il primo carattere e' un '.' assegna come operazione il valore Qualunque.
   3. Se il primo carattere e' un '\', assegna l'operazione Minuscola o Maiuscola, a seconda del carattere successivo.
   4. Altrimenti usa l'operazione Carattere e assegna il carattere nel campo Valore
   5. L'operazione sopra descritta la puoi fare con uno Switch() o con una serie di if() (la mia preferenza e' sempre di usare uno switch() )
2. aggiorna il puntatori Next dell'ultimo elemento della lista e aggiungi la struttura alla fine (la lista deve essere di tipo FIFO).
3. A questo punto se non sei alla fine della stringa, ritorna al primo punto, aggiornando il puntatore del "primo carattere"

A questo punto la sequenza di confronti e' memorizzata nella lista. Operazione analoga se usi un vettore invece di una lista, devi solo tenere aggiornato l'indice dell'elemento corrente (partendo da zero)

Prima di passare al confronto vero e proprio, controlla che la lista sia corretta, inserendo diverse espressioni regolari. Per facilitare il controllo scrivi un metodo che stampa gli elementi della lista.

L'operazione di confronto parte dal puntatore del primo carattere della stringa sorgente, fai il confronto usando il primo elemento della lista. Se il confronto ha successo, basandosi sul campo Operazione e Valore, passa al successivo carattere e al secondo elemento della lista. Se tutti le operazioni hanno successo, hai finito. Appena un confronto fallisce, incrementa il puntatore della stringa sorgente e rifai il processo ripartendo dal primo elemento della lista. Se arrivi alla fine della stringa sorgente, ritorna NULL

Questo e' la classica implementazione di parsing, e' estremamente flessibile perche' e' facile aggiungere altre espressioni regolari, mi stupisce non ve la abbiano insegnata. In questo modo si può fare il parsing di qualunque cosa, per esempio di una operazione matematica. Ovviamente la cosa e' estremamente più facile in C++, usando una class invece di una struttura, in quanto l'operazione di confronto viene fatta all'interno della classe (ma lasciamo perdere a questo punto)

Sono stato vago nei dettagli, volutamente. Come hai visto non esiste un modo unico per implementare tale algoritmo.

Questo articolo e' famoso.

Niente di tutto questo ci è stato spiegato, l'esercizio ci è stato assegnato con le sole conoscenze del C fino ai puntatori, non abbiamo ancora visto liste e allocazioni dinamiche. Forse per questo sto riscontrando parecchie difficoltà.

 

[Andretti60]

char *Regexp(char *src, char *exp)
{
    char *res = 0;
    while(*src != 0)
    {
        if (confrontaStringa(src, exp) != 0)
        {
            res = src;
            break;
        }
        src++;
    }
    retun res;
}
int confrontaStringa(char *src, char *exp)
{
    int res = 0;
    
    .....
        
    return res;
}

Ok, torniamo quindi al tuo codice quindi e vediamo cosa ci sia di sbagliato.

devi avere due cicli while() innestati, quello esterno per la sorgente, e quello interno per la espressione regolare. Per fare le cose più chiare io eviterei di innestare gli while() e aggiungerei un’altra funzione

 

[Andretti60]

Scusa ma scrivere codice con un iPad è impossibile ?
Rompere il codice in più funzioni è tra i modi migliori per scrivere codice leggibile e pulito. Aziende che fanno software hanno perfino un numero massimo di linee di codice che possono essere usate in una funzione (in genere tra 10 e 20), anche dove lavoro io abbiamo questa regola. Un’altra cosa che imparai alla università: guardo il codice che scrissi allora (40 anni fa) e mi stupisco che lo posso ancora leggere e capire.

 

[ilfe98]

Scusa ma scrivere codice con un iPad è impossibile ?
Rompere il codice in più funzioni è tra i modi migliori per scrivere codice leggibile e pulito. Aziende che fanno software hanno perfino un numero massimo di linee di codice che possono essere usate in una funzione (in genere tra 10 e 20), anche dove lavoro io abbiamo questa regola. Un’altra cosa che imparai alla università: guardo il codice che scrissi allora (40 anni fa) e mi stupisco che lo posso ancora leggere e capire.

@Andretti60 Come al solito sempre sul pezzo! È sempre un piacere leggere una tua risposta, mi danno sempre qualche chicca in più, l'articolo in questo caso!
@Ledriana ho subito compreso che non ti fossero state spiegate alcune cose. Come detto da @Andretti60 il pattern matching seppur banale a livello di comprensione del problema, è complesso nel suo insieme. Mi sorprende che ti sia stato assegnato un esercizio di questo tipo. Il principale problema è il rischiare di perdersi nelle miriadi di condizioni imposte. È necessario che anziche gettarti nella programmazione cerchi di mettere un po' di ordine mentale. Un mio personale consiglio è modificare la sintassi degli if else con uno switch. Il fine è lo stesso ma visivamente lo switch è un organizzatore, elide problemi logici che si potrebbero genrare a monte con gli if else, questi ultimi sono una catena, se qualcosa non va in uno allora c'è una forte probabilità che gli altri cadano. Il costrutto switch limita il problema al caso in questione, ti è stato spiegato questo tipo di costrutto?
L'utilizzo di funzioni ausiliare all'interno dello switch è un ulteriore livello di eleganza attribuito al codice. In questo modo riuscirai ad isolare il problema in soltanto poche righe di codice.
In questo forum non c'è un limite al numero di messaggi. Possiamo trattare un caso per volta impostando la risoluzione insieme. Direi di utilizzare il metodo top down: Scomponi un problema grande iterativamente in tanti problemi elementari. Solo così puoi gestire questo numero di costanti da inserire

 

[Ledriana]

@Andretti60 Come al solito sempre sul pezzo! È sempre un piacere leggere una tua risposta, mi danno sempre qualche chicca in più, l'articolo in questo caso!
@Ledriana ho subito compreso che non ti fossero state spiegate alcune cose. Come detto da @Andretti60 il pattern matching seppur banale a livello di comprensione del problema, è complesso nel suo insieme. Mi sorprende che ti sia stato assegnato un esercizio di questo tipo. Il principale problema è il rischiare di perdersi nelle miriadi di condizioni imposte. È necessario che anziche gettarti nella programmazione cerchi di mettere un po' di ordine mentale. Un mio personale consiglio è modificare la sintassi degli if else con uno switch. Il fine è lo stesso ma visivamente lo switch è un organizzatore, elide problemi logici che si potrebbero genrare a monte con gli if else, questi ultimi sono una catena, se qualcosa non va in uno allora c'è una forte probabilità che gli altri cadano. Il costrutto switch limita il problema al caso in questione, ti è stato spiegato questo tipo di costrutto?
L'utilizzo di funzioni ausiliare all'interno dello switch è un ulteriore livello di eleganza attribuito al codice. In questo modo riuscirai ad isolare il problema in soltanto poche righe di codice.
In questo forum non c'è un limite al numero di messaggi. Possiamo trattare un caso per volta impostando la risoluzione insieme. Direi di utilizzare il metodo top down: Scomponi un problema grande iterativamente in tanti problemi elementari. Solo così puoi gestire questo numero di costanti da inserire

Si, ho già cambiato in uno switch, l'articolo che mi ha linkato @Andretti60 è stato estremamente chiarificatore. Purtroppo i miei prof sono estremamente bravi ma danno per scontate molte cose e non hanno mai programmato passo passo con noi, ci lasciano dei pezzi di codice sparsi per le slide e ci abbandonano al nostro destino. A volte si riesce, altre meno. Siete stati molto utili tutti e due. Grazie mille!

 

[Andretti60]

Mi sorprende che ti sia stato assegnato un esercizio di questo tipo.

me lo sono chiesto pure io.
Comunque @Ledriana lascia pure perdere il mio primo commento, visto l’esercizio pensavo tu fossi a un livello più avanzato. Non ti scoraggiare, tutti quanti devono pure iniziare. Posta pure qui i tuoi tentativi.