Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 19
Obsah
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.
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?
Technické poznámky:
- 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 čislo vyhodnocovanie postfixovej notácie, stačil by nám zásobník s prvkami typu double.
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++) {
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 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) { 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 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); } } }