Prednáška 19

Oznamy

• Na budúci týždeň bude semestrálna písomka.
• Tretiu domácu úlohu treba odovzdať do 6. decembra, 22:00.
• V piatok budú doplnkové cvičenia, online.

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ť. Postfixová a prefixová notácia majú oproti infixovej notácii ešte jednu výhodu – nepotrebujú zátvorky.

Nevýhodou naopak je, že tieto notácie nie sú konštruované na používanie unárneho operátora -. Ľahko napríklad vidieť, že prefixový výraz - - 2 3 by mohol zodpovedať ako výrazu -2 - 3, tak aj výrazu -(2 - 3). V nasledujúcom teda budeme predpokladať, že výrazy neobsahujú unárne mínus. Tento nedostatok nie je nijak závažný – každý infixový podvýraz typu -cokolvek možno totiž ekvivalentne prepísať ako (0 - 1) * cokolvek. (Alternatívne by sme v prefixových a postfixových výrazoch mohli pre unárne mínus zaviesť nejaký nový symbol.)

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 notácie do postfixovej

Oveľa zaujímavejšou a dôležitejšou úlohou, než vyhodnocovanie postfixových výrazov, je vyhodnocovanie výrazov v klasickej infixovej notácii. V nasledujúcom túto úlohu vyriešime tým, že napíšeme program realizujúci prevod aritmetického výrazu z infixovej notácie do postfixovej. Výraz v infixovej notácii teda budeme môcť vyhodnotiť tak, že ho najprv prevedieme do postfixovej notácie a tento postfixový výraz následne vyhodnotíme algoritmom popísaným vyššie. (Elegantnejšie prístupy k vyhodnocovaniu aritmetických výrazov vyžadujú istú dávku teórie, s ktorou sa typický študent informatiky zoznámi vo vyšších ročníkoch štúdia.)

Algoritmus pre infixové výrazy neobsahujúce unárne mínus

Začneme tým, že prevod do postfixovej notácie realizujeme pre infixové výrazy neobsahujúce unárny operátor mínus – ako sme už totiž videli, prítomnosť unárneho mínusu vo výslednom postfixovom výraze by mohla viesť k nejednoznačnostiam.

Uvažujme najprv výrazy bez zátvoriek. Tie pozostávajú z čísel a binárnych operátorov +, -, *, /, kde * a / majú vyššiu prioritu (precedenciu) ako + a -. Všetky tieto operátory sú navyše zľava asociatívne. 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íku.
  • 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.
  • Podobnú činnosť treba vykonať aj na konci vstupného reťazca – v takom prípade musíme vypísať všetky operátory 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:

Krok     Vstupný symbol     Výstupný reťazec     Zásobník (dno naľavo)      
------------------------------------------------------------------------------------------------------------------------
   1                  1                          #                         vypíš číslo 1 na výstup 
                            1                    #
   2                  +     1                    #                         # má nižšiu prioritu ako +, nevyberaj ho
                      +     1                    #                         vlož + na zásobník
                            1                    # + 
   3                  2     1                    # +                       vypíš číslo 2 na výstup
                            1 2                  # + 
   4                  +     1 2                  # +                       + má rovnakú prioritu ako +, vyber ho a vypíš
                      +     1 2 +                #                         # má nižšiu prioritu ako +, nevyberaj ho
                      +     1 2 +                #                         vlož + na zásobník
                            1 2 +                # +   
   5                  3     1 2 +                # +                       vypíš číslo 3 na výstup
                            1 2 + 3              # + 
   6                  *     1 2 + 3              # +                       + má nižšiu prioritu ako *, nevyberaj ho
                      *     1 2 + 3              # +                       vlož * na zásobník
                            1 2 + 3              # + *     
   7                  4     1 2 + 3              # + *                     vypíš číslo 4 na výstup
                            1 2 + 3 4            # + *                     
   8                  -     1 2 + 3 4            # + *                     * má vyššiu prioritu ako -, vyber ho a vypíš
                      -     1 2 + 3 4 *          # +                       + má rovnakú prioritu ako -, vyber ho a vypíš
                      -     1 2 + 3 4 * +        #                         # má nižšiu prioritu ako -, nevyberaj ho
                      -     1 2 + 3 4 * +        #                         vlož - na zásobník
                            1 2 + 3 4 * +        # -             
   9                  5     1 2 + 3 4 * +        # -                       vypíš číslo 5 na výstup
                            1 2 + 3 4 * + 5      # -                 
  10    [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:

• Zakaždým, 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ž majú 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ď naopak narazíme na pravú zátvorku, potrebujeme vypísať všetky doposiaľ nevypísané operátory uzatvorené touto zátvorkou. Preto v takom prípade 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).

Funkcia infixToPostfix, realizujúca prevod z infixovej do postfixovej notácie, tak môže vyzerať napríklad nasledovne:

#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) {
    switch (op) {
        case '#':
        case '(':
            return 0;
            break;
        case '+':
        case '-':
            return 1;
            break;
        case '*':
        case '/':
            return 2;
            break;
    }
    return -1;  // specialne pre biele znaky vrati -1
}

/* 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];
        } 
        switch (infix[i]) {
            case '(':
                push(s, '(');
                break;
            case ')': 
                char c;
                while ((c = pop(s)) != '(') {
                    postfix[j++] = ' '; 
                    postfix[j++] = c;
                }
                break;
            default:
                int p = precedence(infix[i]);
                if (p == -1) {                      // predovsetkym biele znaky
                    break;
                }
                postfix[j++] = ' ';
                while (p <= precedence(peek(s))) {
                    postfix[j++] = pop(s);
                    postfix[j++] = ' ';
                }
                push(s, infix[i]);
                break;
        }
    }
    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(void) {
    char infix[maxN];
    char postfix[2 * maxN];
    
    fgets(infix, maxN, stdin);
    infixToPostfix(infix, postfix);
    
    printf("Postfixovy tvar vyrazu: %s\n", postfix);
    
    return 0;
}

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 narozdiel od operácií +, -, *, / sprava asociatívne).

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

Pri prevode infixového výrazu do postfixového tvaru sme predpokladali, že neobsahuje žiadny výskyt unárneho operátora -. V nasledujúcom tento nedostatok napravíme: napíšeme funkciu normalise, ktorá v danom infixovom výraze in 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 pritom v korektnom infixovom výraze unárny práve vtedy, keď (modulo biele znaky, ktoré budeme ignorovať) nenasleduje za číslom, ani za pravou zátvorkou.

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

Prevod infixového výrazu s unárnymi mínusmi do postfixového tvaru teda môžeme realizovať tak, že najprv zavoláme funkciu normalise a následne funkciu infixToPostfix. (O niečo krajším riešením by bolo nahradenie unárnych mínusov nejakým novým špeciálnym znakom – v takom prípade by sa však musela zmeniť aj funkcia infixToPostfix.) Následne môžeme výsledný výraz aj vyhodnotiť pomocou funkcie evaluatePostfix.

const int maxN = 100;

int main(void) {
    char infix1[maxN];
    char infix2[6 * maxN];
    char postfix[12 * maxN];
    
    fgets(infix1, maxN, stdin);
  
    normalise(infix1, infix2);
    printf("Vyraz po odstraneni unarnych minusov: %s\n", infix2);
    
    infixToPostfix(infix2, postfix);
    printf("Vyraz v postfixovom tvare: %s\n", postfix);
    
    printf("Hodnota vyrazu: %f\n", evaluatePostfix(postfix));
    
    return 0;
}

Pri implementácii uvedeného programu sa však treba mať na pozore: kým totiž funkcia evaluatePostfix využíva zásobník prvkov typu double, funkcia infixToPostfix využíva zásobník prvkov typu char. Pri pokuse o skopírovanie kódu pre zásobník do zdrojového súboru tohto programu tak stojíme pred voľbou medzi

typedef char dataType;

a

typedef double dataType;

V tomto prípade ešte môžeme zvoliť druhú možnosť a za dataType považovať double; o zvyšok sa postará automatické pretypovanie znakov (čiže špeciálnych celých čísel) na reálne čísla a naopak. Toto riešenie má však ďaleko od ideálneho a pre iné dvojice typov nemusí riešenie tohto druhu existovať vôbec. (Ozaj elegantný prístup k tomuto problému vyžaduje pokročilejšie programátorské techniky z letného semestra.)