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, čo 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 infoxových várazoch budú unárne mínus automaticky rozpoznané a nahradené ~.

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.

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; 
    if (op == '-' || op == '+') return 1;
    if (op == '*' || op == '/') return 2;
    assert(false); // sem by sme sa nemali dostat    
}

/* Skonvertuje infixovy vyraz infix 
 * do 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 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;
}

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) {
    // kontrola, že num1 a num2 sú čísla
    assert(num1.op == ' ' && num2.op == ' ');
    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++) {
        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 á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);
        num2 = num1;
    } 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);
        }
    }
}