Matematikai kifejezések tárolása fában

Az előadáson szerepelt egy ötlet, amelyben bináris fában tároltunk műveleteket: összegeket, szorzatokat.

A bináris fás tárolás előnye az, hogy a fában tárolt hierarchia, vagyis a fa felépítése meghatározza a műveletek sorrendjét. Ezért nincsen szükség se precedenciát leíró szabályokra, se zárójelezésre. Példa erre a 4*(5+7) kifejezés, amelyet a rajzon látható fa ábrázol. Ennek szövegként leírásához szükségünk van a zárójelezésre is, hiszen az alacsony precedenciájú összeg kifejezés (5+7) eredményét szorozzuk össze egy számmal – a fában tárolt műveletnél a kétértelműség nem merül fel.

Bár egy szövegesen adott műveletből a fa felépítése nem triviális feladat, a fában tárolt művelet kiírása és elvégzése igen egyszerű. Csak be kell járni a fát, és közben elvégezni a megfelelő feladatot, kiírást vagy számolást. Ezeket az ötleteket dolgozza ki ez az írás.

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

Ha megvizsgáljuk az előbbi rajzon látható fát, akkor háromféle csomópontot találunk rajta: összeg, szorzat és konstans csomópontot. Az összeg és szorzat csomópontoknak vannak gyerekeik: olyan részfák, amelyek ugyancsak műveleteket tárolnak. Ezek határozzák meg azokat a számokat, amelyeken a műveletet el kell végezni. A konstans típusú csomópontoknak nincsenek már gyerekeik, vagyis azok a fa levelei.

Ezek szerint egy csomópontban egy számot vagy két pointert kell eltárolni. Bár sokáig lehetne szépítgetni, maradjunk most annál a megoldásnál, amelyben mindkét adatot egy struktúrába tesszük, a típust mutató enum-mal együtt. Hogy izgalmasabb legyen a program, vegyünk fel egy új típust is, a változót: így a fában tárolt kifejezés egy függvénnyé válhat, amelyet egy adott x helyen tudunk kiértékelni.

typedef enum {
   Konstans,
   Osszeg,
   Szorzat,
   Valtozo
} KifejezesTipus;

typedef struct Kifejezes {
   KifejezesTipus tipus;
   double szam;                   /* csak konstanshoz */
   struct Kifejezes *bal, *jobb;  /* csak muvelethez */
} Kifejezes;

A fa létrehozását nagyban megkönnyítjük, ha minden csomóponttípus létrehozásához írunk egy függvényt, amely a keletkező csomópont tartalmát paraméterként veszi át. Ilyen függvény a Konstans típusra:

Kifejezes *uj_konstans(double szam) {
    Kifejezes *uj = (Kifejezes *) malloc(sizeof(Kifejezes));
    uj->tipus = Konstans;
    uj->szam = szam;
    return uj;
}

Az összegre:

Kifejezes *uj_osszeg(Kifejezes *bal, Kifejezes *jobb) {
    Kifejezes *uj = (Kifejezes *) malloc(sizeof(Kifejezes));
    uj->tipus = Osszeg;
    uj->bal = bal;
    uj->jobb = jobb;
    return uj;
}

Egy fát így C kódban könnyen, olvashatóan fel tudunk építeni. Például a 2*3*x*x+3*x kifejezés:

/* 2*3*x*x + 3*x */
fa = uj_osszeg(
        uj_szorzat(
            uj_szorzat(uj_konstans(2), uj_konstans(3)),
            uj_szorzat(uj_valtozo(), uj_valtozo())),
        uj_szorzat(
            uj_konstans(3),
            uj_valtozo()));

A fában tárolt műveletsor kiértékeléséhez be kell járnunk a fát. Egy konstans önmagára értékelődik ki, a változó pedig a paraméterként kapott értékre. Összeg és szorzat esetén ki kell értékelnünk a bal és jobb oldali részfában tárolt kifejezéseket, és az így kapott eredményeken elvégezni az összeadást és a szorzást:

double szamol(Kifejezes *gy, double x) {
   switch (gy->tipus) {
      case Konstans:
          return gy->szam;
      case Valtozo:
          return x;
      case Osszeg:
          return szamol(gy->bal, x)+szamol(gy->jobb, x);
      case Szorzat:
          return szamol(gy->bal, x)*szamol(gy->jobb, x);
   }

   /* ide nem lenne szabad eljutni */
   abort();
}

A fenti switch szerkezet felsorolja az összes lehetséges típust, vagyis a négy return közül valamelyik hatására a függvényből vissza kell térnünk. Azonban előfordulhat, hogy nincs így – például ha egy inicializálatlan, memóriaszemetet tartalmazó Kifejezes struktúrára hívtuk meg a függvényt. Ez viszont azt jelenti, hogy a programunk hibásan van megírva. Ilyenkor a legjobb, amit tehetünk, hogy megszakítjuk a program futását, lehetővé téve a hiba megkeresését. Ezt teszi az abort() függvény.

A fa törlésekor figyelembe kell vennünk azt, hogy mely csomópontok levelek. Változó és szám típusú csomópont esetén ugyanis nincsenek részfák. Ez az a feltétel, ami megállítja a rekurziót:

void torol(Kifejezes *gy) {
    switch (gy->tipus) {
        case Valtozo:
        case Konstans:
            break;
        case Szorzat:
        case Osszeg:
            torol(gy->bal);
            torol(gy->jobb);
            break;
    }
    free(gy);
}

A művelet kiírása már bonyolultabb. Elvileg ugyanúgy, rekurzívan kell csinálni, mint a többi fabejárást:

• Konstans esetén kiírjuk a számot,
• Változó esetén kiírunk egy x-et,
• Összeg és szorzat esetén kiírjuk a bal oldali részfát, utána egy +-t vagy egy *-ot, végül a jobb oldali részfát.

Így azonban rossz eredményt kaphatunk. A jobb oldalt látható fa esetén például a képernyőn 4*5+x jelenne meg, ami hibás, mivel nem a 4-et kell az 5-tel szorozni, hanem az összeget.

A naív megoldás a problémára az, hogy az összegeket bezárójelezzük. Tehát egy összeg esetén a kiírandó dolgok: (, bal részfa, +, jobb részfa, ). Ez sem teljesen jó, mivel ilyenkor ((1+2)+3)-at és ehhez hasonló kimeneteket fogunk kapni.

Ennél okosabban kell figyelembe vennünk a precedenciaszabályokat. Tudjuk, hogy akkor kell zárójelezni, ha egymás mellett szerepel egy szorzat és egy összeg – vagyis ha egy szorzat valamelyik tagja egy összeg. Mert ebben az esetben „enné meg” a szorzásjel a mellette álló összeg valamelyik tagját a magasabb precedencia miatt. Ezért az összegeket minden gondolkodás (és zárójel) nélkül kiírhatjuk, a szorzásnak azonban figyelnie kell arra, hogy milyen a részfáinak típusa. Ha azt látja, hogy a bal vagy a jobb oldali részfája egy összeg, akkor zárójelezve kell kiírnia azt:

void kiir(Kifejezes *gy) {
   switch (gy->tipus) {
      …
      …
      case Szorzat:     /* ha a gyerek osszeg, be kell zarojelezni (a gyereket) */
         if (gy->bal->tipus==Osszeg) {
            printf("("); kiir(gy->bal); printf(")");
         }
         else
            kiir(gy->bal);
         printf("*");
         if (gy->jobb->tipus==Osszeg) {
            printf("("); kiir(gy->jobb); printf(")");
         }
         else
            kiir(gy->jobb);
         break;
      …
   }
}

És így már jó. Ha még többféle operátorunk és precedenciánk lenne, meg tudnánk ezt fogalmazni általánosságban is: az erős operátor részfáit, ha azok gyengébb operátorok, zárójelezni kell. A hatványozás így bezárójelezné a szorzatot, a szorzat pedig bezárójelezi az összeget.