Prednáška 20

Oznamy

• Na testovači dnes pribudnú nejaké úlohy z budúcich cvičení, ktoré vám pomôžu s prípravou na test.
• V piatok sú cvičenia nepovinné, budú na nich vzorové riešenia testu. Môžeme vám tiež poradiť s riešením úloh z cvičení alebo domácej úlohy, prípadne ak máte otázky k ukážkovým príkladom na test.
• Termín DÚ3 je v piatok večer.
• Takisto do piatka je potrebné hlásiť záujem o prípadný preklad zadaní, viď informácie k testu

Opakovanie z minulej prednášky

Aritmetické výrazy

• Bežná infixová notácia, 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

Strom pre výraz (65 – 3 * 5)/(2 + 3)

Aritmetické výrazy môžeme veľmi prirodzene reprezentovať vo forme stromu

• Operátory a čísla tvoria tzv. uzly (alebo vrcholy) stromu.
• Operátory tvoria tzv. vnútorné uzly stromu, každý z nich má dve deti zodpovedajúce podvýrazom pre jednotlivé operandy.
  • Pre jednoduchosť na dnešnej prednáške neuvažujeme unárne mínus, dalo by sa však ľahko dorobiť.
• Čísla tvoria tzv. listy stromu, tie už nemajú žiadne deti.
• Strom obsahuje jediný uzol, ktorý nemá rodiča. Tento sa nazýva koreň stromu a reprezentuje celý aritmetický výraz.
• Informatici stromy väčšinou kreslia „hore nohami”, s koreňom na vrchu.

Uzol takéhoto stromu tak môžeme reprezentovať napríklad nasledujúcou štruktúrou:

struct treeNode {
    // číselná hodnota (len v listoch)
    double val;

    // operátor vo vnútorných uzloch, pre listy medzera
    char op;

    // smerníky na podstromy
    treeNode * left, * right;
};

Pre vnútorné uzly stromu (zodpovedajúce operátorom) pritom:

• Smerníky left a right budú ukazovať na korene podstromov reprezentujúcich ľavý resp. pravý podvýraz.
• Znak op bude zodpovedať danému operátoru (napríklad '+').
• Hodnota val ostane nevyužitá.

Pre listy (zodpovedajúce číselným hodnotám) naopak:

• Smerníky left a right budú mať hodnotu NULL.
• Znak op bude medzera ' ' (podľa op teda môžeme rozlišovať, či ide o číslo alebo o operátor).
• Vo val bude uložená hodnota daného čísla.

Celý strom pritom budeme reprezentovať jeho koreňom.

V tejto reprezentácii sú niektoré položky štruktúry treeNode nevyužité (napr. val vo vnútorných vrcholoch). S využitím objektového programovania (letný semester) budeme vedieť stromy pre aritmetické výrazy reprezentovať elegantnejšie.

Vytvorenie uzlu

Nasledujúce funkcie vytvoria nový vnútorný uzol (pre operátor) resp. nový list (pre číslo):

treeNode * createOp(char op, treeNode * left, treeNode * right) {
    treeNode * v = new treeNode;
    v->left = left;
    v->right = right;
    v->op = op;
    return v; 
}

treeNode * createNum(double val) {
    treeNode * v = new treeNode;
    v->left = NULL;
    v->right = NULL;
    v->op = ' ';
    v->val = val;
    return v;
}

„Ručne” teraz môžeme vytvoriť strom pre výraz (65 – 3 * 5)/(2 + 3):

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

Alebo po častiach:

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

Ďalší plán

Ďalej uvidíme:

• jednoduchú rekurzívnu funkciu na vyhodnotenie výrazu uloženého ako strom,
• ďalšie rekurzívne funkcie na uvoľnenie pamäte stromu a výpis výrazu,
• funkciu na vytvorenie stromu z postfixového výrazu.

Stromy majú v informatike veľa využití, nielen na aritmetické výrazy. Ďalej sa teda budeme venovať práci so stromami všeobecne.

Uvoľnenie pamäte

Nasledujúca funkcia uvoľní z pamäte celý strom s koreňom root.

• Opäť používa rekurziu na prejdenie celého stromu.
• Pozor na poradie príkazov, treba najskôr uvoľniť podstromy až potom zavolať delete na root, inak by sme stratili prístup k deťom.
• Všimnite si, ako sú riešené triviálne prípady, funkcia ani nezisťuje, s akým typom uzla pracuje.

void destroyTree(treeNode * root) {
    if (root != NULL) {
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
    }
}

Vypísanie výrazu reprezentovaného stromom v rôznych notáciách

Infixovú, prefixovú, resp. postfixovú reprezentáciu aritmetického výrazu reprezentovaného stromom s koreňom root možno získať pomocou nasledujúcich funkcií.

• Opäť používajú rekurziu na prejdenie celého stromu.
• Líšia sa hlavne umiestnením príkazu na vypísanie operátora (pred, medzi alebo za rekurzívnym vypísaním podvýrazov).
• Infixová notácia potrebuje aj zátvorky. Táto funkcia ich pre istotu dáva všade. Rozmyslite si, ako by sme ich vedeli vypísať iba tam, kde treba.
• Ako by sme funkcie rozšírili pre unárne mínus?

/** Funkcia vypíše aritmetický výraz v inorder poradí */
void printInorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g", root->val);
    } else {
        printf("(");
        printInorder(root->left);
        printf(" %c ", root->op);
        printInorder(root->right);
        printf(")");
    }
}

/** Funkcia vypíše aritmetický výraz v preorder poradí */
void printPreorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g ", root->val);
    } else {
        printf("%c ", root->op);
        printPreorder(root->left);
        printPreorder(root->right);
    }
}

/** Funkcia vypíše aritmetický výraz v postorder poradí */
void printPostorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g ", root->val);
    } else {
        printPostorder(root->left);
        printPostorder(root->right);
        printf("%c ", root->op);
    }
}

Vytvorenie stromu z postfixového výrazu

Pripomeňme si z minulej prednášky funkciu na vyhodnocovanie postfixového výrazu:

/** Funkcia vyhodnotí a vráti hodnotou výrazu v postfixovom tvare. */
double evaluatePostfix(tokenSequence & tokens) {
    // zásobník, do ktorého ukladáme čísla
    stack numberStack;
    init(numberStack);

    for (int i = 0; i < tokens.length; i++) {
        // aktuálny token zo vstupu
        token curToken = tokens.items[i];
        if (curToken.op == ' ') {
            // čísla rovno ukladáme na zásobník
            push(numberStack, curToken);
        } else {
            // spracovanie operátora
            token num1, num2, result;
            // najskôr vyberieme 1 alebo 2 čísla zo zásobníka
            if (curToken.op == '~') {
                num1 = pop(numberStack);
            } else {
                num2 = pop(numberStack);
                num1 = pop(numberStack);
            }
            // na operandy aplikujeme operátor
            applyOp(curToken, num1, num2, result);
            // výsledné číslo uložíme na zásobník
            push(numberStack, result);
        }
    }
    // zo zásobníka vyberieme výsledné číslo
    token result = pop(numberStack);
    // skontrolujeme, že zásobník je prázdny a výsledok je číslo
    assert(isEmpty(numberStack) && result.op == ' ');
    // uvoľníme pamäť zásobníka
    destroy(numberStack);
    return result.val;
}

• Túto funkciu možno jednoducho prepísať tak, aby namiesto vyhodnocovania výrazu konštruovala zodpovedajúci aritmetický strom.
• Namiesto hodnôt jednotlivých podvýrazov stačí na zásobníku uchovávať korene stromov, ktoré tieto podvýrazy reprezentujú.
• Aplikácii aritmetickej operácie bude zodpovedať spojenie dvoch podstromov do jedného stromu.
• V tomto prípade nepoužívame postupnosť symbolov (tokenov), ale priamo spracovávame postfixový výraz vo forme reťazca.

typedef treeNode *dataType;


/* Sem príde definícia štruktúry pre zásobník a všetkých funkcií poskytovaných zásobníkom. */
treeNode * postfixToTree(char * str) {
    // zásobník, do ktorého ukladáme korene podstromov
    stack treeStack;
    init(treeStack);

    int strPos = 0;  // pozícia v rámci reťazca
    while (str[strPos] != 0) {  // kým nie sme na konci str
        if (isspace(str[strPos])) {  // preskakujeme biele znaky
            strPos++;
        } else if (isdigit(str[strPos]) || str[strPos] == '.') {
            // keď nájdeme cifru alebo bodku (začiatok čísla)
            double val;
            int skip;
            // načítame toto číslo pomocou sscanf,
            // do skip uložíme počet znakov čísla
            sscanf(&(str[strPos]), "%lf%n", &val, &skip);
            // preskočíme všetky znaky čísla
            strPos += skip;

            // vytvoríme list a uložíme na zásobník
            push(treeStack, createNum(val));
        } else {
            // spracovanie operátora
            assert(strchr("+-/*", str[strPos]) != NULL);
            treeNode * left, * right;
            // najskôr vyberieme 2 podstromy zo zásobníka
            // vytvoríme nový koreň,
            // ktorý bude ich rodičom a vložíme na zásobník
            right = pop(treeStack);
            left = pop(treeStack);
            push(treeStack, createOp(str[strPos], left, right));
            strPos++;
        }
    }
    // zo zásobníka vyberieme výsledný strom
    treeNode * result = pop(treeStack);
    // skontrolujeme, že zásobník je prázdny
    assert(isEmpty(treeStack));
    // uvoľníme pamäť zásobníka
    destroy(treeStack);
    return result;
}

Ukážkový program pracujúci so stromami pre aritmetické výrazy

Nasledujúci program prečíta z konzoly aritmetický výraz v postfixovom tvare, skonštruuje jeho aritmetický strom a následne preň zavolá funkcie na výpočet hodnoty výrazu a jeho výpis v rôznych notáciách. Celý program je na konci prednášky.

int main() {
    // načítame postfixový výraz do reťazca
    const int maxLine = 100;
    char postfix[maxLine];
    fgets(postfix, maxLine, stdin);
    // výraz konvertujeme na strom
    treeNode * root = postfixToTree(postfix);
    // spočítame hodnotu výrazu
    double value = evaluateTree(root);
    printf(" value: %g\n", value);
    // vypíšeme vo všetkých troch notáciách
    printf(" inorder: ");
    printInorder(stdout, root);
    printf("\n predorder: ");
    printPreorder(stdout, root);
    printf("\n postdorder: ");
    printPostorder(stdout, root);
    printf("\n");
    // uvoľníme pamäť
    destroyTree(root);
}

Program pre aritmetické výrazy ako stromy

#include <cstdio>
#include <cctype>
#include <cassert>
#include <cstring>
using namespace std;

struct treeNode {
    // číselná hodnota (len v listoch)
    double val;

    // operátor vo vnútorných uzloch, pre listy medzera
    char op;

    // smerníky na podstromy
    treeNode * left, * right;
};

/** Funkcia vráti nový uzol pre operátor */
treeNode * createOp(char op, treeNode * left, treeNode * right) {
    treeNode * v = new treeNode;
    v->left = left;
    v->right = right;
    v->op = op;
    return v;
}

/** Funkcia vráti nový uzol pre číslo */
treeNode * createNum(double val) {
    treeNode * v = new treeNode;
    v->left = NULL;
    v->right = NULL;
    v->op = ' ';
    v->val = val;
    return v;
}


// Nasleduje kód pre zásobník uzlov stromu
typedef treeNode * dataType;

/** Uzol spájaného zoznamu pre zásobník */
struct node {
    dataType data; // dáta uložené v uzle
    node * next;   // smerník na ďalší uzol zoznamu
};

/** Štruktúra pre zásobník implementovaný pomocou zoznamu*/
struct stack {
    node * top; // Smernik na vrch zasobníka  alebo NULL
};

/** Funkcia inicializuje prázdny zásobník */
void init(stack & s) {
    s.top = NULL;
}

/** Funkcia zistí, či je zásobník prázdny */
bool isEmpty(stack & s) {
    return s.top == NULL;
}

/** Funkcia pridá prvok item na vrch zásobníka */
void push(stack & s, dataType item) {
    node * tmp = new node;
    tmp->data = item;
    tmp->next = s.top;
    s.top = tmp;
}

/** Funkcia odoberie prvok z vrchu zasobnika a vráti ho */
dataType pop(stack & s) {
    assert(!isEmpty(s));
    dataType result = s.top->data;
    node * tmp = s.top->next;
    delete s.top;
    s.top = tmp;
    return result;
}

/** Funkcia vráti prvok na vrchu zásobníka, ale nechá ho v zásobníku */
dataType peek(stack & s) {
    assert(!isEmpty(s));
    return s.top->data;
}

/** Funkcia uvoľní pamäť zásobníka */
void destroy(stack & s) {
    while (!isEmpty(s)) {
        pop(s);
    }
}

/** Funkcia konvertuje výraz v postfixovom tvare na strom */
treeNode * postfixToTree(char * str) {
    // zásobník, do ktorého ukladáme korene podstromov
    stack treeStack;
    init(treeStack);

    int strPos = 0;  // pozícia v rámci reťazca
    while (str[strPos] != 0) {  // kým nie sme na konci str
        if (isspace(str[strPos])) {  // preskakujeme biele znaky
            strPos++;
        } else if (isdigit(str[strPos]) || str[strPos] == '.') {
            // keď nájdeme cifru alebo bodku (začiatok čísla)
            double val;
            int skip;
            // načítame toto číslo pomocou sscanf,
            // do skip uložíme počet znakov čísla
            sscanf(&(str[strPos]), "%lf%n", &val, &skip);
            // preskočíme všetky znaky čísla
            strPos += skip;

            // vytvoríme list a uložíme na zásobník
            push(treeStack, createNum(val));
        } else {
            // spracovanie operátora
            assert(strchr("+-/*", str[strPos]) != NULL);
            treeNode * left, * right;
            // najskôr vyberieme 2 podstromy zo zásobníka
            // vytvoríme nový koreň,
            // ktorý bude ich rodičom a vložíme na zásobník
            right = pop(treeStack);
            left = pop(treeStack);
            push(treeStack, createOp(str[strPos], left, right));
            strPos++;
        }
    }
    // zo zásobníka vyberieme výsledný strom
    treeNode * result = pop(treeStack);
    // skontrolujeme, že zásobník je prázdny
    assert(isEmpty(treeStack));
    // uvoľníme pamäť zásobníka
    destroy(treeStack);
    return result;
}

/** Funkcia spočíta hodnotu výrazu reprezentovaného stromom */
double evaluateTree(treeNode * root) {
    assert(root != NULL);
    if (root->op == ' ') {
        return root->val;
    } else {
        double valLeft = evaluateTree(root->left);
        double valRight = evaluateTree(root->right);
        switch (root->op) {
        case '+':
            return valLeft + valRight;
            break;
        case '-':
            return valLeft - valRight;
            break;
        case '*':
            return valLeft * valRight;
            break;
        case '/':
            return valLeft / valRight;
            break;
        default:
            assert(false);
            break;
        }
    }
    return 0; // realne nedosiahnutelny prikaz
}

/** Funkcia uvoľní pamäť daného stromu */
void destroyTree(treeNode * root) {
    if (root != NULL) {
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
    }
}

/** Funkcia vypíše aritmetický výraz v inorder poradí */
void printInorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g", root->val);
    } else {
        printf("(");
        printInorder(root->left);
        printf(" %c ", root->op);
        printInorder(root->right);
        printf(")");
    }
}

/** Funkcia vypíše aritmetický výraz v preorder poradí */
void printPreorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g ", root->val);
    } else {
        printf("%c ", root->op);
        printPreorder(root->left);
        printPreorder(root->right);
    }
}

/** Funkcia vypíše aritmetický výraz v postorder poradí */
void printPostorder(treeNode * root) {
    if (root->op == ' ') {
        printf("%g ", root->val);
    } else {
        printPostorder(root->left);
        printPostorder(root->right);
        printf("%c ", root->op);
    }
}


int main() {
    // načítame postfixový výraz do reťazca
    const int maxLine = 100;
    char postfix[maxLine];
    fgets(postfix, maxLine, stdin);
    // výraz konvertujeme na strom
    treeNode * root = postfixToTree(postfix);
    // spočítame hodnotu výrazu
    double value = evaluateTree(root);
    printf(" value: %g\n", value);
    // vypíšeme vo všetkých troch notáciách
    printf(" inorder: ");
    printInorder(root);
    printf("\n predorder: ");
    printPreorder(root);
    printf("\n postdorder: ");
    printPostorder(root);
    printf("\n");
    // uvoľníme pamäť
    destroyTree(root);
}