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

Add meg az alábbi kifejezésekhez tartozó kifejezésfát, figyelembe véve az operátorok precedenciáját!

• 6+2*3
• 2*6-5/3
• a=b+c
• t[i+2]*3
• 5*-6
• 5-*6

Az alábbi rajzok közül az egyik az x=(double)a/b kifejezésfáját ábrázolja. Melyik az? Add meg a másik fa által ábrázolt kifejezést!

A feladat megoldására 10 perc áll rendelkezésre.

Az x=(double)a/b kifejezést az első kifejezésfa ábrázolja. A másik kifejezés pedig: x=(double)(a/b). Zárójelbe kell tenni az a/b-t, hogy a típuskonverzió az osztás eredményére vonatkozzon. Zárójel nélkül az a változó értékére vonatkozik, mivel erősebb a konverziós operátor precedenciája, mint az osztás operátoré.

Pontozás: összesen nyolc kérdés volt: 6 kifejezésfa rajzolása, és a megrajzolt fákra vonatkozó két kérdés. Minden teljesen helyes válasz 1 pont.

1. A szabványos bemeneten érkező szöveget kisbetűsítve a szabványos kimenetére írja.
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. Két lehetőség lenne: cím szerint átvett változót módosít, vagy visszatérési értékben adja az eredményt. Cím szerinti paraméter esetén &c lenne a paraméter. Amikor kitalálták, úgy döntöttek, legyen inkább visszatérési érték, mert kényelmesebb úgy használni.
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.

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.

#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;
}

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.

#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;
}

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.