Prednáška 19

Oznamy

• Zajtrajšia rozcvička bude o vyfarbovaní
• Tretiu domácu úlohu treba odovzdať do budúceho pondelka 5. 12. 22:00.
• Príďte v piatok na cvičenia, ak potrebujete pomôcť s DÚ alebo s príkladmi z cvičení.
• Tento týždeň a budúci pondelok ešte prednášky v normálnom režime
• Budúcu stredu 7.12. v prvej polovici prednášky informácie k skúške a rady k skúškovému všeobecne, potom doberieme posledné učivo
• Posledný týždeň semestra v pondelok 12.12. nepovinná prednáška o nepreberaných črtách jazykov C a C++, v stredu 14.12. cez prednášku semestrálny test
• Cvičenia bežia normálne každý utorok, piatkové cvičenia už iba 2x

Semestrálny test

• Treba získať aspoň 50% bodov
• Opravný termín v januári
• Môžete si priniesť ťahák v rozsahu 1 listu A4
• Na semestrálnom teste budú podobné typy príkladov, aké poznáte z teoretických cvičení, napríklad napíšte funkciu, ktorá robí zadanú činnosť, doplňte chýbajúce časti funkcie, zistite, čo funkcia robí.
• Vyskytnú sa ale aj príklady, kde je úlohou napísať, ako bude na nejakom vstupe fungovať algoritmus alebo dátová štruktúra z prednášky. Ukážky takýchto príkladov nájdete na stránke Zimný semester, semestrálny test

Termíny skúšok

• Piatok 16.12. 13:10 v H6 a H3
• Utorok 10.1. 13:00 v H6 a H3
• Utorok 17.1. 13:00 v H6 a H3, hlavne 1. opravný termín
• Pondelok 30.1. 13:00 v H6, hlavne 2. opravný termín

Na termíny sa bude dať prihlasovať od stredy 30.11. 20:00

• Kapacita termínov bude obmedzená, prihláste sa teda radšej skôr, neskôr to môžete zmeniť
• Hláste sa iba na jeden termín!
• Ak vidíte konflikt niektorého termínu s hromadnou písomkou z iného predmetu, dajte mi prosím vedieť čím skôr, najneskôr v stredu
• Decembrový termín odporúčame hlavne študentom, ktorým programovanie nerobí problémy

Začneme s dokončením vyfarbovania z minulej prednášky

Aritmetické výrazy

Nejaký čas sa teraz budeme venovať spracovaniu aritmetických výrazov pozostávajúcich z reálnych čísel, operácií +,-,*,/ a zátvoriek (,). Prakticky najdôležitejšou úlohou tu je vyhodnotenie daného výrazu; napríklad pre výraz

(65 - 3 * 5) / (2 + 3)

chceme vedieť povedať, že jeho hodnota je 10. K tejto úlohe sa však dostaneme až časom. Najprv zavedieme a zľahka preskúmame dva alternatívne spôsoby zápisu aritmetických výrazov, z ktorých jeden nám vyhodnocovanie výrazov značne uľahčí.

Infixová notácia

Bežný spôsob zápisu aritmetických výrazov v matematike sa zvykne nazývať aj infixovou notáciou (prípadne infixovou formou alebo infixovým zápisom). Toto pomenovanie odkazuje na skutočnosť, že binárne operátory (ako napríklad +,-,*,/) sa v tejto notácii píšu medzi svojimi dvoma operandmi. Poradie vykonávania jednotlivých operácií sa pritom riadi zátvorkami a prioritou operácií.

Napríklad

(65 – 3 * 5) / (2 + 3)

je infixový výraz s hodnotou 10.

Prefixová notácia

Pri takzvanej prefixovej notácii (často podľa jej pôvodcu Jana Łukasiewicza nazývanej aj poľskou notáciou) sa každý operátor v aritmetickom výraze zapisuje pred svojimi dvoma operandmi.

Napríklad výraz (65 – 3 * 5) / (2 + 3) má prefixový zápis

/ - 65 * 3 5 + 2 3

Zaujímavosť: programovací jazyk Lisp a jeho varianty využívajú prefixovú notáciu na všetky výrazy, píšu však aj zátvorky, napríklad (+ 1 2).

Postfixová notácia

Pri postfixovej notácii (často nazývanej aj obrátenou poľskou notáciou) je situácia opačná: operátor sa zapisuje bezprostredne za svojimi dvoma operandmi.

Výraz (65 – 3 * 5) / (2 + 3) má teda postfixový zápis

65 3 5 * - 2 3 + /

Postfixová a prefixová notácia sú pre človeka o niečo ťažšie čitateľné, než bežná notácia infixová (čo môže byť aj otázkou zvyku). Uvidíme však, že najmä výrazy v postfixovej notácii sa dajú pomerne jednoducho vyhodnocovať. Výhodou postfixovej a prefixovej notácie oproti infixovej je aj to, že nepotrebujú zátvorky.

Nevýhodou naopak je, že bez zátvoriek v týchto notáciách nie je možné využiť unárny operátor -.

• Operátory +, * a / sú totiž vždy binárne, aplikujú sa na dva operandy.
• Operátor - môže byť binárny aj unárny, napríklad 1 - 2 je príklad výrazu, kde je binárny a 2 * -(2 + 3) je výraz s unárnym -
• Prefixový výraz - - 2 3 by teda mohol zodpovedať ako výrazu -2 - 3, tak aj výrazu -(2 - 3)
• Na vyriešenie tohto problému by sme v prefixových a postfixových výrazoch mohli pre unárne mínus zaviesť nejaký nový symbol.
• Druhá možnosť je úplne sa vyhnúť unárnemu mínus. Každý infixový podvýraz typu -cokolvek možno totiž ekvivalentne prepísať ako (0 - 1) * cokolvek.
• Pre jednoduchosť budeme v ďalších programoch predpokladať, že výrazy neobsahujú unárne mínus.

Vyhodnocovanie aritmetických výrazov v postfixovej notácii

Na vyhodnocovanie výrazov v postfixovej forme budeme používať zásobník, do ktorého budeme postupne vkladať jednotlivé operandy. Využijeme pritom vlastnosť, že operátor má v postfixovom zápise obidva operandy pred sebou. Keď teda narazíme na operátor, jeho operandy sme už prečítali a spracovali. Ide navyše o posledné dve prečítané alebo vypočítané hodnoty.

Výraz budeme postupne čítať zľava doprava:

• Keď pritom narazíme na operand, vložíme ho na zásobník.
• Keď narazíme na operátor:
  • Vyberieme zo zásobníka jeho dva operandy.
  • Prvé z týchto čísel je pritom druhým operandom a druhé z nich je prvým operandom.
  • Vykonáme s týmito operandmi danú operáciu a výsledok tejto operácie vložíme naspäť na zásobník.
• Tento postup opakujeme, až kým neprídeme na koniec výrazu. V tom okamihu by sme mali mať na zásobníku jediný prvok – výslednú hodnotu výrazu.

Cvičenie:

• Odsimulujme činnosť tohto algoritmu na našom vstupe 65 3 5 * - 2 3 + /
• Aké všelijaké prípady môžu nastať, keď na vstupe nemáme správny výraz v postfixovej notácii?

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

typedef double dataType;

/* Sem pride definicia struktury pre zasobnik 
 * a funkcii poskytovanych zasobnikom. */


int main() {
    // vstup budeme citat z konzoly
    FILE *fr = stdin;
        
    stack s;
    init(s);
    
    while (true) {
        // preskakujeme medzery na vstupe
        int c = getc(fr);
        while (c != EOF && c != '\n' && isspace(c)) {
            c = getc(fr);
        }
        // koniec riadku alebo EOF znamenaju koniec vyrazu
        if (c == EOF || c == '\n') {
            break;
        } else if (isdigit(c)) {
            // ked najdeme cifru, vratime ju 
            // a nacitame realne cislo
            ungetc(c, fr);
            double num;
            fscanf(fr, "%lf", &num);
            push(s, num);
        } else {
            // nacitali sme zrejme nejake znamienko 
            // vyberieme 2 operandy zo zasobnika
            // najskor druhy operand
            double num2 = pop(s);
            double num1 = pop(s);
            // vykoname operaciu podla typu operatora
            // a vysledok dame na zasobnik
            switch (c) {
                case '+':
                    push(s, num1 + num2);
                    break;
                case '-':
                    push(s, num1 - num2);
                    break;
                case '*':
                    push(s, num1 * num2);
                    break;    
                case '/':
                    push(s, num1 / num2);
                    break;    
            }
        }
    }
    
    // vysledna hodnota je na vrchu zasobnika,
    // vyberieme ju a vypiseme
    printf("%f\n", pop(s));
    // teraz by uz mal byt zasobnik prazdny
    assert(isEmpty(s));

    destroy(s);
}

Nasledujúca alternatívna implementácia vyhodnocovania postfixových výrazov sa od predchádzajúcej líši tým, že vstupný výraz najprv uloží do reťazca, ktorý následne vyhodnotí prostredníctvom funkcie evaluatePostfix. Drobnou nevýhodou tohto prístupu je, že dĺžka vstupného reťazca je obmedzená konštantou; funkcia vyhodnocujúca výraz uložený v reťazci sa nám však neskôr zíde.

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

typedef double dataType;


/* Sem pride definicia struktury pre zasobnik a funkcii poskytovanych zasobnikom. */


double evaluatePostfix(char *expr) {
    stack s;
    init(s);
    
    int i = 0;
    while (true) {
        while (expr[i] != 0 && expr[i] != '\n' && isspace(expr[i])) {
            i++;
        }
        if (expr[i] == 0 || expr[i] == '\n') {
            break;
        } else if (isdigit(expr[i])) {
            double num;
            sscanf(&expr[i], "%lf", &num);
            push(s, num);
            while (isdigit(expr[i]) || expr[i] == '.') {
                i++;
            } 
        } else {
            double num2 = pop(s);       
            double num1 = pop(s);       
            switch (expr[i]) {
                case '+':
                    push(s, num1 + num2);
                    break;
                case '-':
                    push(s, num1 - num2);
                    break;
                case '*':
                    push(s, num1 * num2);
                    break;    
                case '/':
                    push(s, num1 / num2);
                    break;    
            }
            i++;
        }
    }
    double result = pop(s);
    assert(isEmpty(s));
    destroy(s);
    
    return result;
}

int main() {
    FILE *fr = stdin;
        
    char expr[100];    
    fgets(expr, 100, fr);
    printf("%f\n", evaluatePostfix(expr));    
}

Prevod výrazu z infixovej do postfixovej notácie

• Pre bežnú prax je dôležitejšie vyhodnocovanie výrazov v klasickej infixovej notácii.
• Túto úlohu teraz vyriešime tak, že napíšeme program, ktorý preloží aritmetického výrazu z infixovej do postfixovej notácie.
• Následne ho môžeme vyhodnotiť algoritmom popísaným vyššie.
• Obidva procesy by sa dali vykonávať aj súčasne.
• Všeobecnejšie a elegantnejšie prístupy k analýze a vyhodnocovanie výrazov ale napríklad aj celých programov uvidíte na predmete Kompilátory (Mgr. štúdium), ktorý využíva poznatky z predmetu Formálne jazyky a algoritmy (semester 2Z).

Popis algoritmu

Uvažujme najprv výrazy bez zátvoriek (a bez unárnych mínusov).

• Pozostávajú teda z čísel a binárnych operátorov +, -, *, /, kde * a / majú vyššiu prioritu ako + a -.
• Všetky tieto operátory sú navyše zľava asociatívne, t.j. napr. 30 / 6 / 5 je to isté ako (30 / 6) / 5.

Na prevod takéhoto jednoduchého výrazu do postfixového tvaru ním teda stačí prejsť zľava doprava a všimnúť si dve skutočnosti:

• Poradie jednotlivých čísel v postfixovom výraze je rovnaké, ako v pôvodnom infixovom výraze.
• Napríklad výraz 1 + 2 + 3 * 4 - 5 má postfixový tvar 1 2 + 3 4 * + 5 -.
• Z toho vyplýva, že pri prechádzaní vstupným infixovým výrazom možno čísla priamo vypisovať do výstupného postfixového výrazu bez toho, aby nás ďalej zaujímali.
• Každý operátor treba presunúť spomedzi jeho dvoch argumentov za jeho druhý argument.
• Ak teda vo vstupnom infixovom výraze narazíme na operátor, nevypíšeme ho hneď do výstupného výrazu, ale uložíme ho pre neskorší výpis na správnej pozícii.
• Uložený operátor potom treba vypísať za jeho druhým argumentom. Ak pritom aj samotný tento argument obsahuje nejaké ďalšie operátory, určite musia byť vypísané skôr. Operátory teda budeme ukladať na zásobník.
• Zakaždým, keď vo vstupnom infixovom výraze narazíme na operátor, je možné, že tesne pred ním končí argument jedného alebo niekoľkých operátorov uložených na zásobníku. Vďaka ľavej asociatívnosti pritom ide o práve všetky operátory na vrchu zásobníka, ktoré majú vyššiu alebo rovnakú prioritu, ako nájdený operátor. Všetky tieto operátory teda postupne vyberieme zo zásobníka a vypíšeme ich do výstupného reťazca. Až následne na zásobník vložíme nájdený operátor.
• Na konci vstupného reťazca vypíšeme všetky operátory, ktoré zostali na zásobníku.

Z technických dôvodov budeme na spodku zásobníka uchovávať „umelé dno” #, ktoré budeme chápať ako symbol s nižšou prioritou ako všetky operátory.

• Situáciu, keď pri vyberaní operátorov zo zásobníka narazíme na jeho dno tak budeme môcť riešiť konzistentne so situáciou, keď narazíme na operátor s nižšou prioritou – v oboch prípadoch chceme s vyberaním prestať.

Na vstupnom výraze 1 + 2 + 3 * 4 - 5 bude práve popísaný algoritmus pracovať nasledovne:

Vstupný symbol    Výstupný reťazec   Zásobník (dno vľavo) 
------------------------------------------------------------------------------------------------------------
             1                       #                 vypíš číslo 1 na výstup 
                  1                  #

             +    1                  #                 # má nižšiu prioritu ako +, nevyberaj ho
                  1                  # +               vlož + na zásobník

             2    1                  # +               vypíš číslo 2 na výstup
                  1 2                # + 

             +    1 2                # +               + má rovnakú prioritu ako +, vyber + a vypíš
                  1 2 +              #                 # má nižšiu prioritu ako +, nevyberaj ho
                  1 2 +              #                 vlož + na zásobník
                  1 2 +              # +   

             3    1 2 +              # +               vypíš číslo 3 na výstup
                  1 2 + 3            # + 

             *    1 2 + 3            # +               + má nižšiu prioritu ako *, nevyberaj ho
                  1 2 + 3            # + *             vlož * na zásobník

             4    1 2 + 3            # + *             vypíš číslo 4 na výstup
                  1 2 + 3 4          # + *                     

             -    1 2 + 3 4          # + *             * má vyššiu prioritu ako -, vyber - a vypíš
                  1 2 + 3 4 *        # +               + má rovnakú prioritu ako -, vyber + a vypíš
                  1 2 + 3 4 * +      #                 # má nižšiu prioritu ako -, nevyberaj ho
                  1 2 + 3 4 * +      # -               vlož - na zásobník

             5    1 2 + 3 4 * +      # -               vypíš číslo 5 na výstup
                  1 2 + 3 4 * + 5    # -                 

[koniec vstupu]   1 2 + 3 4 * + 5    # -               vyber a vypíš operátory na zásobníku
                  1 2 + 3 4 * + 5 -  #                 <-- VÝSLEDNÝ POSTFIXOVÝ VÝRAZ

Do tejto schémy je už jednoduché zapracovať aj zátvorky:

• Keď vo vstupnom infixovom reťazci narazíme na ľavú zátvorku, vložíme ju do zásobníka. Podobne ako pri # ju budeme považovať za symbol s nižšou prioritou, než všetky binárne operátory (argument operátora spred tejto zátvorky totiž určite nemôže končiť v jej vnútri).
• Keď narazíme na pravú zátvorku, potrebujeme vypísať všetky doposiaľ nevypísané operátory uzatvorené touto zátvorkou. Preto vyberieme a vypíšeme na výstup všetky operátory zo zásobníka až po prvú ľavú zátvorku (ktorú zo zásobníka taktiež vyberieme).

Implementácia

Funkcia infixToPostfix, realizujúca prevod z infixovej do postfixovej notácie:

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

typedef char dataType;


/* Sem pride definicia struktury pre zasobnik a funkcii poskytovanych zasobnikom. */

int precedence(char op) {
    if (op == '#' || op == '(') return 0; // specialne pripady
    if (op == '-' || op == '+') return 1;
    if (op == '*' || op == '/') return 2;
    assert(false); // sem by sme sa nemali dostat    
}

/* Skonvertuje infixovy vyraz infix to postfixovej formy 
 * a vysledok ulozi do retazca postfix */
void infixToPostfix(const char *infix, char *postfix) {
    stack s;
    init(s);
    push(s, '#');
    
    int j = 0; // index do vystupneho retazca
    for (int i = 0; infix[i] != 0; i++) {
        if (isdigit(infix[i]) || infix[i] == '.') {
            postfix[j++] = infix[i];
        } else if (isspace(infix[i])) { // biele znaky preskakujeme
        } else if (infix[i] == '(') { // zaciatok zatvorky na zasobnik
            push(s, infix[i]);
        } else if (infix[i] == ')') {
            /* koniec zatvorky: vypiseme vsetky operatory, 
             * co boli v 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]); 
            while (precedence(peek(s)) >= p) {
                postfix[j++] = pop(s);
                postfix[j++] = ' ';
            }
            push(s, infix[i]);
        }
    }

    while (!isEmpty(s)) {
        char c = pop(s);
        if (c != '#') {
            postfix[j++] = ' ';
            postfix[j++] = c;
        }
    }
    postfix[j] = 0;
    destroy(s);
}

const int maxN = 100;

int main() {
    char infix[maxN];
    char postfix[2 * maxN];
    
    fgets(infix, maxN, stdin);
    infixToPostfix(infix, postfix);
    
    printf("Postfixovy tvar vyrazu: %s\n", postfix);
}

Cvičenie: Rozšírte program vyššie o operáciu umocňovania ^ s prioritou vyššou ako * (dajte si pritom pozor na fakt, že umocňovanie je na rozdiel od operácií +, -, *, / sprava asociatívne).

Rozšírenie na infixové výrazy obsahujúce unárne mínus

• Prevod infixového výrazu do postfixového tvaru môžeme rozšíriť o spracovanie unárneho operátora -, tým, že ho z výrazu odstránime pred prevodom.
• Napíšeme funkciu normalise, ktorá v danom infixovom výraze nahradí všetky výskyty unárneho mínusu reťazcom (0-1)* a výsledok uloží do (opäť infixového) výrazu out.
• Mínus je v korektnom infixovom výraze unárny práve vtedy, keď nenasleduje za číslom, ani za pravou zátvorkou (biele znaky pritom ignorujeme).

void normalise(const char *in, char *out) {
    int j = 0; // index do vystupneho retazca
    bool hasOperand = false;
    for (int i = 0; in[i] != 0; i++) {
        if (in[i] == '-' && !hasOperand) {
            out[j++] = '(';
            out[j++] = '0';
            out[j++] = '-';
            out[j++] = '1';
            out[j++] = ')';
            out[j++] = '*';
        } else if (isdigit(in[i]) || in[i] == '.' 
                   || in[i] == ')') {
            out[j++] = in[i];
            hasOperand = true;
        } else if (isspace(in[i])) {
            out[j++] = in[i];
        } else {
            out[j++] = in[i];
            hasOperand = false;
        }
    }
    out[j] = 0;
}

Typ dát na zásobníku

Ak by sme chceli v tom istom programe spraviť aj prevod z infixu do postfixu aj vyhodnotenie postfixu, máme problém:

• Funkcia evaluatePostfix využíva zásobník prvkov typu double ale funkcia infixToPostfix využíva zásobník prvkov typu char.
• Pri našej implementácii vieme do zásobníka vkladať iba jeden typ dát
• Ak by sme ako datatype pre zásobník zvolili double, pri vkladaní a vyberaní znakov by sa znaky konvertovali na reálne čísla a naspať. Program by bol síce funkčný, ale nie príliš elegantný.
• Druhá možnosť je dvakrát implementovať celý zásobník pre rôzne typy dát, kopírovanie a menenie kódu je však tiež niečo, čomu sa chceme vyhnúť.
• Najlepšie by bolo použiť techniku generického programovania, ktorá je k dispozícii vo veľa jazykoch, vrátane C++, ale nie C. Touto technikou vieme zásobník implementovať raz a použiť s rôznymi typmi.