13. hét: generikus algoritmusok, állapotgépek

Czirkos Zoltán, Nagy Gergely, Pohl László · 2016.08.28.

Gyakorlófeladatok a 13. előadás anyagához kapcsolódóan.

1. Függvénypointerek

Függvénypointerek tömbje

Vizsgán volt

Definiálj olyan 3 elemű tömböt, amely olyan mutatókat tartalmaz, melyek a fenti feladat függvényére mutathatnak!

Megoldás

/* így néz ki a függvény, amiről szó van */
int fv(int *t, int meret);

/* így néz ki egy, a fenti típusú függvényre mutató pointer */
/* a neve lesz a pointer neve; elé csillag, és zárójelbe. */
int (*pfv)(int *t, int meret);

/* ha ezekből kell egy 3 elemű tömb, akkor nem egy pfv pointer
   van, hanem egy három elemű tpfv tömb. a paraméterek nevei
   természetesen itt is, és eggyel feljebb is elhagyhatóak,
   vagyis mindkét lenti sor egyformán jó. */

int (*tpfv[3])(int *t, int meret);          /* <- ez a megoldás */
int (*tpfv[3])(int *, int);                 /* <- vagy ez is jó */

Ugyanúgy kell mindent deklarálni, ahogy használni fogjuk! tpfv az egy tömb, amit ha megindexelünk [3], akkor kapunk egy pointert *, ami egy (int *, int) paraméterű függvényre mutat, amit meghívva egy int a visszatérési értéke.

A (*pfv) köré azért kell a zárójel, mert nélküle int * pointerrel visszatérő függvény lenne, nem pedig pedig függvényre mutató pointer:

int *fv(int*, int);         /* int* függvény */
int (*pfv)(int*, int);      /* int függvényre mutató ptr */

foreach()

Írj függvényt, amely átvesz egy int típusú elemekből álló tömböt, annak méretét, valamint egy olyan függvényt, amely egy int paramétert vár és visszatérési értéke void. A megírandó függvény járja végig a tömböt és minden elemére hívja meg a paraméterként átvett függvényt!

qsort() valós számok tömbjére

A qsort() könyvtári függvény generikus, segítségével bármilyen típusú adatok rendezhetőek. A rendezéshez az adott, általunk használt adattípushoz készítenünk kell egy összehasonlító függvényt. Készíts egy olyan függvényt, amelyik int típusú számok összehasonlításához használható a qsort()-hoz. Mutass példát, hogyan kell használni a függvényt!

Megoldás

int integer_osszehasonlito(const void *pelso, const void *pmasodik) {
    const int *elso = (const int *)pelso;
    const int *masodik = (const int *)pmasodik;

    if (*elso < *masodik)
        return -1;
    if (*elso > *masodik)
        return 1;
    return 0;
}


int intek[5];
int i;

/* veletlen elemek */
srand(time(0));
for (i = 0; i < 5; i++)
    intek[i] = rand()%100;

/* rendezes es kiiras */
/* itt az int-et batran sizeofolhatom */
qsort(intek, 5, sizeof(intek[0]), integer_osszehasonlito);
for (i = 0; i < 5; i++)
    printf("%d ", intek[i]);
printf("\n");

qsort() pontok tömbjére

Adott a következő, pontok koordinátáit tároló rekord:

struct pont {
    double x;
    double y;
};

Egy ilyenekből álló tömböt szeretnénk rendezni úgy, hogy az origótól lévő távolságuk szerint növekvő sorrendben legyenek. A rendezéshez a qsort() könyvtári függvényt használjuk. Írd meg az ennek negyedik paraméterében használható összehasonlító függvényt.

Sztringek visszafelé

Írj összehasonlító függvényt a qsort() számára, amellyel sztringek visszafelé (csökkenő) sorrendbe rendezhetőek! Mi erre a legegyszerűbb megoldás?

Megoldás

A strcmp() visszatérési értéke pozitív vagy negatív, nagyobb vagy kisebb sztring esetén. Ezt negálva megfordul a sorrend:

int strcmp_neg(void const *pa, void const *pb) {
    return -1 * strcmp((char const *) pa, (char const *) pb);
}

Még rövidebb megoldáshoz jutunk, ha fordítva adjuk neki a paramétereket, hiszen ha a<b, akkor b>a:

int strcmp_neg(void const *pa, void const *pb) {
    return strcmp((char const *) pb, (char const *) pa);
}

Numerikus integrálás

Tekintsünk egy valós, egyváltozós függvényt, például:

double fv(double x) {
    return x*x + 2*x + 5;
}

Írj C függvényt, amelyik trapéz-módszerrel numerikus integrálást végez. Visszatérési értéke legyen az integrál értéke; paraméterei az integrálandó függvény, az intervallum és a lépésköz.

Egyenlet megoldása

Készíts függvényt, ami egy folytonos függvény nullahelyét megkeresi egy adott intervallumban, intervallumfelezéssel. A függvény paraméterként kapja az intervallumot, amelyben keres, és a függvény pointerét. Építsen be egy hibahatárt, amelyen belül a nullahelyet megtaláltnak tekinti. A függvény a nullahely valós értékével térjen vissza.

Generikus lista és fa

A láncolt lista és a bináris fa példák olyan adatszerkezetekre, amelyekre minden programnak szüksége lehet. Ezek kezelésének módja (például listaelem beszúrása) független attól, hogy milyen adatokat tartalmaznak.

Deklarálj olyan listát, amely típus nélküli mutató segítségével tetszőleges adatot képes tárolni! Írj függvényeket, amelyek a lista elejére, végre fűznek egy elemet, illetve egy megadott elemet törölnek a listából!

Végezd el ugyanezt bináris fára is! A beszúráskor végzendő összehasonlításhoz vegyél át egy függvényt, amely összehasonlítja a két beszúrandó adatot, és amelynek a visszatérési értéke hasonlít az strcmp()-éhez!

double-öket rendező függvény

Írjunk függvényt, amely paraméterként kap egy double elemekből álló tömböt, és rendezi azt! A rendezés szempontja (növekvő, csökkenő, abszolútérték szerint növekvő stb.) is legyen a függvény paramétere!

Megoldás

#include <stdio.h>
#include <math.h>

/* rendezi a tombot a megadott szempont szerint */
void double_rendez(double tomb[], int meret, bool (*kisebb_e)(double a, double b)) {
    int i;

    for (i = 0; i < meret - 1; ++i) {
        int lk = i;
        int j;
        double temp;

        for (j = i + 1; j < meret; ++j)
            if (kisebb_e(tomb[j], tomb[lk]))
                lk = j;

        temp = tomb[lk];
        tomb[lk] = tomb[i];
        tomb[i] = temp;
    }
}

/* igaz, ha a<b */
bool kisebb(double a, double b) {
    return a < b;
}

/* igaz, ha |a|<|b| */
bool abszolut_kisebb(double a, double b) {
    return fabs(a) < fabs(b);
}

int main(void) {
    int i;
    double tomb[10] = {1.2, 5.6, 9, -1.4, -6, 5, 9.1, 11, 0, -12};

    double_rendez(tomb, 10, kisebb);
    for (i = 0; i < 10; ++i)
        printf("%7.2f", tomb[i]);
    printf("\n");

    double_rendez(tomb, 10, abszolut_kisebb);
    for (i = 0; i < 10; ++i)
        printf("%7.2f", tomb[i]);
    printf("\n");

    return 0;
}

A fenti függvények nem követik az strcmp() konvenciót: az összehasonlító függvények nem kompatibilisek azzal. Azonban nincs is erre szükség itt még, hiszen a rendezendő adatok típusa adott.

Saját generikus rendező függvény

Alakítsuk át az előbbi rendezőfüggvényünket úgy (bármelyik algoritmust is választottuk), hogy ne double, hanem tetszőleges elemekkel dolgozzon!

Megoldás

Ehhez a függvénynek void* pointerrel kell átvennie a tömböt (mivel a típusait nem ismeri), és ugyancsak paraméter kell legyen az egyes elemek mérete is. Az elemek cseréje nem végezhető el értékadással, de segítségül hívhatjuk a memcpy függvényt, amely adott méretű memóriaterületet másol. Az „ideiglenes változó” helyébe – amely a háromlépéses cseréhez kell – is egy külön, típus nélküli memóriaterület lép. Mivel ennek mérete függvényparaméter, dinamikusan foglaljuk. A hasonlító függvény is void*-okat kell várjon, nem pedig double-öket.

void rendez(void *tomb,
            int meret, size_t elemmeret,
            bool (*kisebb_e)(void const *pa, void const *pb)) {
    int i;
    void *temp;

    temp = malloc(elemmeret);

    for (i = 0; i < meret - 1; ++i) {
        void *pi = (char*)tomb + i * elemmeret;
        void *plk = pi;

        int j;
        for (j = i + 1; j < meret; ++j) {
            void *pj = (char*) tomb + j * elemmeret;
            if (kisebb_e(pj, plk))
                plk = pj;
        }

        if (plk != pi) {
            memcpy(temp, plk, elemmeret); /* temp=lk */
            memcpy(plk, pi, elemmeret);   /* lk=i */
            memcpy(pi, temp, elemmeret);  /* i=temp */
        }
    }

    free(temp);
}

A teljes program letölthető innen: genrend.c.

2. Állapotgépek

Kettős mássalhangzók

Készíts kettős mássalhangzó számláló programot!

a.) Írj programot, mely a billentyűzetről érkező karaktereket figyeli, és megszámolja a beírt szövegben található "ly" és "sz" kettős mássalhangzójú betűk számát. A szöveget nem tárolhatja el a program, csak a találatok számát. A szöveg beírása és a számlálás a fájl vége jellel véget ér, ekkor a program írja ki tételesen az összeszámlált mennyiségeket.

b.) Az előbbi programot egészítsd ki azzal, hogy a "zs" betűket is számolja, de vigyázz: egy leütött karaktert csak egyetlen kettős mássalhangzójú betűhöz számold, méghozzá az elsőhöz (pl. "egészség": 1 db "sz", 0 db "zs")!

Mondatszámláló

Adja meg egy tetszőleges, standard bemenetről érkező szövegről, hogy hány mondat van benne. Mondatnak tekintünk minden olyan karaktersorozatot, amelyik nagybetűvel kezdődik, ponttal, kérdőjellel vagy felkiáltójellel végződik.

HTML formátum

Írj programot, amelyik HTML formátumú fájlból eltávolítja a szedés jelöléseit, vagyis a <…> szerű karaktersorozatokat, ezzel többé-kevésbé olvashatóvá téve azt normál szövegként. (Például <br>, <title>).

Szavak

Írj olyan programot, amely külön-külön sorokban nyomtatja ki a bemenetére érkező szavakat!

Szmájli számláló I.

Kis ZH volt

Írj állapotgépes programot, amely a szabványos bemenetről olvasott szövegben megszámolja a szomorú :( és a vidám :) szmájlikat. A számlálás után kiírja, hogy a szöveg vidám, szomorú vagy közömbös, azaz több, kevesebb vagy ugyanannyi :) volt, mint :(.

Tervezd meg az állapotgépet állapot- és tevékenységtáblával, utána írd meg a programot! A programra csak akkor jár pont, ha állapotgépes és a leírt állapottáblát valósítja meg.

Megoldás

: ( ) többi
alap →kp - - -
kp - szom++, →alap vid++, →alap →alap
#include <stdio.h>

int main(void) {
    enum Allapot { alap, kp } all;

    all = alap;
    int szom = 0, vid = 0;
    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case alap:
            if (c == ':') all = kp;
            break;
        case kp:
            if (c == ')')      vid++;
            else if (c == '(') szom++;
            if (c != ':') all = alap;
            break;
        }
    }

    if (vid > szom) printf("vidam");
    else if (szom < vid) printf("szomoru");
    else printf("kozombos");

    return 0;
}

Szmájli számláló II.

Kis ZH volt

Írj állapotgépes programot, amely a szabványos bemenetről olvasott szövegben megszámolja a szomorú :( és a vidám :) szmájlikat. A számlálás után kiírja, hogy a szöveg vidám, szomorú vagy közömbös, azaz több, kevesebb vagy ugyanannyi :) volt, mint :(. A szmájlik zárójelenként egynek számítanak, vagyis :))) három vidámat, :(( két szomorút jelent.

Tervezd meg az állapotgépet állapot- és tevékenységtáblával, utána írd meg a programot! A programra csak akkor jár pont, ha állapotgépes és a leírt állapottáblát valósítja meg.

Megoldás

: ( ) többi
alap →kp - - -
kp - szom++ vid++ →alap
#include <stdio.h>

int main(void) {
    enum Allapot { alap, kp } all;

    all = alap;
    int szom = 0, vid = 0;
    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case alap:
            if (c == ':') all = kp;
            break;
        case kp:
            if (c == ')')   vid++;
            else if (c == '(') szom++;
            else if (c != ':') all = alap;
            break;
        }
    }

    if (vid > szom) printf("vidam");
    else if (szom < vid) printf("szomoru");
    else printf("kozombos");

    return 0;
}

Sz és zs számláló

Kis ZH volt

Írj állapotgépes programot, amely a szabványos bemenetről olvasott szövegben megszámolja az „sz” és a „zs” betűket! (Hosszú ssz és zzs is egynek számítanak, azokkal külön nem kell foglalkozni.) A számlálás után írd ki a szabványos kimenetre mindkettő darabszámát!

Tervezd meg az állapotgépet állapot- és tevékenységtáblával, utána írd meg a programot! A programra csak akkor jár pont, ha állapotgépes és a leírt állapottáblát valósítja meg.

Megoldás

s z többi
alap →svolt →zvolt -
svolt - sz++, →alap →alap
zvolt zs++, →alap - →alap
#include <stdio.h>

int main(void) {
    enum Allapot { alap, svolt, zvolt } all;
    int c, sz, zs;

    all = alap;
    sz = zs = 0;

    while ((c = getchar()) != EOF) {
        switch (all) {
        case alap:
            if (c == 's') all = svolt;
            else if (c == 'z') all = zvolt;
            break;
        case svolt:
            if (c == 'z') sz++;
            if (c != 's') all = alap;
            break;
        case zvolt:
            if (c == 's') zs++;
            if (c != 'z') all = alap;
            break;
        }
    }

    printf("sz: %d, zs: %d\n", sz, zs);

    return 0;
}

Dzs számláló

Kis ZH volt

Írj állapotgépes programot, amely a szabványos bemenetről olvasott szövegben megszámolja a „dzs” betűket! (Hosszú ddzs egynek számít, nem kell külön foglalkozni vele.) A számlálás után írd ki a szabványos kimenetre a darabszámot!

Tervezd meg az állapotgépet állapot- és tevékenységtáblával, utána írd meg a programot! A programra csak akkor jár pont, ha állapotgépes és a leírt állapottáblát valósítja meg.

Megoldás

d z s többi
alap →dvolt - - -
dvolt - →dzvolt →alap →alap
dzvolt →dvolt →alap dzs++, →alap →alap
#include <stdio.h>

int main(void) {
    enum Allapot { alap, dvolt, dzvolt } all;

    all = alap;
    int dzs = 0;
    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case alap:
            if (c == 'd') all = dvolt;
            break;
        case dvolt:
            if (c == 'd') ;
            else if (c == 'z') all = dzvolt;
            else all = alap;
            break;
        case dzvolt:
            if (c == 's') dzs++;
            if (c == 'd') all = dvolt;
            else all = alap;
            break;
        }
    }

    printf("dzs: %d\n", dzs);

    return 0;
}

Sztringek belseje I.

A négy állapotos C kommentszűrő program (lásd a vonatkozó órai feladatot) nem működik tökéletesen. Ugyanis ez a kód nem tartalmaz kommentet:

printf("/* ez nem komment. */\n");

Javítsd ki úgy az állapotgéped, hogy kezelje ezt is!

Sztringek belseje II.

Hol van vége egy sztringnek? Nem az indító idézőjel utáni következő idézőjel karakternél:

printf("A program azt irja ki, hogy \"Hello, /* nem komment */ vilag\".\n");

Fejleszd tovább az előző feladat állapotgépét eszerint!

Kommentben komment

A C szabvány tiltja a /* */ kommentek egymásba ágyazását. (Tetszőleges mélységben egymásba ágyazott kommenteket nem lehetne állapotgéppel feldolgozni.) Éppen ezért, ha a fordítók kommentben kommentet látnak, figyelmeztető hibajelzést szoktak adni. Egészítsd úgy ki a kommentszűrő programodat, hogy írjon ki hibaüzenetet, ha komment belsejében /* karaktersorozatot talál!

Multifilter

Írd át a kommentszűró programot úgy, hogy ne csak a /* és */ karakterpárokra működjön, hanem tetszőleges karakterpárokra! Pl. a Pascal nyelvben a kommenteket (* és *) karakterekkel is lehetett jelölni. A kezdő- és végpárokat a felhasználó egy konfigurációs fájlban (multifilter.ini) adhassa meg a programnak! A program ellenőrizze, hogy létezik-e a fájl, és ha nem, adjon hibajelzést, majd lépjen ki! (Ha sikerült megnyitnia a fájlt, abban négy karakternek kell lennie; a nyitó kombinációnak, két karakter, és a záró kombinációnak, újabb két karakter. C-hez a fájlban /**/ lenne, Pascalhoz (**).)

C++ komment

Kis ZH volt

A feladat a szabványos bemenetről érkező szövegben (fájl vége jelig) megszámolni, hogy hány C++ komment van benne, és a darabszámot kiírni. A C++ komment két / (per) jellel kezdődik, és a sor végéig tart, pl.:

printf("Hello"); // Üdvözlet
Ha C++ kommenten belül van „//” karakterpár, az nem növeli a kommentek számát. Készíts állapotgépes modellt állapottábla és tevékenységtábla megadásával, majd valósítsd meg C program formájában!

Megoldás

#include <stdio.h>

int main(void) {
    int c, szaml = 0;
    enum Allapot { kod, pervolt, komment } all = kod;
    all = kod;
    while ((c = getchar()) != EOF) {
        switch (all) {
            case kod:
                if (c == '/')
                    all = pervolt;
                break;
            case pervolt:
                if (c == '/') {
                    szaml++;
                    all = komment;
                } else
                    all = kod;
                break;
            case komment:
                if (c == '\n')
                    all = kod;
                break;
        }
    }
    printf("%d darab komment", szaml);
    return 0;
}

Haskell komment

Kis ZH volt

A feladat a szabványos bemenetről érkező Haskell nyelvű programkódban megszámolni, hogy hány komment van benne, és a darabszámot kiírni. A szöveg végét fájl vége jelzi. A Haskell komment két - (mínusz) jellel kezdődik, és a sor végéig tart, pl.:

lesser = filter (< p) xs -- kivalogatja a p-nel kisebbeket
Ha a kommenten belül van „--” karakterpár, az nem növeli a kommentek számát. Készíts állapotgépes modellt állapottábla és tevékenységtábla megadásával, majd valósítsd meg C program formájában!

Megoldás

#include <stdio.h>

int main(void) {
    int c, szaml = 0;
    enum Allapot { kod, minuszvolt, komment } all = kod;
    all = kod;
    while ((c = getchar()) != EOF) {
        switch (all) {
            case kod:
                if (c == '-')
                    all = minuszvolt;
                break;
            case minuszvolt:
                if (c == '-') {
                    szaml++;
                    all = komment;
                } else
                    all = kod;
            case komment:
                if (c == '\n')
                    all = kod;
                break;
        }
    }
    printf("%d darab komment", szaml);
    return 0;
}

Üres sorok száma

Kis ZH volt

A feladat a szabványos bemenetről érkező szövegben (fájl vége jelig) megszámolni, hogy hány üres sor van benne. A szöveget a szabványos kimenetre ki is kell írni változatlanul, majd a szöveg után az üres sorok darabszámát. Üres sornak számít az, amiben nincs karakter, de az is, amiben csak szóközök vannak. Készíts állapotgépes modellt állapottábla és tevékenységtábla megadásával, majd valósítsd meg C program formájában!

Megoldás

#include <stdio.h>

int main(void) {
    enum Allapot { soreleje, sorbelseje } all = soreleje;
    int c, szaml = 0;
    while ((c = getchar()) != EOF) {
        putchar(c);
        switch (all) {
            case soreleje:
                if (c == '\n')
                    szaml++;
                else if (c != ' ')
                    all = sorbelseje;
                break;
            case sorbelseje:
                if (c == '\n')
                    all = soreleje;
                break;
        }
    }
    printf("%d ures sor volt.", szaml);
    return 0;
}

C sztring feldolgozása

Kis ZH volt

A feladat a szabványos bemenetről érkező C sztring feldolgozása: a szövegben szereplő \n, \t és \" karakterpárokat a megfelelő karakterrel (újsor, tabulátor, idézőjel) helyettesíteni, és úgy írni a szabványos kimenetre. (Egyéb \+karakter párok nem szerepelnek a sztringben, kezelésük tetszőleges.) Készíts állapotgépes modellt állapottábla és tevékenységtábla megadásával, majd valósítsd meg C program formájában! Pl. be:

hello \n    \"világ\"

ki:

hello
    "világ"!

Megoldás

#include <stdio.h>

int main(void) {
    enum Allapot { alap, visszaper } all = alap;
    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
            case alap:
                if (c == '\\')
                    all = visszaper;
                else
                    putchar(c);
                break;
            case visszaper:
                switch (c) {
                    case 'n':
                        putchar('\n');
                        break;
                    case 't':
                        putchar('\t');
                        break;
                    case '"':
                        putchar('"');
                        break;
                }
                all = alap;
                break;
        }
    }
    return 0;
}

A1llapotge1p

A számítástechnika hőskorában nem lehetett magyar nyelvű billentyűzetet kapni, sőt az operációs rendszerek még nem támogatták a magyar nyelvű billentyűzetkiosztást sem. Magyar nyelvű, ékezetes szövegeket azonban akkor is kellett írni. Az egyik szövegfeldolgozó program úgy oldotta meg a problémát, hogy az adott, ékezet nélküli magánhangzó után tett 1-es, 2-es és 3-as számjegyekkel jelezte a különféle ékezeteket. Az 1-es jelezte a hosszú magánhangzót (pl. á = a1), a 2-es a két pontot (pl. ö = o2), és a 3-as a csak a magyar nyelvben előforduló hosszú ő és ű betű jelölésére szolgált (pl. ő = o3).

Írj állapotgépes programot, amely egy ilyen módon kódolt szöveget átalakít rendes, ékezetes szöveggé!

Gondolkodtató részfeladatok:

  • Oldd meg, hogy hibás bemeneti kombinációkra hibajelzést adjon a program! Pl. az a2 kombináció hibás, mivel az ä betűt jelentené, amely viszont a magyar nyelvben nem használatos.
  • Érdemes minden magánhangzónak külön állapotot létrehozni? Ne felejtsd el, hogy összesen tíz állapotra vonatkozik ez a kérdés, hiszen nem csak az a, e, i, o és u karakterek után jelentenek mást az 1, 2 és 3 számjegyek, hanem az A, E, I, O és U karakterek után is. Lehetne valahogy paraméterezni az állapotokat?

C++ kommentszűrő

A C++ nyelvben a kommentek a // karakterekkel kezdődnek, és a sor végéig tartanak. (Természetesen az egy / továbbra is osztást jelent.) Ezt a fajta kommentet olyan kényelmesnek találta mindenki, hogy szép lassan a C-be is beépítették: a nyelv 1999-es, C99 szabványa már ismeri azt.

Írj programot, amelyik a szabványos bemenetén érkező, //-es kommenteket tartalmazó forráskódból kiszűri a kommenteket! Figyelj arra, hogy ettől a program tördelése ne változzon meg: ami eredetileg két sorba volt törve, az a kimeneten is így szerepeljen.

Megoldás

/\negyéb
alap→perki: cki: c
perkommentki: /, \n
→alap
ki: /, c
→alap
komment-ki: \n
→alap
-

C++ komment → C komment

Egy C99 szabvány szerinti, //-es kommenteket is tartalmazó forráskódot szeretnénk lefordítani egy nagyon régi C fordítóval, amely csak a /*-os kommenteket ismeri. Alakítsd át úgy az előző kommentszűrődet, hogy a kitörlés helyett tartsa meg a //-es kommenteket, de alakítsa át azokat /*-os formára!

Pl. ha a bemenete ilyen:

#include <stdio.h>

int main(void) {
    printf("Helló világ!\n");   // Üdvözlet
    return 0;
}

Akkor a kimenete legyen ilyen:

#include <stdio.h>

int main(void) {
    printf("Helló világ!\n");   /* Üdvözlet */
    return 0;
}

Megoldás

A megtalált komment elejénél kiír egy /* karaktersorozatot. A komment belsejében minden karaktert kiír (ahogy máskor is). A komment végén, az újsor a karakternél pedig kiírja a bezáró */-ot, és persze az újsort is (hogy a forráskód tördelése ne változzon).

/\negyéb
alap→perki: cki: c
perki: /*
→komment
ki: /, \n
→alap
ki: /, c
→alap
kommentki: cki: */\n
→alap
ki: c

Kommentszűrő táblázattal

Dolgozd át a fenti kommentszűrő programot úgy, hogy a program kódjában is táblázatos állapotgép szerepeljen: lásd az előadásanyagot.

Rövidítések

Írjunk állapotgépes mondatot, amely a soronkért beírt tulajdonnevekből rövidítéseket csinál. Írja ez ki minden szó első betűjét. Pl.

Budapesti Muszaki Egyetem
BME
Elektronikus Eszkozok Tanszeke
EET

Megoldás

A tervezés két állapotot ad: azt, amikor várunk a szó első betűjére (mert azt kell kiírni), és azt, amikor egy szó belsejében vagyunk.

szóköz\negyéb
szóra vár--ki: c
→szóban
szóban→szóra várki: \n
→szóra vár
-
#include <stdio.h>
#include <ctype.h>

int main(void) {
    enum Allapot { szora_var, szoban };
    
    int c;
    enum Allapot all;
    
    all=szora_var;
    while ((c=getchar()) != EOF) {
        switch (all) {
            case szora_var:
                if (!isspace(c)) {
                    putchar(c);
                    all=szoban;
                }
                break;
            case szoban:
                if (c=='\n')
                    putchar(c);
                if (isspace(c))
                    all=szora_var;
                break;
        }
    }
    
    return 0;
}

Mondat második szava

Tervezz állapotgépes programot, amelyik a szabványos bemeneten olvasott szövegből minden mondat második szavát írja csak ki! Jelenjenek meg ezek a szavak külön sorban!

Megoldás

A tervezést az „új mondat” állapotnál kell kezdeni. Ide kell kerülnie egy bejövő pont, felkiáltójel vagy kérdőjel karakter hatására a gépnek – de az induláskor is. Ettől meg kell különböztetni az „első szó” állapotot, amelybe akkor kerülünk, amikor az első, szó betűjeként értelmezhető karaktert megkapjuk. Innen a „második szóra vár” állapotba egy újabb szóköz (vagy szóelválasztó) hatására kerülünk. Ez még nem a „második szó” állapot, ahol majd ki kell írni a beolvasott betűket (és ahonnan tovább ugrunk egy újabb szóelválasztó hatására), hiszen itt még sok szóelválasztó jöhet (pl. szóköz), ami még nem jelenti a második szó elkezdését. Ha betűt kapunk, az viszont már igen, és az a második szó első betűje kell legyen, ezért ki is írjuk. Azután egy újabb szóelválasztó hatására onnantól „mondat vége” állapotban működik tovább a gép, és már nem figyel semmire, csak várja a következő mondatelválasztó karaktert, amely hatására minden elölről kezdődik.

. ! ?szóköz \n , : ;egyéb
új mondat--→első szó
első szó→új mondat→második szóra vár-
második szóra vár→új mondat-kiír: c
→második szó
második szó→új mondat→mondat vége
kiír: \n
kiír: c
mondat vége→új mondat--

Érdemes a mondatelválasztó és a szóelválasztó karakter felismeréséhez segédfüggvényeket írni.

#include <stdio.h>
#include <stdbool.h>

/* Igazzal tér vissza, ha a karakter mondat végét jelzi. */
bool mondatvege_jel(int c) {
    return c == '!' || c == '.' || c == '?';
}

/* Igaz, ha a karakter szó végét jelzi. Nem csak szóköz lehet,
 * hanem pl. vessző, pontosvessző is. */
bool szovege_jel(int c) {
    return c == ' ' || c == '\n' || c == ':' || c == ',' || c == ';';
}

int main(void) {
    enum Allapot { ujmondat, elsoszo, masodikszoravar, masodikszo, mondatvege };

    int c;
    enum Allapot all = ujmondat;

    while ((c = getchar()) != EOF) {
        switch (all) {
        case ujmondat:
            if (!mondatvege_jel(c) && !szovege_jel(c))
                all = elsoszo;
            break;
        case elsoszo:
            if (mondatvege_jel(c))
                all = ujmondat;
            else if (szovege_jel(c))
                all = masodikszoravar;
            break;
        case masodikszoravar:
            if (mondatvege_jel(c))
                all = ujmondat;
            else if (!szovege_jel(c)) {
                putchar(c);
                all = masodikszo;
            }
            break;
        case masodikszo:
            if (mondatvege_jel(c))
                all = ujmondat;
            else if (szovege_jel(c)) {
                putchar('\n');
                all = mondatvege;
            }
            else
                putchar(c);
            break;
        case mondatvege:
            if (mondatvege_jel(c))
                all = ujmondat;
            break;
        }
    }

    return 0;
}