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.


Prednáška 19

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

Organizačné poznámky

  • DÚ10 (predposlednú) odovzdávajte do pondelka 5.12. 22:00.
  • Vo štvrtok 1.12. večer bude Beánia http://beania.matfyz.sk/
  • Strážte si konflikty s termínmi skúšok: písomka piatok 16.12.2016 o 11:30, riadne termíny skúšok utorok 20.12. doobeda a štvrtok 12.1. poobede, prvý opravný piatok 27.1. doobeda
    • V prípade konfliktov nám dajte čím skôr vedieť!
  • Bioinformatici krátke stretnutie dnes po prednáške

Aritmetické výrazy

Infixový zápis (infixová forma alebo notácia) aritmetického výrazu

  • bežný zápis používaný v matematike
  • každý binárny operátor medzi dvoma operandami, s ktorými sa bude vykonávať príslušná operácia
  • poradie, v akom sa jednotlivé operácie vykonávajú, sa riadi umiestnením zátvoriek a prioritou operácií

Napríklad: (65 – 3*5)/(2 + 3)

Vyhodnocovanie výrazov v infixovej notácii sme videli na prednáške 9.

  • Pre jednoduchosť: úplne uzátvorkovaný výraz, znamienka + a -, čísla, bez medzier, napr. (((12-5)+7)-(6+8))

Pripomeňme si kostru programu:

int vyhodnotVyraz(char str[]){
    if (str[0] != '(') return vyhodnotCislo(str);
    else {
        char s[100];
        int poz, hodnota1, hodnota2;

        poz = najdiZnamienko(str);

        strCopy(str, s, 1, poz-1);      // kopíruj od 1 po pozíciu pred znamienkom (pozícia 0 je '(' )
        hodnota1 = vyhodnotVyraz(s);
        strCopy(str, s, poz+1, strlen(str)-2); // od pozície po znamienku po predposledný znak stringu (posledný znak - strlen()-1 je ')' )
        hodnota2 = vyhodnotVyraz(s);

        switch (str[poz]){
            case '+': return hodnota1+hodnota2;
            case '-': return hodnota1-hodnota2;
        }

        return 0;
    }    
}


int najdiZnamienko(char str[]){
    /*Vieme, ze vyraz je tvaru (Vyraz1 Z Vyraz2)*/
    int poc=0;
    for (int i=1; i<strlen(str)-1; i++){
        if (str[i]=='(') poc++;
        else if (str[i]==')') poc--;
        else if (((str[i]=='+')||(str[i]=='-'))&&(poc==0)) return i;
    }
    return -1;
}

V prípade, že by sme chceli výraz vyhodnocovať bez úplného uzátvorkovania, zmenila by sa hlavne funkcia, ktorá hľadá operand, ktorý potrebujeme vykonať.

Postfixová a prefixová notácia

Okrem infixovej notácie se môžeme stretnúť s ďalšími formami zápisu aritmetických výrazov.

Postfixová notácia (obrátená poľská notácia) má v zápise výrazu operátor až po oboch operandoch.

Výraz (65 – 3*5)/(2 + 3) by teda v postfixovej forme mal notáciu 65 3 5 * - 2 3 + /

V prefixovej notácii je situácia opačná ako pri postfixovej notácii. Každý operátor stojí pred dvoma operandami, ku ktorým prislúcha.

Výraz (65 – 3*5)/(2 + 3) by v prefixovej forme bol / - 65 * 3 5 + 2 3

Postfixová a prefixová notácia sú na prvý pohľad pre človeka neprehľadné, ale ako uvidíme, dajú sa oveľa jednoduchšie vyhodnocovať. Okrem toho vidíme ešte jednu výhodu - nepotrebujú zátvorky.

Vyhodnocovanie postfixovej formy

Na vyhodnocovanie výrazov v postfixovej forme budeme používať zásobník.

  • Budeme do neho vkladať operandy, teda hodnoty podvýrazov.
  • Využijeme vlastnosť, že operátor má oba operandy pred sebou. Teda keď narazíme na operátor, jeho operandy už máme niekde prečítané.
  • Navyše sú to posledné dve prečítané alebo vypočítané hodnoty.

Pri vyhodnocovaní výrazu prechádzame výraz zľava doprava

  • Keď narazíme na operand, uložíme ho do zásobníku.
  • Keď narazíme na operátor, tak vyberieme dva operandy zo zásobníku.
    • Ale pozor! Keďže máme zásobník (LIFO), musíme prehodiť poradie operandov oproti tomu, ako sme ich vybrali zo zásobníku
    • Napríklad delenie a/b je v postfixovej notácii a b /, teda zo zásobníku najskôr vyberieme deliteľa b a ako druhého vyberieme delenca a, a preto pri vykonávaní operácie musíme prehodiť ich poradie.
  • Vykonáme operáciu s vybranými operandami a výsledok tejto operácie umiestnime späť do zásobníku.

Tento postup opakujeme, kým nedojdeme na koniec výrazu. V tom okamžiku by sme mali mať na zásobníku jeden prvok a to je výsledok výrazu.

int main(void) {
    stack s;  // vytvor prazdny zasobnik
    init(s);
    char postfix[maxN];  // nacitaj vyraz do retazca
    fgets(postfix, maxN, stdin);

    int i = 0;
    while (postfix[i] != '\0') {
        if (isspace(postfix[i])) { // preskakuj biele znaky
            i++;
        } else if (isdigit(postfix[i]) || postfix[i]=='.') { // spracuj jedno cislo zo vstupu
            push(s, evaluateNumber(postfix, i));
        } else { // binarny operator
            double elem1 = pop(s);
            double elem2 = pop(s);
            switch (postfix[i]) {
                case '+': push(s, elem2 + elem1);
                    break;
                case '-': push(s, elem2 - elem1);
                    break;
                case '*': push(s, elem2 * elem1);
                    break;
                case '/': push(s, elem2 / elem1);
                    break;
            }
            i++;
        }
    }
    printf("%f\n", pop(s));  // na zasobniku mame vysledok
    assert(isEmpty(s));      // teraz uz je zasobnik prazdny 
}

Funkcia evaluateNumber môže vyzerať napríklad takto:

double evaluateNumber(char str[], int &i) {
    /* Z retazca od pozicie i precitaj cislo az po prvy
     * iny znak (medzera, koniec retazca, operator).
     * Cislo i sa nastavi na prvu poziciu, ktora sa neda precitat. */
    double val = 0;
    while (isdigit(str[i])) {
        val = val * 10 + (str[i] - '0');
        i++;
    }
    /* desatinna cast */
    if (str[i] == '.') {
        i++;
        double power = 0.1;
        while (isdigit(str[i])) {
            val += (str[i] - '0') * power;
            power /= 10;
            i++;
        }
    }
    return val;
}

Konverzia infixovej formy na postfixovú

Vidíme, že vyhodnocovanie postfixového výrazu je jednoduché. Väčšinou však pracujeme s infixovou formou zápisu a preto ju potrebujeme nejakým spôsobom prepísať do postfixovej.

Pre jednoduchosť si najskôr ukážeme iba výrazy bez zátvoriek, pričom * a / majú vyššiu prioritu ako + a -. Použijeme zásobník, do ktorého si budeme ukladať zatiaľ nevypísané časti infixovej formuly (teda operátory, ktoré ešte nemajú oba operandy).

Pri vyhodnocovaní prechádzame výrazom zľava doprava:

  • Ak objavíme operand, prepíšeme ho do postfixového reťazca a ďalej nás už nezaujíma.
  • Ak narazíme na operátor, pozrieme sa na vrch zásobníka:
    • Kým operátor zo zásobníka má väčšiu alebo rovnakú prioritu, tak vyberáme zo zásobníka (a vybrané operátory prepíšeme do postfixového reťazca). Vypisujeme až dokiaľ nenarazíme na operátor s nižšou prioritou (alebo dno).
  • Po tomto kroku umiestnime aktuálny operátor do zásobníka.
  • Tento postup opakujeme pokiaľ nenarazíme na koniec výrazu.
    • Potom vyberieme operátory zo zásobníka a umiestnime ich na výstup.
  • Odsimulujme na výraze 8 + 3 * 4 * 2 - 5 + 2 * 3

Pridanie zátvoriek:

  • Ľavú zátvorku iba vložíme do zásobníka
  • Keď narazíme na pravú zátvorku, znamená to, že všetky operátory, ktoré boli v zátvorke, by mali byť už vypísané na výstup. Preto ich vypisujeme, až kým nenarazíme na ľavú zátvorku.
int precedence(char op) {
    if (op == '#' || op == '(') return 0; // specialne pripady, ktore bezne nevyhadzujeme
    if (op == '-' || op == '+') return 1;
    if (op == '*' || op == '/') return 2;
    assert(false); // sem by sme sa nemali dostat    
}

int main(void) {
    char infix[maxN], postfix[maxN];
    fgets(infix, 100, stdin); // nacita aritmeticky vyraz v infixovej forme

    stack s; // vytvor prazdny zasobnik
    init(s);
    push(s, '#'); // specialne dno zasobnika

    int j = 0; /* index do vystupneho retazca */
    for (int i = 0; infix[i] != 0; i++) {
        if (isdigit(infix[i]) || infix[i]=='.') { /* cisla skopirujeme na vystup */
            postfix[j++] = infix[i];
        }
        else if (isspace(infix[i])) { /* biele znaky preskakujeme */
        } else if (infix[i] == '(') { /* zaciatok zatvorky dame na zasobnik */
            push(s, infix[i]);
        } else if (infix[i] == ')') {
            /* koniec zatvorky znamena, ze vypiseme vsetky operatory, 
             * co boli v tej zatvorke (a este nie su vypisane)*/
            char popped = pop(s);
            postfix[j++] = ' ';
            while (popped != '(') {
                postfix[j++] = popped;
                postfix[j++] = ' ';
                popped = pop(s);
            }
        }
        else { /* spracovanie operatora */
            postfix[j++] = ' '; // pridame medzeru
            int p = precedence(infix[i]); // dolezitost prichadzajuceho operatora
            while (precedence(peek(s)) >= p) {
                postfix[j++] = pop(s);
                postfix[j++] = ' ';
            }
            push(s, infix[i]);
        }
    }

    /* vsetko, co na zasobniku ostalo, vypiseme */
    char popped = pop(s);
    postfix[j++] = ' ';
    while (popped != '#') {
        postfix[j++] = popped;
        postfix[j++] = ' ';
        popped = pop(s);
    }

    postfix[j] = '\0';
    printf("Postfix: %s\n", postfix);
}
  • Program na niekoľkých miestach pridáva medzery (občas zbytočné), aby sa nám operandy nezliali do jedného čísla a vedeli sme ich následne vyhodnocovať.
  • Nefunguje pre unárne mínus (napr. 2*-3), ktoré treba detegovať a kopírovať na výstup spolu s číslom (a správne spracovávať aj v postfixovej notácii)

Cvičenia:

  • Ako by ste rozšírili o operáciu umocnenia ^ s ešte vyššou prioritou ako *?
  • Niektoré časti programu (cykly while) sa trochu opakujú, ako by sa to dalo vyriešiť pomocnou funkciou?
  • Ako by sme program upravili, aby nikde nedal dve medzery za sebou?

Zhrnutie

Aritmetické výrazy

  • Bežná infixová notácia, napr. (65 – 3*5)/(2 + 3)
  • Úplne uzátvorkovaná, napr. ((65 – (3*5))/(2 + 3))
  • Postfixová notácia 65 3 5 * - 2 3 + /
  • Prefixová notácia / - 65 * 3 5 + 2 3
  • Prefixová a postfixová notácia nepotrebujú zátvorky
  • Prevod z infixovej notácie na postfixovú pomocou zásobníka
    • Čo si ukladáme do zásobníka?
  • Vyhodnocovanie postfixovej notácie pomocou zásobníka
    • Čo si ukladáme do zásobníka?

Aritmetický výraz ako strom

Ďalšia téma:

  • uloženie aritmetického výrazu vo forme stromu a práca so stromami všeobecne

Zajtra a budúci týždeň:

  • ďalšie príklady stromov v informatike
Strom pre výraz (65 – 3*5)/(2 + 3)

Reprezentácia aritmetického výrazu vo forme stromu

  • Každý operátor a každé číslo tvorí vrchol stromu
  • Vrchol pre operátor má pod sebou zavesené menšie stromy pre podvýrazy, ktoré spája
  • Informatici stromy väčšinou kreslia hore nohami, s koreňom na vrchu
    • V našom príklade je koreň vrchol s operátorom /

Dátová štruktúra pre vrcholy stromu

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

Ak máme vrchol pre operátor:

  • left a right sú smerníky na ľavý a pravý podvýraz
  • znak op je znamienko operátora, napr. '+'
  • hodnota val je nevyužitá

Ak máme vrchol pre číslo vo výraze:

  • left a right majú hodnotu NULL (žiadne podvýrazy)
  • znak op má hodnotu medzera ' '
  • val obsahuje hodnotu čísla

Jednoduchá ale nie veľmi elegantná reprezentácia

  • niektoré položky sú nevyužité (val v operátoroch, left a right pri číslach)
  • budúci semester uvidíme krajšie riešenie pomocou objektov

Vytváranie vrcholov stromu

Nasledujúce dve funkcie vytvoria nový vrchol.

  • Pre vrchol typu operátor už funkcia dostane smerníky na vrcholy pre podvýrazy
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;
}

Vytvorme teraz ručne strom pre náš výraz (65 – 3*5)/(2 + 3):

node *v = createOp('/',
            createOp('-', createNum(65),
                          createOp('*', createNum(3), createNum(5))),
            createOp('+', createNum(2), createNum(3)));

Alebo to môžeme rozpísať po krokoch:

node *v65 = createNum(65);
node *v3 = createNum(3);
node *v5 = createNum(5);
node *v2 = createNum(2);
node *v3b = createNum(3);
node *vKrat = createOp('*', v3, v5);
node *vMinus = createOp('-', v65, vKrat);
node *vPlus = createOp('+', v2, v3b);
node *vDeleno = createOp('/', vMinus, vPlus);

Vyhodnocovanie výrazu

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

Zhrnutie

  • Aritmetický výraz vieme reprezentovať aj ako strom.
  • Rekurzívnou funkciou môžeme potom ľahko spočítať jeho hodnotu.
  • Nabudúce si ukážeme, ako prerobiť postfixovú formu na strom (a tým pádom vieme prerobiť aj infixovú, lebo tú vieme prerobiť na postfixovú).
  • Ukážeme si tiež, ako výraz reprezentovaný stromom vypísať vo všetkých troch formách.

Terminológia stromov

  • Stromvrcholy/uzly (nodes, vertices) a tie sú pospájané hranami (edges)
  • Nás zaujímajú zakorenené stromy, ktoré majú jeden vrchol zvolený ako koreň (root)
  • Každý iný vrchol okrem koreňa je spojený hranou s jedným rodičom/otcom (parent) a s niekoľkými (nula alebo viac) deťmi/synmi (children)
  • Listy sú vrcholy, ktoré nemajú deti, ostatné vrcholy voláme vnútorné
  • V binárnom strome má každý vrchol najviac dve deti
  • Predkovia vrchola sú všetky vrcholy na ceste od neho smerom ku koreňu, teda on sám, jeho otec, otec jeho otca atď, až kým nenarazíme na koreň
  • Ak x predkom y, tak y je potomkom x
  • Podstrom s koreňom vo vrchole x tvorí vrchol x a všetci jeho potomkovia
  • Strom je teda buď prázdny, alebo je tvorený koreňom a dvoma podstromami: ľavým a pravým.

Náš aritmetický strom

  • Je binárny
  • V listoch sú čísla, vo vnútorných vrcholoch operácie
  • Každý vnútorný vrchol má dve deti

Jednoduchá práca so stromami

Uvoľňovanie stromu

Na precvičenie práce so stromami si ešte napíšme funkciu, ktorá dostane koreň stromu a uvoľní všetku pamäť, ktorú jednotlivé vrcholy stromu zaberali.

  • Opäť použijeme rekurziu, pričom najprv uvoľníme všetku pamäť pre ľavý podstrom, potom pre pravý a nakoniec samotný koreň.
  • Ako triviálny nerekurzívny prípad použijeme prázdny strom, ktorý ma smerník na koreň NULL.
void destroyTree(node* v){
  if(v!=NULL){
    destroyTree(v->left);
    destroyTree(v->right);
    delete v;
  }
}

Výška (hĺbka) stromu

  • Hĺbka vrcholu v strome je jeho vzdialenosť od koreňa. T.j. koreň má hĺbku 0, jeho synovia hĺbku 1 atď.
  • Výška stromu (niekedy nazývaná hĺbka stromu) je maximum z hĺbok jeho vrcholov
    • Ak máme strom s jedným vrcholom, výška je 0
    • Inak spočítame výšku ľavého a pravého podstromu
    • Ku každej pripočítame 1, lebo pridávame hranu k otcovi
    • Aby to fungovalo aj pre prázdne podstromy, dodefinujeme výšku prázdneho podstromu na -1
 int height(node *v) {
    /* Vrat vysku stromu s korenom v.
     * Ak v je NULL, vrati -1. */
    if (v == NULL) return -1;
    int left = height(v->left);
    int right = height(v->right);
    /* vrat max(left, right)+1 */
    if (left >= right) return left + 1;
    else return right + 1;
}

Ak máme binárny strom s n vrcholmi, aká môže byť jeho minimálna a maximálna výška?

  • Výška stromu s n vrcholmi je najviac n-1, ak sú všetky navešané jeden pod druhý, t.j. každý okrem posledného má jedného syna
  • Strom s výškou h má najviac 2^{{h+1}}-1 vrcholov
    • Dá sa dokázať indukciou vzhľadom na h
  • Takže vieme, že n\leq 2^{{h+1}}-1.
  • Vyjadríme h: h\geq \log _{2}(n+1)-1
  • Takže dostávame \log _{2}(n+1)-1\leq h\leq n-1
  • Napr. strom s milión vrcholmi má hĺbku medzi 19 a 999999