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
• Pondelok 9.1. 13:00 v H6 a H3
• Pondelok 23.1. 9: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 skúškou alebo 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. Najprv ale zavedieme 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.

Unárne mínus

• Operátory +, * a / sú vždy binárne, čo znamená, že sa aplikujú sa na dva operandy.
• Operátor - môže byť binárny aj unárny (unárny znamená, že sa aplikuje na jeden operand).
  • Príklad s binárnym mínus: 1 - 2.
  • Príklad s unárnym mínus: 2 * -(2 + 3).
• Nevýhodou postfixovej a prefixovej notácie je, že bez zátvoriek v nich nie je možné rozpoznať binárne a unárne mínus.
  • Prefixový výraz - - 2 3 by napríklad mohol zodpovedať ako výrazu -2 - 3 aj výrazu -(2 - 3).
• Na vyriešenie tohto problému budeme na unárne mínus používať znamienko ~. V infixových výrazoch budú unárne mínus automaticky rozpoznané a nahradené ~.

Predspracovanie výrazu

Používateľ zadá výraz ako text v niektorej notácii. Aby sa nám s ním lepšie pracovalo, prevedieme ho najskôr na postupnosť symbolov (angl. token), pričom každý symbol bude buď číslo reprezentované v premennej typu double alebo znak reprezentujúci operátor alebo zátvorku.

Jednotlivé symboly budeme ukladať do záznamov typu token

struct token {
    char op;   
    double val;
};

• Ak štruktúra obsahuje číslo, op bude medzera a samotné číslo bude v položke val.
• Ak štruktúra reprezentuje iný symbol, tento symbol bude v položke op a položka val sa nebude používať.

Postupnosť symbolov uložíme do štruktúry tokenSequence, ktorá obsahuje pole položiek typu token a tiež koľko položiek bolo do poľa uložených.

struct tokenSequence {
    token * items;  // pole tokenov
    int size;       // veľkosť alokovaného poľa
    int length;     // počet tokenov uložených v poli
};

Preklad výrazu na postupnosť symbolov realizuje funkcia tokenize.

• Na načítanie čísla používame funkciu sscanf, ktorá vyzerá podobne ako scanf, ale načítava zo zadaného reťazca
  • Ako reťazec zadáme &(str[strPos]), čo spôsobí, že sa začne načítavať od pozície strPos, mohli by sme písať aj str+strPos.
  • Formátovací znak %n nám do premennej skip uloží počet znakov, ktoré sa pri načítaní čísla použili, tento o tento počet potom posunieme premennú strPos.
• Kód token newToken = {str[strPos], 0} inicializuje položku op na znak str[strPos] a položku val na nulu.
• Pomocné funkcie init a addToken pracujú s postupnosťou symbolov, nájdete ich v programe na konci prednášky.

void tokenize(char * str, tokenSequence & tokens) {
    init(tokens, strlen(str));  // inicializujeme prázdnu postupnosť

    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);
            // vytvoríme a uložíme token
            token newToken = {' ', val};
            addToken(tokens, newToken);
            // preskočíme všetky znaky čísla
            strPos += skip;
        } else {
            // spracovanie zátvoriek alebo operátora
            assert(strchr("+-/*()~", str[strPos]) != NULL);
            // vytvoríme a uložíme token
            token newToken = {str[strPos], 0};
            addToken(tokens, newToken);
            strPos++;
        }
    }
}

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

• Budeme používať zásobník, do ktorého budeme vkladať čísla čakajúce na spracovanie.
• Operátor má v postfixovom zápise obidva operandy pred sebou. Keď 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ď narazíme na číslo, 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.
• Pri unárnom mínus vyberáme zo zásobníka iba jeden operand.
• 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.

Technická poznámka:

• Keďže vo výslednom programe budeme potrebovať zásobníky čísel aj znakov, používame v ňom zásobník položiek typu token. Ak by sme však robili čisto vyhodnocovanie postfixovej notácie, stačil by nám zásobník s prvkami typu double.

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?

typedef token dataType;
// Nasleduje kód pre zásobník tokenov
// ...


/** Funkcia aplikuje operátor uložený v opToken na čísla
* uložené v num1 a num2, výsledok uloží ako číslo do result.
* Unárny operátor sa aplikuje iba na num1. */
void applyOp(token opToken, token num1, token num2, token & result) {
    result.op = ' ';
    switch (opToken.op) {
    case '~':
        result.val = -num1.val;
        break;
    case '+':
        result.val = num1.val + num2.val;
        break;
    case '-':
        result.val = num1.val - num2.val;
        break;
    case '*':
        result.val = num1.val * num2.val;
        break;
    case '/':
        result.val = num1.val / num2.val;
        break;
    default: // iné operátory nepovoľujeme.
        assert(false);
    }
}

/** 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;
}

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 funkciu, ktorá preloží aritmetický výraz z infixovej do postfixovej notácie.
• Následne ho môžeme vyhodnotiť algoritmom popísaným vyššie.

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 výrazu do postfixového tvaru ním 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 -.
• Prechádzaní vstupným infixovým výrazom budeme teda čísla priamo pridávať do výstupného postfixového výrazu.
• Každý operátor treba presunúť spomedzi jeho dvoch operandov za jeho druhý operand.
• Ak teda vo vstupnom infixovom výraze narazíme na operátor, nepridáme ho hneď do výstupného výrazu, ale uložíme ho pre neskoršie pridanie na správnej pozícii.
• Uložený operátor treba vypísať za jeho druhým operandom. Ak pritom aj samotný operand obsahuje nejaké ďalšie operátory, určite musia byť vypísané skôr. Operátory teda budeme ukladať na zásobník.
• Keď vo vstupnom infixovom výraze narazíme na operátor, je možné, že tesne pred ním končí operand 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ý výraz    Zásobník (dno vľavo) 
------------------------------------------------------------------------------------------------------------
             1                       #                 pridaj 1 na výstup 
                  1                  #

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

             2    1                  # +               pridaj 2 na výstup
                  1 2                # + 

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

             3    1 2 +              # +               pridaj 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            # + *             pridaj 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 * +      # -               pridaj 5 na výstup
                  1 2 + 3 4 * + 5    # -                 

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

Pridanie zátvoriek:

• 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).

Pridanie unárneho mínus:

• Unárne mínus má vyššiu prioritu ako binárne operátory. Predpokladáme, že ho máme zapísané ako ~.
• Je však sprava asociatívne, t.j. --2 je to isté ako -(-2) a v postfixovom tvare to bude 2 ~ ~
• Preto ak je aktuálny operátor unárne mínus (~), nevyhadzujeme iné unárne mínus zo zásobníka. Toto je v programe dosiahnuté tak, že nové unárne mínus ("pravé") má vyššiu prioritu ako to, čo už je na zásobníku ("ľavé").

Implementácia

/** Pomocná funkcia, ktorá vráti prioritu operátora.
 * Argument right určuje, či ide o pravý z dvoch porovnávaných operátorov */
int priority(char op, bool right) {
    if (op == '#' || op == '(') return 0;
    if (op == '-' || op == '+') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '~' && !right) return 3;
    if (op == '~' && right) return 4;
    assert(false); // sem by sme sa nemali dostať
}

/** Skonvertuje infixový výraz infix do postfixovej formy */
void infixToPostfix(tokenSequence & infix, tokenSequence & postfix) {
    // inicializuje výslednú postupnosť tokenov
    init(postfix, infix.length);

    // vytvoríme zásobník operátorov a na spodok dáme #
    stack opStack;
    init(opStack);
    token curToken = {'#', 0};
    push(opStack, curToken);

    for (int i = 0; i < infix.length; i++) {
        // aktuálny token zo vstupu
        curToken = infix.items[i];
        if (curToken.op == ' ') {
            // čísla rovno skopírujeme do výstupu
            addToken(postfix, curToken);
        } else if (curToken.op == '(') {
            // začiatok zátvorky uložíme na zásobník
            push(opStack, curToken);
        } else if (curToken.op == ')') {
            // koniec zátvorky:
            // na výstup pridáme zo zásobníka operátory,
            // ktoré boli v zátvorke
            token popped = pop(opStack);
            while (popped.op != '(') {
                addToken(postfix, popped);
                popped = pop(opStack);
            }
        } else {
            // spracovanie operátora:
            // na výstup pridáme zo zásobníka operátory s vyššou prioritou
            int p = priority(curToken.op, true);
            while (priority(peek(opStack).op, false) >= p) {
                token popped = pop(opStack);
                addToken(postfix, popped);
            }
            // aktuálny operátor dáme na zásobník
            push(opStack, curToken);
        }
    }

    // zvyšné operátory presunieme zo zásobníka na výstup
    while (peek(opStack).op != '#') {
        token popped = pop(opStack);
        addToken(postfix, popped);
    }
    destroy(opStack);
}

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).

Predspracovanie unárneho mínus

• Pre prevodom infixového výrazu do postfixového tvaru potrebujeme v infixovom výraze nahradiť unárne mínus znakom ~.
• Rob9 to funkcia fixUnaryMinus.
• Mínus je v korektnom infixovom výraze unárny práve vtedy, keď nenasleduje za číslom, ani za pravou zátvorkou, čo testuje pomocná funkcia isOperand<-tt>.

/** Pomocná funkcia, ktorá vráti, či token je koncom operandu v infixovej notácii */
bool isOperand(token curToken) {
    return curToken.op == ' ' || curToken.op == ')';
}

/** Funkcia, ktorá v infixovom výraze zmení unárne mínus na ~ */
void fixUnaryMinus(tokenSequence &infix) {
    for (int i = 0; i < infix.length; i++) {
        if(infix.items[i].op=='-' 
           && (i==0 || !isOperand(infix.items[i-1]))) {
            infix.items[i].op = '~';
        }
    }
}

Záverečné poznámky

• Infixové výrazy vieme teda vyhodnotiť tak, že najskôr ich prevedieme na postfixové a tie potom vyhodnotíme.
• Obidva procesy by sa dali vykonávať aj súčasne (počas prechodu reťazcom by sme používali jeden zásobník operandov a jeden zásobník operátorov).
• 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 automaty (semester 2Z).

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 (naraz alebo jedno po druhom), 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.

Program na prácu s výrazmi

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

/** Štruktúra pre jednu súčasť výrazu: znamienko alebo číslo */
struct token {
    char op;     // znamienko alebo medzera, ak ide o číslo
    double val;  // číselná hodnota, ak je op medzera
};

/** Štruktúra pre postupnosť tokenov */
struct tokenSequence {
    token * items;  // pole tokenov
    int size;       // veľkosť alokovaného poľa
    int length;     // počet tokenov uložených v poli
};

/** Funkcia inicializuje prázdnu postupnosť tokenov
pričom alokuje pole požadovanej veľkosti. */
void init(tokenSequence & tokens, int size) {
    tokens.items = new token[size];
    tokens.size = size;
    tokens.length = 0;
}

/** Funkcia do postupnosti tokenov pridá nový token. */
void addToken(tokenSequence & tokens, token & newToken) {
    assert(tokens.length < tokens.size);
    tokens.items[tokens.length] = newToken;
    tokens.length++;
}

/** Funkcia odalokuje pamäť alokovanú pre postupnosť tokenov */
void destroy(tokenSequence & tokens) {
    delete[] tokens.items;
}

/** Funkcia vypíše postupnosť tokenov, každý v hranatých zátvorkách. */
void printTokens(tokenSequence & tokens) {
    for (int i = 0; i < tokens.length; i++) {
        token curToken = tokens.items[i];
        if (curToken.op == ' ') {
            printf(" [val %g]", curToken.val);
        } else {
            printf(" [op %c]", curToken.op);
        }
    }
    printf("\n");
}

/** Funkcia vypíše postupnosť tokenov ako aritmetický výraz. */
void printTokenExpression(tokenSequence & tokens) {
    for (int i = 0; i < tokens.length; i++) {
        token curToken = tokens.items[i];
        if (curToken.op == ' ') {
            printf(" %g", curToken.val);
        } else {
            printf(" %c", curToken.op);
        }
    }
    printf("\n");
}

/** Funkcia konvertuje výraz z reťazca na postupnosť tokenov. */
void tokenize(char * str, tokenSequence & tokens) {
    init(tokens, strlen(str));  // inicializujeme prázdnu postupnosť

    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);
            // vytvoríme a uložíme token
            token newToken = {' ', val};
            addToken(tokens, newToken);
            // preskočíme všetky znaky čísla
            strPos += skip;
        } else {
            // spracovanie zátvoriek alebo operátora
            assert(strchr("+-/*()~", str[strPos]) != NULL);
            // vytvoríme a uložíme token
            token newToken = {str[strPos], 0};
            addToken(tokens, newToken);
            strPos++;
        }
    }
}

// Nasleduje kód pre zásobník tokenov
typedef token 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 aplikuje operátor uložený v opToken na čísla
* uložené v num1 a num2, výsledok uloží ako číslo do result.
* Unárny operátor sa aplikuje iba na num1. */
void applyOp(token opToken, token num1, token num2, token & result) {    
    result.op = ' ';
    switch (opToken.op) {
    case '~':
        result.val = -num1.val;
        break;
    case '+':
        result.val = num1.val + num2.val;
        break;
    case '-':
        result.val = num1.val - num2.val;
        break;
    case '*':
        result.val = num1.val * num2.val;
        break;
    case '/':
        result.val = num1.val / num2.val;
        break;
    default: // iné operátory nepovoľujeme.
        assert(false);
    }
}

/** 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;
}

/** Pomocná funkcia, ktorá vráti prioritu operátora.
* Argument right určuje, či ide o pravý z dvoch porovnávaných operátorov */
int priority(char op, bool right) {
    if (op == '#' || op == '(') return 0;
    if (op == '-' || op == '+') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '~' && !right) return 3;
    if (op == '~' && right) return 4;
    assert(false); // sem by sme sa nemali dostať
}

/** Skonvertuje infixový výraz infix do postfixovej formy */
void infixToPostfix(tokenSequence & infix, tokenSequence & postfix) {
    // inicializuje výslednú postupnosť tokenov
    init(postfix, infix.length);

    // vytvoríme zásobník operátorov a na spodok dáme #
    stack opStack;
    init(opStack);
    token curToken = {'#', 0};
    push(opStack, curToken);

    for (int i = 0; i < infix.length; i++) {
        // aktuálny token zo vstupu
        curToken = infix.items[i];
        if (curToken.op == ' ') {
            // čísla rovno skopírujeme do výstupu
            addToken(postfix, curToken);
        } else if (curToken.op == '(') {
            // začiatok zátvorky uložíme na zásobník
            push(opStack, curToken);
        } else if (curToken.op == ')') {
            // koniec zátvorky:
            // na výstup pridáme zo zásobníka operátory,
            // ktoré boli v zátvorke
            token popped = pop(opStack);
            while (popped.op != '(') {
                addToken(postfix, popped);
                popped = pop(opStack);
            }
        } else {
            // spracovanie operátora:
            // na výstup pridáme zo zásobníka operátory s vyššou prioritou
            int p = priority(curToken.op, true);
            while (priority(peek(opStack).op, false) >= p) {
                token popped = pop(opStack);
                addToken(postfix, popped);
            }
            // aktuálny operátor dáme na zásobník
            push(opStack, curToken);
        }
    }

    // zvyšné operátory presunieme zo zásobníka na výstup
    while (peek(opStack).op != '#') {
        token popped = pop(opStack);
        addToken(postfix, popped);
    }
    destroy(opStack);
}

/** Pomocná funkcia, ktorá zo zásobníka vyberie
* jedno alebo dve čísla, aplikuje na nich operátor a výsledok uloží na zásobník. */
void processOp(stack & numberStack, token curToken) {
    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);
}

/** Spočíta hodnotu výrau v infixovej forme,
 * kombinuje infixToPostfix a evaluatePostfix */
double evaluateInfix(tokenSequence & infix) {
    // zásobník, do ktorého ukladáme čísla
    stack numberStack;
    init(numberStack);

    // vytvoríme zásobník operátorov a na spodok dáme #
    stack opStack;
    init(opStack);
    token curToken = {'#', 0};
    push(opStack, curToken);

    for (int i = 0; i < infix.length; i++) {
        // aktuálny token zo vstupu
        curToken = infix.items[i];
        if (curToken.op == ' ') {
            // čísla ukladáme na zásobník
            push(numberStack, curToken);
        } else if (curToken.op == '(') {
            // začiatok zátvorky uložíme na zásobník
            push(opStack, curToken);
        } else if (curToken.op == ')') {
            // koniec zátvorky:
            // spracujeme zo zásobníka operátory,
            // ktoré boli v zátvorke
            token popped = pop(opStack);
            while (popped.op != '(') {
                processOp(numberStack, popped);
                popped = pop(opStack);
            }
        } else {
            // spracovanie operátora:
            // spracujeme zo zásobníka operátory s vyššou prioritou
            int p = priority(curToken.op, true);
            while (priority(peek(opStack).op, false) >= p) {
                token popped = pop(opStack);
                processOp(numberStack, popped);
            }
            // aktuálny operátor dáme na zásobník
            push(opStack, curToken);
        }
    }

    // spracujeme zvyšné operátory zo zásobníka
    while (peek(opStack).op != '#') {
        token popped = pop(opStack);
        processOp(numberStack, popped);
    }
    destroy(opStack);

    // zo zásobníka vyberieme výsledné číslo
    token result = pop(numberStack);
    // skontrolujeme, že ásobník je prázdny a výsledok je číslo
    assert(isEmpty(numberStack) && result.op == ' ');
    // uvoľníme pamäť zásobníka čísel
    destroy(numberStack);
    return result.val;
}

/** Pomocná funkcia, ktorá vráti, či token je koncom operandu v infixovej notácii */
bool isOperand(token curToken) {
    return curToken.op == ' ' || curToken.op == ')';
}

/** Funkcia, ktorá v infixovom výraze zmení unárne mínus na ~ */
void fixUnaryMinus(tokenSequence &infix) {
    for (int i = 0; i < infix.length; i++) {
        if(infix.items[i].op=='-' 
           && (i==0 || !isOperand(infix.items[i-1]))) {
            infix.items[i].op = '~';
        }
    }
}

/** Hlavný program načítava a vykonáva postupnosť príkazov tokenize, postfix, infix a end. 
 * Príkaz tokenize tokenizuje a vypíše vstupný výraz. 
 * Príkaz postfix načíta výraz v postfixovom formáte a vypíše jeho hodnotu. 
 * Príkaz infix načíta výraz v infixovom formáte, upraví v ňom unárne - na ~.
 * prevedie ho do postfixového formátu, vyhodnotí postfixový výraz a naopokon
 * vyhodnotí aj priamo infixovú formu výrazu.  */
int main() {
    const int maxLine = 100;
    char command[maxLine];
    char expression[maxLine];

    while (true) {
        int ret = scanf("%s", command);
        if (ret < 1 || strcmp(command, "end") == 0) {
            break;
        } else if (strcmp(command, "tokenize") == 0) {
            fgets(expression, maxLine, stdin);
            tokenSequence tokens;
            tokenize(expression, tokens);
            printf(" tokens:");
            printTokens(tokens);
            destroy(tokens);
        } else if (strcmp(command, "postfix") == 0) {
            fgets(expression, maxLine, stdin);
            tokenSequence postfix;
            tokenize(expression, postfix);
            double value = evaluatePostfix(postfix);
            printf(" value: %g\n", value);
            destroy(postfix);
        }
        if (strcmp(command, "infix") == 0) {
            fgets(expression, maxLine, stdin);
            tokenSequence infix;
            tokenize(expression, infix);
            fixUnaryMinus(infix);
            printf(" infix:");
            printTokenExpression(infix);
            tokenSequence postfix;
            infixToPostfix(infix, postfix);
            printf(" postfix:");
            printTokenExpression(postfix);
            double value = evaluatePostfix(postfix);
            printf(" value of postfix: %g\n", value);
            double value2 = evaluateInfix(infix);
            printf(" value of infix: %g\n", value2);
            destroy(infix);
            destroy(postfix);
        }
    }
}