Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Cvičenia 11

Z Programovanie
Prejsť na: navigácia, hľadanie

Cieľom dnešného cvičenia je precvičiť si prácu s aritmetickými výrazmi a binárnymi stromami.

Stromy pre aritmetické výrazy

  • Nižšie nájdete program, ktorý obsahuje niektoré funkcie z prednášok na prácu s aritmetickými výrazmi uloženými ako strom
  • Rozšírte tento program tak, aby sa v aritmetickom výraze mohla vyskytovať aj premenná x. Tá sa spozná podľa toho, že v položke op štruktúry node je uložený znak 'x' (položka val sa v takýchto vrcholoch nepoužíva).
    • Napíšte funkciu, ktorá dostane nezáporné celé číslo n a zostaví strom, ktorý reprezentuje x^{n}, pričom použije len vrcholy pre premennú x a pre násobenie.
    • Modifikujte funkciu evaluate, aby pracovala aj pre výrazy s premennou x, pričom hodnotu tejto premennej dostane ako parameter, t.j. hlavička bude double evaluate(node *v, double x). Overte, že ak tútu funkciu spustíte pre váš strom zodpovedajúci x^{n}, dostanete správny výsledok.
    • Modifikujte aj funkciu infix, aby správne vypisovala výraz s premennou x

Binárne stromy

  • Napíšte funkciu dvojicky(node *root), ktorá spočíta počet všetkých vnútorných vrcholov v binárnom strome s koreňom root takých, že ich ľavé aj pravé dieťa majú v svojom dátovom poli uloženú tú istú hodnotu.
  • Napíšte rekurzívnu funkciu, ktorá každému uzlu binárneho stromu prirobí smerník na otca do položky parent typu node *. Funkcia bude mať hlavičku void assignParent(node *v, node *parent) kde vrchol parent je otcom vrchola v, alebo NULL ak v je koreň a teda nemá otca. Funkcia doplní otca vrcholu v aj všetkým jeho potomkom, t.j. napr. synom vrchola v nastaví ako otca smerník na v. Použite nasledujúcu štruktúru pre vrchol stromu:
struct node {
    /* vrchol stromu  */
    dataType data;
    node * left;  /* lavy podstrom */
    node * right; /* pravy podstrom */
    node * parent; /* otec vrcholu */
};

Ešte stromy

  • Máme binárny strom, v ktorom má každý vrchol buď dve deti a v dátovom poli uložený znak '#' alebo nemá žiadne deti a v dátovom poli má uložený znak '*'. Keď tento strom vypíšeme v preorder poradí, dostaneme postupnosť ##*#*** Nakreslite, ako vyzerá tento strom.
  • Napíšte funkciu, ktorá binárny strom upraví tak, že v dátovej časti vrcholov bude node * next ukazujúci na nasledujúci vrchol stromu v
    • infixovom poradí
    • prefixovom poradí

Program pre prácu so stromami pre aritmetické výrazy

#include <iostream>
#include <cassert>
using namespace std;

struct node { /* vrchol stromu  */
    double val;     /* ciselna hodnota */
    char op;        /* operator '+', '-', '*', '/', 
                     * alebo ' ' ak ide o hodnotu */
    node * left;    /* lavy podvyraz alebo NULL */
    node * right;   /* pravy podvyraz alebo NULL */
};

node * createOp(char op, node *left, node *right) {
    /* vytvori novy vrchol stromu s operatorom op
     * a do jeho laveho a praveho podvyrazu ulozi
     * smerniky left a right. */
    node *v = new node;
    v->left = left;
    v->right = right;
    v->op = op;
    return v;
}

node * createNum(double val) {
    /* Vytvori novy vrchol stromu s danou hodnotou,
     * lavy a pravy podvyraz bude prazdny, op bude medzera */
    node *v = new node;
    v->left = NULL;
    v->right = NULL;
    v->op = ' ';
    v->val = val;
    return v;
}

void infix(node *v) {
    /* funkcia na tlac vyrazu v infixovej notacii */
    if(v->op == ' ') {
        cout << ' ' << v->val;
    }
    else {
        cout << " (";
        infix(v->left);
        cout << " " << v->op;
        infix(v->right);
        cout << " )";
    }
}

double evaluate(node *v) {
    /* vyhodnoti vyraz dany stromom s korenom vo vrchole v */
    assert(v != NULL);

    /* ak je operator medzera, vratime jednoducho hodnotu */
    if (v->op == ' ') {
        return v->val;
    }

    /* rekurzivne vyhodnotime lavy a pravy podvyraz */
    double valLeft = evaluate(v->left);
    double valRight = evaluate(v->right);

    /* Hodnotu laveho a praveho podvyrazu spojime podla typu operatora
     * a vratime. Prikaz break netreba, pouzivame return. */
    switch (v->op) {
        case '+': return valLeft + valRight;
        case '-': return valLeft - valRight;
        case '*': return valLeft * valRight;
        case '/': return valLeft / valRight;
        default: assert(false);
    }
}

int main(void) {
    node * vyraz = createOp('+', createNum(2), createNum(3));

    // vypis vyrazu
    cout << "Vyraz: ";
    infix(vyraz);
    cout << endl;

    // vyhodnotenie vyrazu
    cout << "Hodnota: " << evaluate(vyraz) << endl;
}