Gyakorlat, 13. hét: állapotgépek

Czirkos Zoltán · 2019.08.24.

Állapotgépek tervezése.

Állapotgépek. A feladatok megoldásának lényege az, hogy az állapotátmeneti táblát és a tevékenyságtáblát megalkotjuk: az állapotgépet megtervezzük. Ha ez megvan, akkor onnantól a kódolás már mechanikus. Egy olyan feladatnál, ahol több állapotátmenet is van, nem lehet csak úgy nekiugrani a kódolásnak! Ha a táblázat megalkotása után fejből írunk valami kódot, nem a tábla alapján, annak sincs semmi értelme. Az is értelmetlen, ha a kettőt fordított sorrendben csináljuk meg…

A tervezés után az állapotgépet mindenképpen le kell tisztázni egy állapottáblával. A gráfot nézve ugyan jobban lehet mélázgatni az állapotátmeneteken, a táblázat sokkal áttekinthetőbb, és biztosítja azt is, hogy semelyik átmenetet sem hagytuk ki. A kódolás során pedig kifejezetten jobb abból dolgozni.

Felkészülés a gyakorlatra:

1. Próba ZH

A feladat segít felmérni, hogy állsz a tanulással. A szövege csak a többi megoldással együtt jelenik meg. Óra után pedig rögzítsd a pontszámod – a dolgozat nálad marad.

Feladat

Válaszolj röviden az alábbi kérdésekre:

#include <stdio.h>
#include <ctype.h>

int main(void) {
    int c;
    while ((c = getchar()) != EOF)
        putchar(tolower(c));
    return 0;
}
  1. Mit csinál a program?
  2. Miért int típusú a változó?
  3. Miért kell a zárójel az értékadásnál? Rajzold fel a kifejezésfát a ciklusfeltételhez!
  4. Miért visszatérési értékben adja a tolower() függvény a karaktert?
  5. Működik a program számok vagy írásjelek esetén is? Miért?
  6. Megírható ez a program a scanfprintf függvénypárral is? Hogyan?
Mintamegoldás és pontozási útmutató

Minden válasz 1 pontos. Ha nem elég rövid, szabatos a válasz, vagyis túl sok a rizsa benne, akkor viszont nem járt a pont. (Pl. ha a felét ki lehet húzni, mégis megmarad a lényegi információ.)

  1. A beírt szöveget kisbetűsítve írja ki.
  2. Mert a getchar() értéke EOF is lehet, amelyik a char típus ábrázolási tartományán kívül esik.
  3. A precedencia miatt; hogy a változóba kerülő értéket (karakterkódot) vizsgáljuk, ne pedig az összehasonlítás eredményét tegyük a változóba.
  4. Átvehetné cím szerint is: tolower(&c), de nem ezt a megoldást választották.
  5. Igen, mert a tolower() függvény ezeket változatlanul adja vissza.
  6. Igen, így:
    char c;
    while (scanf("%c", &c) == 1)
        printf("%c", tolower(c));
    A scanf-es sorban != EOF is lehet, viszont a változó mindenképp char c kell legyen ebben az esetben.

2. Mondatok nagybetűsítője

A feladat az előző műveletet megcsinálni „visszafelé”. Vagyis olyan programot kell írni, amely a beírt, csupa kisbetűkből álló szöveget javítja ki, méghozzá úgy, hogy minden mondat elején álló első betűt nagybetűre cseréli.

Megoldás

Ehhez állapotgép kell. Mondat végét jelző írásjel után a következő betű nagybetű, de csak akkor, ha szóköz is jött. Figyelni kell, hogy az utána lévő szóköztől nem váltunk kisbetűs módra még! A gép alapállapota a nagybetűsítés, hiszen a bejövő szöveg legelső karaktere biztosan mondat elején van.

. ! ?szóköz, \negyéb
nagybetűki: cki: cki: toupper(c)
→kisbetű
kisbetűki: c
→mondatvége?
ki: cki: c
mondatvége?ki: cki: c
→nagybetű
ki: c
→kisbetű
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

bool mondatvege_jel(int c) {
    return c == '!' || c == '.' || c == '?';
}

int main(void) {
    enum allapot {
        nagybetu,
        kisbetu,
        mondatvege
    } all;
    all = nagybetu;     /* kiindulo allapot */

    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case nagybetu:
            putchar(toupper(c));
            if (!mondatvege_jel(c) && !isspace(c))
                all = kisbetu;
            break;
        case kisbetu:
            putchar(c);
            if (mondatvege_jel(c))
                all = mondatvege;
            break;
        case mondatvege:
            putchar(c);
            if (isspace(c))
                all = nagybetu;
            else if (!mondatvege_jel(c))
                all = kisbetu;
            break;
        }
    }

    return 0;
}

3. C kommentek

Írj programot, amely a szabványos bemenetről olvas karaktereket fájl vége jelig! A szabványos bemeneten keresztül egy C program érkezik. A program szűrje ki a /* és */ közötti megjegyzéseket a szabványos bemeneten érkező szövegből, és a megjegyzések nélküli szöveget írja a szabványos kimenetre!

Megoldás

Az állapotátmeneteket itt is nyilak jelölik, a többi jelzés pedig a kiírandó karaktereket mutatja. A c betű az aktuálisan beolvasott karaktert jelenti. Az állapotgép ezen változata nem vesz tudomást a sztringekről, pl. nem veszi figyelembe azt, hogy "a/*b" nem komment.

/ * egyéb
alap →per '*' c
per '/' →komment
' '
→alap
'/', c
komment →vége
vége →alap →komment
#include <stdio.h>

int main(void) {
    typedef enum Allapot { alap, per, komment, csillag } Allapot;

    int c;
    Allapot all = alap;
    while ((c = getchar()) != EOF) {
        switch (all) {
            case alap:
                if (c == '/') {
                    all = per;
                } else {
                    putchar(c);
                }
                break;
            case per:
                if (c == '/') {
                    putchar('/');
                } else if (c == '*') {
                    putchar(' ');
                    all = komment;
                } else {                       
                    putchar('/');
                    putchar(c);
                    all = alap;
                }
                break;
            case komment:
                if (c == '*') {
                    all = csillag;
                }
                break;
            case csillag:
                if (c == '/') {
                    all = alap;
                } else if (c == '*') {
                    all = csillag;
                }
                else {
                    all = komment;
                }
                break;
        }
    }

    /* Ha véget ért a bemenet, elvileg alapállapotban kell lennünk, mert
     * a forráskód nem végződhet bezáratlan kommenttel. Esetleg lehetséges,
     * hogy egy perjel volt a végén, az viszont nem a komment vége, hanem
     * egy osztás: írjuk ki! */
    if (all == per) {
        putchar('/');
    }
    return 0;
}

4. Zárójeles szöveg

Írjunk állapotgépes programot, amelyik egy adott szövegből eltávolítja a (zárójelezett részeket). Előfordulhat, hogy a zárójelek tetszőleges mélységben egymásba vannak ágyazva (például így, mint ez a (zárójeles) szó).

Megoldás

Nem lehet megoldani véges számú állapotot tartalmazó állapotgéppel. Minden bezáró zárójel „)” esetén tudni kellene, hogy hány be nem zárt zárójel van még; ez annyiféle „(” utáni állapotot feltételez. A feladat szövege szerint pedig ezekből tetszőlegesen sok lehetne. Ellenben állapotváltozónak használhatunk egy int-et, amit növelünk és csökkentünk. Feltételezve, hogy az int nem csordul túl, így megoldható a feladat – de ez nem véges automata, nem rajzolható fel egy véges állapotátmeneti gráffal vagy állapottáblával.

5. További feladatok

  • Egészítsük ki úgy a C kommentszűrőt, hogy ismerje a sztringeket is! Például "a/*b" nem komment, hiába van benne per-csillag.
  • Szintén a kommentszűrőhöz: ismerje fel az állapotgép a C++ nyelvből átvett, // stílusú kommentet is! Ezek két perjellel kezdődnek, és a sor végéig tartanak.
  • A forráskód hány százaléka komment? Egészítsük ki a programot úgy, hogy meghatározza ezt!