II. rész: Függvény építése RPN kifejezésből

Az objektumorientált programozásban általában az adatainkat kezeljük objektumként. Ezekre ilyenkor önálló entitásként tekintünk, amelyek a programban bizonyos feladatot képesek elvégezni, és amelyeknek változó belső állapota is lehet. Az objektum modellezhet egy „hétköznapi” entitást, amely a program felhasználója számára is megjelenik (pl. egy rajzolóprogram alakzatai), de valamilyen elvontabb dolgot is (pl. egy verem tároló). Az objektum képes valamilyen műveletek elvégzésére (veremnél: betesz, kivesz), és a háttérben rendelkezik valamilyen belső reprezentációval is (veremnél tipikusan egy tömb vagy egy láncolt lista).

Az objektumok ezeken felül reprezentálhatnak algoritmusokat is. Ilyenek lehetnek például egy másik objektumon elvégzett műveletek (egy alakzat átméretezése, befestése, körvonala stílusának beállítása), vagy egy bizonyos feladat eltérő megvalósításai, stratégiái. Mivel ilyenkor az algoritmusokat is objektumokkal modellezzük, adatként vagyunk képesek dolgozni azokkal. Minden olyan absztrakció, amely adatokon használható, működhet algoritmusok esetén is. Építhetünk például egy kompozit műveletet az alakzatokhoz, amely egymás után több kisebb műveletet végez el rajtuk.

Így működött az osztályhierarchiás előadás szintaxisfás példája is. De ehhez hasonló volt az okos pointerek nullpointerek kezelését beállító parameterizálása is, és a nyelvi elemzés alapműveleteiből felépített rekurzív alászálló elemző is.

Hogy építünk fel ilyen függvényeket? Példaként maradjunk a négy alapműveletes matematikai kifejezésnél. Adott egy egyváltozós matematikai függvény egy sztringben, az egyszerűség kedvéért fordított lengyel jelöléssel, például "5 x + 7 *". Ez (5 + x) * 7-et jelent. A feladatunk az, hogy ezt értékeljük ki egy adott x helyen. Hogyan oldható ez meg? Hogyan építhető olyan adatszerkezet vagy függvény, amelyik a kiértékelést elvégzi? Tételezzük fel azt is, hogy a kifejezésünk fordított lengyel jelöléssel adott. Ezt egyszerűbb kezelni, és így a függvény létrehozására tudunk koncentrálni. A fordított lengyel jelöléssel adott kifejezés lineárisan feldolgozható: balról jobbra haladva a sztringben, minden elemnél kontextustól függetlenül lehet tudni, hogy mi a teendő. Minden operátor az előtte álló két operandusra vonatkozik:

Egy ilyen kifejezés kiértékeléséhez egy veremre van csak szükség. A számokat bedobjuk a verembe; ha műveletet kell végezni, azt pedig a verem tetején lévő két számmal végezzük, az eredményt a verembe visszadobva. Ha a kifejezés 5 2 7 + *, akkor

• Bedobjuk az 5-öt a verembe:

  5

• Bedobjuk a 2-t a verembe:

  5 2

• Bedobjuk a 7-et a verembe:

  5 2 7

• Kivesszük a verem tetején lévő két számot (2 és 7), összeadjuk őket, visszatesszük az eredményt:

  5 9

• Kivesszük a felül lévő számokat (5 9), szorzunk, visszatesszük:

45

• A sztring végére értünk, a veremben lévő egyetlen szám az eredmény.

Ha van változónk is, kiértékelés közben annak értékét tehetjük a verembe, mintha szám lett volna ott.

Tehát: hogyan építünk fel egy ilyen kifejezésből (sztringből) egy függvényt? Ne feledjük, az alábbi kódokban nem a kiértékelés menete a lényeg. A feladatunk az, hogy algoritmust építsünk bemenő adatok alapján: sztringet kapunk, függvényt adunk vissza. Az adatszerkezet megépítésén van a hangsúly.

A fenti kiértékelő módszert egy az egyben felhasználhatjuk. Ezek alapján a függvény, amely az egyes tokenekből (szám, művelet, változó) álló kifejezést feldolgozza, kiértékeli egy adott x helyen, a következő:

#include <string>
#include <vector>
#include <stack>
#include <iostream>

double kiertekel(std::vector<std::string> const& kifejezes, double x) {
    std::stack<double> st;
    for (auto const& token : kifejezes) {
        if (token == "+") {
            double a = st.top(); st.pop();
            double b = st.top(); st.pop();
            st.push(a + b);
        } else if (token == "*") {
            double a = st.top(); st.pop();
            double b = st.top(); st.pop();
            st.push(a * b);
        } else if (token == "x") {
            st.push(x);
        } else {
            st.push(std::stod(token));
        }
    }
    return st.top();
}

int main() {
    std::vector<std::string> kifejezes = {"5", "2", "x", "+", "*"};
    std::cout << kiertekel(kifejezes, 7) << std::endl;
}

Persze ezzel még nem az eredeti feladatot oldottuk meg, hiszen nem írtunk olyan függvényt, amelyik a tokenekből előállítja a matematikai függvényünket. Ezen egy closure segít:

std::function<double(double)> fuggvenyt_epit(std::vector<std::string> kifejezes) {
    return [kifejezes = std::move(kifejezes)] (double x) {
        return kiertekel(kifejezes, x);
    };
}

int main() {
    std::vector<std::string> kifejezes = {"5", "2", "x", "+", "*"};
    auto f = fuggvenyt_epit(kifejezes);
    std::cout << f(7) << std::endl;
    std::cout << f(8) << std::endl;
    std::cout << f(9) << std::endl;
}

Így eltároljuk a kiértékelendő kifejezést, tulajdonképp részlegesen alkalmazva a kiertekel() függvényt: a visszaadott lambdának a kifejezés már nem paramétere, hanem csak a változó az.

Ez a megoldás nem túl szerencsés, mert nem hatékony. Valójában nem épült adatszerkezet, csak eltároltuk a bemeneti adatot, a sztringek sorozatát; a kapott f() függvény minden egyes hívásakor újra és újra a sztringek feldolgozását el kell végezni. Mintha minden kiértékeléskor újra beolvasnánk a bemenetet.

Ahhoz, hogy a bemenet feldolgozását és a függvény kiértékelését el tudjuk egymástól választani, építenünk kell egy olyan adatszerkezetet, amely a már feldolgozott, de még kiértékeletlen függvényt reprezentálja. Erre jó lehet egy absztrakt szintaxisfa, ahogyan az az osztályhierarchiás előadáson szerepelt. Egy ilyen látható oldalt is.

Ebben az egyes műveleteket (konstans, változó, összeadás) objektumokkal reprezentáljuk. Ezek tulajdonképp apró algoritmusok, amelyek az x változó értékét feldolgozzák; mivel a programunkban objektumokként jelennek meg, így építkezni is tudunk belőlük. Olyan adatszerkezetet hozhatunk létre, amelyik műveleteket tartalmaz.

Az egyes műveletekhez tartozó osztályok váza az alábbi:

class Muvelet {
    virtual double kiertekel(double x) const = 0;
};

class Konstans : public Muvelet {
    virtual double kiertekel(double) const {
        return c;
    }
};

class Valtozo : public Muvelet {
    virtual double kiertekel(double x) const {
        return x;
    }
};

class Osszeg : public Muvelet {
    virtual double kiertekel(double x) const {
        return bal->kiertekel(x) + jobb->kiertekel(x);
    }
};

class Szorzat : public Muvelet {
    virtual double kiertekel(double x) const {
        return bal->kiertekel(x) * jobb->kiertekel(x);
    }
};

Az adatszerkezet megépítéséhez, vagyis a bemenet feldolgozásához itt is egy vermet kell használni. De ez a verem most nem a kiértékelés részeredményeit fogja tartalmazni, hanem azokat a részfákat, amelyekből végülis a teljes szintaxisfa felépül. Konstans és változó hatására új részfát dobunk a verembe. Művelet hatására fát építünk a verem tetején lévő két részfából:

Mire végzünk, a veremben egyetlen egy csomópont lesz, amelyik a szintaxisfa gyökere. Mindez kódban:

class Muvelet;
class Konstans : public Muvelet { /* ... */ };
/* ... */

Muvelet* fat_epit(std::vector<std::string> const& kifejezes, double x) {
    std::stack<Muvelet*> st;
    for (auto const& token : kifejezes) {
        if (token == "+") {
            Muvelet* a = st.top(); st.pop();
            Muvelet* b = st.top(); st.pop();
            st.push(new Osszeg(a, b));
        } else if (token == "*") {
            Muvelet* a = st.top(); st.pop();
            Muvelet* b = st.top(); st.pop();
            st.push(new Szorzat(a, b));
        } else if (token == "x") {
            st.push(new Valtozo());
        } else {
            st.push(new Konstans(std::stod(token)));
        }
    }
    return st.top();
}

A használatnál előbb megépíthetjük a fát, utána pedig a tartalmazott függvényt tetszőlegesen sokszor kiértékelhetjük:

int main() {
    std::vector<std::string> kifejezes = {"5", "2", "x", "+", "*"};
    Muvelet *f = fat_epit(kifejezes);
    std::cout << f->kiertekel(7) << std::endl;
    std::cout << f->kiertekel(8) << std::endl;
    std::cout << f->kiertekel(9) << std::endl;
    delete f;
}

(A heterogén kollekciónak így nem túl szép a memóriakezelése – okos pointerekkel többre mehetünk, de erről egy másik írásban lesz szó.)

A felépített szintaxisfa nagyon hasznos lehet, hiszen a reprezentált kifejezést nem csak adott x helyen kiértékelni akarhatjuk, hanem egész más műveleteket is el tudnánk végezni rajta.

Mi a helyzet viszont akkor, ha tényleg csak kiértékelni szeretnénk? A fa csomópontjai tulajdonképpen függvényeket tartalmaznak; minden művelet egy függvény. Kell ehhez osztályhierarchiát építenünk? Valójában nem, mert a nyelv beépített eszközei eleve alkalmasak arra, hogy függvényeket tároljunk és manipuláljunk. A lambda kifejezések a létrehozó könyezetük változóit látják: jelen esetben a részfákat csomagolhatnánk így be. Az std::function objektumok pedig tetszőleges függvénytípushoz nyújtanak type erasure-t, amely azt teszi lehetővé, hogy tárolóban, adatként kezeljük ezeket.

Az új verzióban így a verem std::function objektumokat fog tartalmazni.

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <functional>

std::function<double(double)> fuggvenyt_epit(std::vector<std::string> const& kifejezes) {
    std::stack<std::function<double(double)>> st;
    for (auto const& token : kifejezes) {
        if (token == "+") {
            auto a = std::move(st.top()); st.pop();
            auto b = std::move(st.top()); st.pop();
            st.push([a = std::move(a), b = std::move(b)] (double x) {
                return a(x) + b(x);
            });
        } else if (token == "*") {
            auto a = std::move(st.top()); st.pop();
            auto b = std::move(st.top()); st.pop();
            st.push([a = std::move(a), b = std::move(b)] (double x) {
                return a(x) * b(x);
            });
        } else if (token == "x") {
            st.push([] (double x) {
                return x;
            });
        } else {
            double c = std::stod(token);
            st.push([c] (double) {
                return c;
            });
        }
    }
    return std::move(st.top());
}

int main() {
    std::vector<std::string> kifejezes = {"5", "2", "x", "+", "*"};
    auto f = fuggvenyt_epit(kifejezes);
    
    std::cout << f(7) << std::endl;
    std::cout << f(8) << std::endl;
    std::cout << f(9) << std::endl;
}

(Melyik move-ot miért volt érdemes betenni? Ezt mindenki átgondolhatja magának.)