Grep

Program care printeaza liniile ce contin un anumit tipar

   Cei care folosesc linux au auzit, poate, de programul grep. Astazi o sa incercam sa implementam o versiune mai minimalista a acestuia in limbajul de programare C.

Rationamentul necesar pentru a crea un astfel de program este destul de simplu. In primul rand, ce dorim sa facem? Dorim sa facem un program care printeaza fiecare linie introdusa de utilizator ce contine un anumit tipar specificat de noi in "interiorul programului".
Sa spunem ca tiparul este test, daca utilizatorul introduce linia "am scris test", atunci, programul nostru o va printa din nou. Daca introduce input ce nu contine nici o ocurenta a acelui tipar, atunci nu o mai printam.

Rezumand ce am spus mai sus, asta ar fi schita programului:

cat timp utilizatorul introduce o linie executa
    daca linia contine o ocurenta a tiparului atunci
        printeaza acea linie

Iata si codul sursa:

#include < stdio.h >
#define MAXLINE 1000

int getline(char s[], int lim);
int strindex(char s[], char t[]);

int main() {
    char pattern[] = "test";
    char s[MAXLINE];

    while(getline(s, MAXLINE)) {
        if(strindex(s, pattern) >= 0) {
            printf("%s", s);
        }
    }
    return 0;
}

int getline(char s[], int lim) {
    int c, i;

    i = 0;
    while(--lim > 0 && (c = getchar()) != EOF && c != '\n') {
        s[i++] = c;
    }

    if(c == '\n') {
        s[i++] = c;
    }
    s[i] = '\0';

    return i;
}

int strindex(char s[], char t[]) {
    int i, j, k;

    for(i = 0; s[i] != '\0'; i++) {
        for(j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++)
            ;

        if(k > 0 && t[k] == '\0') {
            return i;
        }
    }
    return -1;
}

Programul nostru foloseste 3 functii esentiale - nemaipunand-o la socoteala pe main(). Aceste functii sunt: getline - folosita pentru a prelua input de la utilizator, strindex - folosita pentru a verifica ocurenta tiparului in string si printf - pentru a printa linia ce contine cel putin o ocurenta a tiparului. Din fericire functia printf a fost deja scrisa pentru noi de catre alti programatori, asa ca noi mai avem de implementata doar doua functii, respectiv getline si strindex.
Codul de mai sus a fost extras din cartea "The C programming language".

   Haideti sa explicam mecanismul de functionare al codului nostru. Sa incepem cu implementatia functiei getline. Declaram doua variabile de tipul int, c pentru a retine fiecare caracter, in parte, din linia citita si i pentru a tine evidenta  elementelor din array-ul unde se vor stoca caracterele citite.
Initializam variabila i cu valoarea 0 pentru a stoca elemente in array-ul s incepand de la indexul 0. Pe urmatoarea linie avem o bucla while ce se va opri atunci cand am depasit limita de caractere impusa pe o linie. Totusi, observi ca mai intai decrementam variabila lim si apoi o comparam cu valoarea 0. Probabil, te intrebi de ce? Facem acest lucru pentru a pastra o pozitie din array libera pentru caracterul null. Astfel, array-ul nostru va contine maxim 999 de caractere diferite de cel null  si caracterul null. Atunci ca observi operatorul de decrementare(--) sau de incrementare(++) in fata unei variabile, spunem ca am predecrementat/preincrementat acea variabila. Deci, lim va lua valoarea lim-1 si apoi va fi evaluata.

Urmatoarea conditie de oprire a buclei este ca sa ajungem la sfarsitul fisierului, daca am ajuns la sfarsitul fisierului oprim bucla. Cand am ajuns la sfarsitul fisierului variabila c va lua valoarea EOF - din acest motiv am declarat variabila c ca fiind int, pentru a putea retine valoarea sfarsitului de fisier.

Ultima conditie de oprirere a buclei este ca c sa ia valoarea line feed-ului('\n'). Totusi, te vei intreba de ce oprim bucla atunci cand gasim un line feed, dar pe liniile imediat urmatoare verificam daca c este egal cu un line feed, si daca este adaugam acel line feed in s. Vei spune ca am putea scoate ultima conditie din while si if-ul imediat urmator. Daca am face asa cum spui tu atunci functia noastra ar citi pana cand ajunge la sfarsitul fisierului, nu pana ala sfarsitul liniei. Deci array-ul s ar putea contine mai multe line feed-uri.

Dupa ce am adaugat line feed-ul in s, adaugam caracterul null pe pozitia imediat urmatoare si returnam valoarea varibilei i care este egala cu lungimea stringului s.

Sa descriem modul de functionare a functiei strindex.
Declaram 3 variabile de tipul int, i, j si k.  Pe linia urmatoare avem o bucla for ce duce variabila i pana cand s[i] va fi egal cu caracterul null, deci pana cand caracterul null se va afla pe pozitia i in array-ul s. 
In interiorul buclei for mai avem o alta bucla for ce initializeaza variabila j cu valoarea lui i si variabila k cu valoarea 0. Astfel, bucla va rula atat timp cat caracterul de pe pozitia j din s va fi egal cu caracterul de pe pozitia k din t si cat timp t[k] va fi diferit de caracterul null - deci, pana ajungem la sfarsitul stringului.

Apoi, in if-ul de pe pozitia urmatoare verificam daca bucla a rulat cel putin o data(k > 0) si daca a rulat pana la sfarsitul stringului(t[k] == '\0'). Prima conditie poate fi indeplinita daca unul sau mai multe caractere din s au fost egale cu cele din t, dar, atat timp cat nu au fost toate egale, inseamna ca nu se gaseste tiparul t in s. Daca conditia impusa de if a fost indeplinita cu succes, atunci returnam valoarea variabilei i - deci valoarea indexului din s de unde incepe prima ocurenta a tiparului t. In caz contrar returnam -1, avand in vedere ce array-urile sunt indexate de la 0, o valoare negativa este destul de convenabila pentru a exprima un status de eroare.

Codul din main() este foarte simplu, bucla while va rula atat timp valoarea returnata de getline este diferita de 0 - aceasta poate fi 0 atunci cand am ajuns la sfarsitul fisierului.
In interiorul buclei verificam daca in linia citita apare tiparul t, daca apare - adica valoarea returnata de strindex este mai mare sau egala cu 0 - printam linia abia citita.