Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 19
Verzia z 17:32, 26. november 2023, ktorú vytvoril Brona (diskusia | príspevky) (→Prevod výrazu z infixovej do postfixovej notácie)
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.
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);
}
}
}
