C++11 öröklés

Az eheti feladatok örökléssel kapcsolatosak. Igyekezz használni a C++11 újdonságait, ahol lehet: final, override, nullptr, új inicializáló szintaxis!

A laborhoz

A laborhoz ki van írva egy beadandó az admin portálon. Ide óra végén töltsd fel a forráskódokat (*.cpp, *.h)! A feladatokat ezért külön projektben oldd majd meg, ne írd felül a megoldásokat.

Labor otthoni munkában

A labor teljesítéséhez mind a három feladatot meg kell oldani.

     2  3  4  5
  6  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20
 21 22 23 24 25

Eratoszthenész szitája prímszámokat keres. (Ismerős lehet általános iskolából és Prog1-ből is.) A módszer a következő. Felírjuk a számokat valameddig. 2 prímszám, ezt megjegyezzük. Kihúzzuk a többszöröseit, mivel azok nem prímszámok. Ezután 3 a következő, ami még nincs kihúzva. Az is prímszám, mivel nem találtunk ezidáig osztót hozzá. A többszörösei viszont nem prímek: kihúzzuk az összes 3-mal oszthatót. 4-et már kihúztuk (2×2). 5 a következő prím, kihúzzuk n×5-öt stb.

Ezt most nem tömbökkel, hanem egy gépsorral kell megvalósítanod. A gépsor minden eleme fel tud dolgozni egy számot: process(int). A sor elemei lehetnek sziták (Sieve) vagy a sor végén lévő vödör (Bucket). A sziták feldolgozáskor a számot elnyelik (ha osztható azzal a számmal, aminek a szűrésére létre lettek hozva), vagy továbbküldik. A sor végén lévő vödör kiírja a kapott számot (ha keresztüljutott a szitákon, prímszám kell legyen), és beszúr maga elé egy olyan szitát, amely legközelebb már kiszűri a többszöröseit.

A gépsorral egyesével, növekvő sorrendben kell megetetni a számokat. A rajz a 3-as szám feldolgozása utáni állapotot mutatja. Ha a gépsorral megetetjük a 4-et, a 2-es szita elnyeli. Ha megetetjük vele az 5-öt, akkor az eljut a vödörhöz; a vödör kiírja, és beszúr maga elé egy 5-ös szitát. A Dummy elem egy strázsa a duplán láncolt lista elején, a pointerműveletek egyszerűsítéséhez. Csak továbbítja a számot, egyéb dolga nincs. Kezdetben csak a Dummy létezik, és a vödör; az összes szita később jön létre.

Valósítsd meg a programot, az alábbi lépésekkel sorban haladva!

1. Definiáld az ősosztályt (Element), amelynek tisztán virtuális függvénye a fent említett void process(int). Ugyanez az osztály egyben a láncolt lista pointereit is adja; add hozzá ehhez csak az adattagokat (prev és next). Legyenek ezek publikusak.
2. Készítsd el ennek a leszármazottait, amelyekben megvalósítod a process() függvényeket. A Dummy csak továbbküldi a számot a következő elemnek. A Sieve vagy továbbküldi, vagy nem, attól függően, hogy a benne tárolt szám osztója-e a feldolgozandó számnak. Végül pedig, a Bucket kiírja a kapott számot, mert ami átment a láncon, az prímszám.
3. Ezek után megépítheted a főprogramban a kezdeti gépsort, amelyben csak a Dummy és a Bucket vannak. Láncold ezeket össze oda-vissza. Ez könnyen kell menjen, mert a lista pointerek publikusak.
4. Ezen a ponton a Dummy-nak adott összes szám ki kell íródjon a képernyőre, mert az továbbadja őket az őt követő Bucket elemnek, amely pedig kiírja őket.
5. Miután ezt letesztelted, ki tudod már egészíteni a Bucket process() függvényét olyan módon, hogy befűzzön maga elé egy Sieve elemet, amely szűrni fog.
6. Ha ez is működik, kész vagy, már csak be kell dobálni a lista elején a számokat, a végén pedig kipotyognak a prímek.

#include <iostream>


class Element {
  public:
    Element *prev = nullptr, *next = nullptr; // C++11

    virtual ~Element() {
        delete next;
    }
    virtual void process(int i) = 0;
};


class Dummy final: public Element { // C++11
  public:
    /* továbbküldi */
    virtual void process(int i) override { // C++11
        next->process(i);
    }
};


class Sieve final: public Element {
  private:
    int divisor_;
  public:
    Sieve(int divisor) : divisor_{divisor} {} // C++11
    /* ha nem osztható, továbbküldi */
    virtual void process(int i) override {
        if (i % divisor_ != 0)
            next->process(i);
    }
};


class Bucket final: public Element {
  public:
    /* ha eljutott idáig, kiírja, és beszúrja maga elé az új szitát */
    virtual void process(int i) override {
        std::cout << i << std::endl;
        Element *newsieve = new Sieve{i}; // C++11
        newsieve->prev = this->prev;
        newsieve->next = this;
        this->prev->next = newsieve;
        this->prev = newsieve;
    }
};


int main() {
    Element *dummy = new Dummy;
    Element *bucket = new Bucket;
    dummy->next = bucket;
    bucket->prev = dummy;
    
    /* sorban mennek bele a számok */
    for (int i = 2; i < 100; ++i)
        dummy->process(i);
    
    delete dummy;    /* a destruktora intézi a többit */
}

RPN = reverse polish notation, inverz lengyel jelölésmód. Ez azt jelenti, hogy a matematikai operátorokat és operandusaikat nem a szokásos módon, középen a műveleti jellel írjuk: 2+3, hanem a műveleti jelet a két operandus után téve: 2 3 +. Ennek nagy előnye, hogy precedenciaszabályok és zárójelezés nélkül képes pontosan meghatározni a műveleti sorrendet, mert mindig lehet tudni, hogy az operátor előtt álló két szám (vagy épp két művelet eredménye) az adott operátor operandusa. Pl.

Ha egy így megadott műveletsort kapunk, azt nagyon könnyű feldolgozni, csak egy verem kell hozzá. Olvasni kell egyesével a szavakat. Ha számot kapunk, akkor azt be kell tenni a verembe. Ha műveletet, akkor pedig ki kell venni a két legfelső számot a veremből, elvégezni rajtuk a műveletet, és visszatenni az eredményt. A műveletsor végére pontosan egy szám kell a veremben maradjon, az pedig nem más, mint a végeredmény.

Feladatok

• Próbáld ezt ki, végezd el így papíron a két fenti műveletet!
• Írj programot, amely így működik! Ehhez használd fel az std::string, az std::stack osztályokat, és az std::stod (C++11) függvényt! A programnak elég az összeadást és a szorzást tudnia. Puska:

  std::string word;
  std::cin >> word;               /* egy szót olvas, szóköznél megáll */
  while (std::cin >> word) {      /* szavak fájl vége jelig */
      // ...
  }
  stack.push(std::stod(word));    /* számmá alakít és betesz */
  std::cout << stack.top();       /* legfelső */
  stack.pop();                    /* kivesz */

Előfordulhat, hogy a C++11-es std::stod nincs még benne a fejlesztőkörnyezeted szabványos könyvtárában. Ha nem találja, akkor használj helyette mást: strtod(), sscanf(), istringstream.

#include <stack>
#include <sstream>
#include <iostream>


int main() {
    std::stack<double> rpn;
    std::string word;
    /* fájl végéig olvassuk a szavakat */
    while (std::cin >> word) {
        if (word == "+") {
            /* ha +, a verem tetejére megy a legfölső két szám helyett az összegük */
            double a = rpn.top();
            rpn.pop();
            double b = rpn.top();
            rpn.pop();
            rpn.push(a + b);
        }
        else if (word == "*") {
            /* ha *, akkor ugyanaz a szorzatukra */
            double a = rpn.top();
            rpn.pop();
            double b = rpn.top();
            rpn.pop();
            rpn.push(a * b);
        }
        else {
            /* amúgy egy szám, ami megy a verembe */
            rpn.push(std::stod(word));
        }
    }
    /* az eredmény a veremben lévő szám (elvileg 1 kell legyen) */
    double res = rpn.top();
    std::cout << "Eredmény: " << res;
}

Innen letölthető az előadás kifejezéses programja: expression.cpp. Ezeket az osztályokat így kell használni:

Expression *c = new Product{
                    new Constant{5},
                    new Sum{
                        new Constant{3},
                        new Variable
                    }
                };
std::cout << "f(x) = " << *c << std::endl;
std::cout << "f(3) = " << c->evaluate(3) << std::endl;

Expression *cd = c->derivative();
std::cout << "f'(x) = " << *cd << std::endl;

delete c;
delete cd;

Dolgozd össze a két programot! Alakítsd át úgy az inverz lengyel logikás számológépedet, hogy az azonnali műveletvégzés helyett építsen fel egy kifejezést!

• Ehhez egy kifejezésekből álló vermet kell használnod (heterogén kollekció) a számokból álló verem helyett. A beolvasás ugyanúgy történik: ha számot lát, new Constant-ot dob a verembe, ha változót, new Variable-t, ha összeadást, akkor a két felső elemet kiveszi, és visszarak egy new Sum-ot, amibe beletette azokat; és így tovább.
• A beolvasás végén egyetlen kifejezésnek kell lennie a veremben.
• Írd ki a kifejezést! Ezzel most megírtad az inverz lengyel logikáról a szokásos jelölésre alakító programot.
• Deriváld a kifejezést, és írd ki a derivált egyszerűsített változatát is! A programod most tetszőleges, lengyel logikával megadott kifejezéseket tud deriválni.

Tipp

A verem itt kifejezésfák heterogén kollekciója lesz. A 2 x + 8 x + * kifejezésben, a második összeadás beolvasása után, de még a szorzás beolvasása előtt, az adatszerkezet így fest:

#include <stack>
#include <sstream>

int main() {
    std::stack<Expression*> rpn;
    std::string word;
    while (std::cin >> word) {
        if (word == "+") {
            Expression *e1 = rpn.top();
            rpn.pop();
            Expression *e2 = rpn.top();
            rpn.pop();
            rpn.push(new Sum{e2, e1});
        }
        else if (word == "*") {
            Expression *e1 = rpn.top();
            rpn.pop();
            Expression *e2 = rpn.top();
            rpn.pop();
            rpn.push(new Product{e2, e1});
        }
        else if (word == "x") {
            rpn.push(new Variable{});
        }
        else {
            rpn.push(new Constant{std::stod(word)});
        }
    }
    Expression *e = rpn.top();
    rpn.pop();
    
    std::cout << "f(x)=" << *e << std::endl;
    
    Expression *d = e->derivative();
    std::cout << "f'(x)=" << *d << std::endl;
    Expression *ds = d->simplify();
    std::cout << "f'(x)=" << *ds << std::endl;
    
    delete e;
    delete d;
    delete ds;
}

Lásd a feladatgyűjteményt.