Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 20
Verzia z 13:47, 27. november 2023, ktorú vytvoril Brona (diskusia | príspevky) (→Príklad: plné binárne stromy)
Obsah
Oznamy
- Oznamy z pondelka
Prednášky
- Tento týždeň a budúci pondelok ešte prednášky v normálnom režime.
- Budúcu stredu 6.12. v prvej polovici prednášky informácie k skúške a rady k skúškovému všeobecne, potom doberieme posledné povinné učivo.
- Posledný týždeň semestra v pondelok 11.12. nepovinná prednáška o nepreberaných črtách jazykov C a C++, v stredu 13.12. prednáška pravdepodobne nebude.
Cvičenia a úlohy
- Cvičenia bežia normálne každý utorok, piatkové cvičenia už iba 2x.
- Ak ste na cvičení nezískali 5 bodov, sú pre vás povinné cvičenia v piatok. Dobrá príležitosť spýtať sa na nejasné veci v cvičeniach, prednáškach, domácej úlohe. Môžete aj trénovať prvý príklad zo skúšky.
- Budúci utorok bude teoretická rozcvička na papieri.
- Tretiu domácu úlohu treba odovzdať do budúceho utorka 5.12. 22:00.
Semestrálny test
- V stredu 13.12. o 18:10.
- 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
- Môžete si pozrieť aj ukážkový test pre pokročilých, ktorý má podobné typy príkladov ako semestrálny test.
Termíny skúšok
- Piatok 15.12. 13:10
- Piatok 12.1. 9:00
- Piatok 19.1. 9:00
- Piatok 26.1. 9:00, hlavne 1. opravný termín
- Piatok 9.2. 9:00, hlavne 2. opravný termín
Na termíny sa bude dať prihlasovať od dnes 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.
- Decembrový termín odporúčame hlavne študentom, ktorým programovanie nerobí problémy.
- Viac informácií o skúške je na stránke Zimný semester, skúška, spolu cez to prejdeme budúcu stredu.
- Na testovač tento týždeň pridáme zopár tréningových príkladov na skúšku.
Opakovanie z minulej prednášky
Aritmetické výrazy
- Bežná infixová notácia, napr. (65 – 3*5)/(2 + 3)
- Postfixová notácia 65 3 5 * - 2 3 + /
- Prefixová notácia / - 65 * 3 5 + 2 3
- Prefixová a postfixová notácia nepotrebujú zátvorky
- Prevod z infixovej notácie na postfixovú pomocou zásobníka
- Čo si ukladáme do zásobníka?
- Vyhodnocovanie postfixovej notácie pomocou zásobníka
- Čo si ukladáme do zásobníka?
Aritmetický výraz ako strom
Aritmetické výrazy možno reprezentovať aj vo forme stromu
- Operátory a čísla tvoria tzv. uzly (alebo vrcholy) stromu.
- Operátory tvoria tzv. vnútorné uzly stromu, každý z nich má dve deti zodpovedajúce podvýrazom pre jednotlivé operandy.
- Čísla tvoria tzv. listy stromu, tie už nemajú žiadne deti.
- Strom obsahuje jediný uzol, ktorý nemá rodiča. Tento sa nazýva koreň stromu a reprezentuje celý aritmetický výraz.
- Informatici stromy väčšinou kreslia „hore nohami”, s koreňom na vrchu.
Uzol takéhto stromu tak môžeme reprezentovať napríklad nasledujúcou štruktúrou:
struct treeNode {
// ciselna hodnota (zmysluplna len v listoch)
double val;
// operator vo vnutornych uzloch, pre listy rovny medzere
char op;
// smernik na koren podstromu reprezentujuceho lavy podvyraz
// alebo NULL v liste
treeNode *left;
// smernik na koren podstromu reprezentujuceho pravy podvyraz
// alebo NULL v liste
treeNode *right;
};
Pre vnútorné uzly stromu (zodpovedajúce operátorom) pritom:
- Smerníky left a right budú ukazovať na korene podstromov reprezentujúcich ľavý resp. pravý podvýraz.
- Znak op bude zodpovedať danému operátoru (napríklad '+').
- Hodnota val ostane nevyužitá.
Pre listy (zodpovedajúce číselným hodnotám) naopak:
- Smerníky left a right budú mať hodnotu NULL.
- Znak op bude medzera ' ' (podľa op teda môžeme rozlišovať, či ide o číslo alebo o operátor).
- Vo val bude uložená hodnota daného čísla.
Celý strom pritom budeme reprezentovať jeho koreňom.
V tejto reprezentácii sú niektoré položky štruktúry treeNode nevyužité (napr. val vo vnútorných vrcholoch). S využitím objektového programovania (letný semester) budeme vedieť stromy pre aritmetické výrazy reprezentovať elegantnejšie.
Vytvorenie uzlu
Nasledujúce funkcie vytvoria nový vnútorný uzol (pre operátor) resp. nový list (pre číslo):
treeNode *createOp(char op, treeNode *left, treeNode *right) {
treeNode *v = new treeNode;
v->left = left;
v->right = right;
v->op = op;
return v;
}
treeNode *createNum(double val) {
treeNode *v = new treeNode;
v->left = NULL;
v->right = NULL;
v->op = ' ';
v->val = val;
return v;
}
„Ručne” teraz môžeme vytvoriť strom pre výraz (65 – 3 * 5)/(2 + 3):
treeNode *root = createOp('/',
createOp('-',
createNum(65),
createOp('*', createNum(3), createNum(5))),
createOp('+', createNum(2), createNum(3)));
Alebo po častiach:
treeNode *v65 = createNum(65);
treeNode *v3 = createNum(3);
treeNode *v5 = createNum(5);
treeNode *v2 = createNum(2);
treeNode *v3b = createNum(3);
treeNode *vKrat = createOp('*', v3, v5);
treeNode *vMinus = createOp('-', v65, vKrat);
treeNode *vPlus = createOp('+', v2, v3b);
treeNode *vDeleno = createOp('/', vMinus, vPlus);
Vyhodnotenie výrazu reprezentovaného stromom
Nasledujúca rekurzívna funkcia vypočíta hodnotu aritmetického výrazu reprezentovaného stromom s koreňom root.
- Ak je zadaný vrchol listom, vrátime hodnotu uloženú v položke val.
- V opačnom prípade rekurzívne spočítame hodnoty pre obidva podvýrazy a skombinujeme ich podľa typu znamienka.
- Celkovo veľmi jednoduchý a prirodzený výpočet, nie je potrebný explicitný zásobník.
- Funkcia nižšie nefunguje pre unárne mínus, nebolo by však ťažké ho dorobiť.
Rekurziu budeme používať vždy, keď potrebujeme prejsť všetky uzly stromu. Cyklom sa to programuje ťažko, lebo z uzla potrebujeme ísť doľava aj doprava.
double evaluateTree(treeNode *root) {
assert(root != NULL);
if (root->op == ' ') {
return root->val;
} else {
double valLeft = evaluateTree(root->left);
double valRight = evaluateTree(root->right);
switch (root->op) {
case '+':
return valLeft + valRight;
break;
case '-':
return valLeft - valRight;
break;
case '*':
return valLeft * valRight;
break;
case '/':
return valLeft / valRight;
break;
default:
assert(false);
break;
}
}
return 0; // realne nedosiahnutelny prikaz
}
Uvoľnenie pamäte
Nasledujúca funkcia uvoľní z pamäte celý strom s koreňom root
- Opäť používa rekurziu na prejdenie celého stromu
- Pozor na poradie príkazov, treba najskôr uvoľniť podstromy až potom zavolať delete na root, inak by sme stratili prístup k deťom.
- Všimnite si, ako sú riešené triviálne prípady, funkcia ani nezisťuje, s akým typom uzla pracuje.
void destroyTree(treeNode *root) {
if (root != NULL) {
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
}
Vypísanie výrazu reprezentovaného stromom v rôznych notáciách
Infixovú, prefixovú, resp. postfixovú reprezentáciu aritmetického výrazu reprezentovaného stromom s koreňom root možno získať pomocou nasledujúcich funkcií.
- Opäť používajú rekurziu na prejdenie celého stromu.
- Líšia sa hlavne umiestnením príkazu na vypísanie operátora (pred, medzi alebo za rekurzívnym vypísaním podvýrazov).
- Infixová notácia potrebuje aj zátvorky. Táto funkcia ich pre istotu dáva všade. Rozmyslite si, ako by sme ich vedeli vypísať iba tam, kde treba.
void printInorder(FILE *fw, treeNode *root) {
if (root->op == ' ') {
fprintf(fw, "%.2f", root->val);
} else {
fprintf(fw, "(");
printInorder(fw, root->left);
fprintf(fw, " %c ", root->op);
printInorder(fw, root->right);
fprintf(fw, ")");
}
}
void printPreorder(FILE *fw, treeNode *root) {
if (root->op == ' ') {
fprintf(fw, "%.2f ", root->val);
} else {
fprintf(fw, "%c ", root->op);
printPreorder(fw, root->left);
printPreorder(fw, root->right);
}
}
void printPostorder(FILE *fw, treeNode *root) {
if (root->op == ' ') {
fprintf(fw, "%.2f ", root->val);
} else {
printPostorder(fw, root->left);
printPostorder(fw, root->right);
fprintf(fw, "%c ", root->op);
}
}
Vytvorenie stromu z postfixového výrazu
Pripomeňme si z minulej prednášky funkciu na vyhodnocovanie postfixového výrazu:
/** 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;
}
Túto funkciu možno jednoducho prepísať tak, aby namiesto vyhodnocovania výrazu konštruovala zodpovedajúci aritmetický strom. Namiesto hodnôt jednotlivých podvýrazov stačí na zásobníku uchovávať korene stromov, ktoré tieto podvýrazy reprezentujú. Aplikácii aritmetickej operácie potom bude zodpovedať spojenie dvoch podstromov do jedného stromu:
typedef treeNode *dataType;
/* Sem príde definícia štruktúry pre zásobník a všetkých funkcií poskytovaných zásobníkom. */
treeNode * postfixToTree(tokenSequence & tokens) {
// zásobník, do ktorého ukladáme korene podstromov
stack treeStack;
init(treeStack);
for (int i = 0; i < tokens.length; i++) {
// aktuálny token zo vstupu
token curToken = tokens.items[i];
if (curToken.op == ' ') {
// čísla ukladáme na zásobník ako listy stromu
push(treeStack, createNum(curToken.val));
} else {
// spracovanie operátora
treeNode * left, * right;
// vyberieme 1 alebo 2 podstromy zo zásobníka
// vytvoríme nový koreň, ktorý bude ich rodičom a vložíme na zásobník
if (curToken.op == '~') {
left = pop(treeStack);
push(treeStack, createOp(curToken.op, left, NULL));
} else {
right = pop(treeStack);
left = pop(treeStack);
push(treeStack, createOp(curToken.op, left, right));
}
}
}
// zo zásobníka vyberieme výsledný strom
treeNode * result = pop(treeStack);
// skontrolujeme, že zásobník je prázdny
assert(isEmpty(treeStack));
// uvoľníme pamäť zásobníka
destroy(treeStack);
return result;
}
Ukážkový program pracujúci so stromami pre aritmetické výrazy
Nasledujúci program prečíta z konzoly aritmetický výraz v postfixovom tvare, skonštruuje jeho aritmetický strom a následne preň zavolá funkcie na výpočet hodnoty výrazu a jeho výpis v rôznych notáciách:
int main(void) {
char expr[100];
fgets(expr, 100, stdin);
treeNode *root = parsePostfix(expr);
printf("Hodnota vyrazu je: %.2f\n", evaluateTree(root));
printf("Vyraz v infixovej notacii: ");
printInorder(stdout, root);
printf("\n");
printf("Vyraz v prefixovej notacii: ");
printPreorder(stdout, root);
printf("\n");
printf("Vyraz v postfixovej notacii: ");
printPostorder(stdout, root);
printf("\n");
destroyTree(root);
}
Binárne stromy
Stromy pre aritmetické výrazy sú špeciálnym prípadom binárnych stromov. V informatike majú binárne stromy množstvo rozličných uplatnení. Ukážeme si teda všeobecnú dátovú štruktúru binárneho stromu.
Terminológia stromov
- Strom obsahuje množinu uzlov alebo vrcholov prepojených hranami. (uzol angl. node, vrchol vertex, hrana edge).
- Ak je strom neprázdny, jeden jeho vrchol nazývame koreň (angl. root)
- Každý uzol u okrem koreňa je spojený hranou s práve jedným rodičom (angl. parent), ktorým je nejaký uzol v. Naopak uzol u je dieťaťom (angl. child) uzla v.
- Vo všeobecnom strome môže mať každý uzol ľubovoľný počet detí (aj nula)
- Strom je binárny, ak má každý uzol najviac dve deti. Budeme pritom rozlišovať medzi pravým a ľavým dieťaťom.
- Uzly zakoreneného stromu, ktoré nemajú žiadne dieťa, nazývame listami; zvyšné uzly potom nazývame vnútornými uzlami.
- Predkom uzla u nazveme ľubovoľný uzol v ležiaci na ceste z u do koreňa stromu (vrátane u a koreňa). Naopak potom hovoríme, že u je potomkom uzla v.
- Podstromom stromu T zakoreneným v nejakom uzle v stromu T budeme rozumieť strom s koreňom v pozostávajúci zo všetkých jeho potomkov a všetkých hrán stromu T vedúcich medzi týmito uzlami.
Každý binárny strom je teda buď prázdny, alebo je tvorený jeho koreňom a dvoma podstromami – ľavým a pravým.
Takéto stromy sa nazývajú zakorenené. Presnejšiu matematickú definíciu zakorenených aj nezakorenených stromov uvidíte na predmete Úvod do kombinatoriky a teórie grafov (letný semester).
Štruktúra pre uzol binárneho stromu
V nasledujúcom budeme pracovať výhradne s binárnymi stromami. Štruktúra pre uzol všeobecného binárneho stromu je podobná, ako pri stromoch pre aritmetické výrazy, namiesto operátora alebo hodnoty si však v každom uzle budeme pamätať hodnotu ľubovoľného typu dataType. V nasledujúcej definícii je tento typ int.
/* Typ prvkov ukladanych v uzloch binarneho stromu */
typedef int dataType;
/* Uzol binarneho stromu */
struct node {
// hodnota ulozena v uzle
dataType data;
// smernik na lave dieta (NULL, ak dieta neexistuje)
node *left;
// smernik na prave dieta (NULL, ak dieta neexistuje)
node *right;
};
Vytvorenie binárneho stromu
Nasledujúca funkcia vytvorí uzol binárneho stromu s dátami data, ľavým podstromom zakoreneným v uzle *left a pravým podstromom zakoreneným v uzle *right (parametre left a right sú teda smerníkmi na uzly). Ako výstup funkcia vráti smerník na novovytvorený uzol.
/* Vytvori uzol binarneho stromu */
node *createNode(dataType data, node *left, node *right) {
node *v = new node;
v->data = data;
v->left = left;
v->right = right;
return v;
}
Nasledujúca volanie tak napríklad vytvorí binárny strom so šiestimi uzlami zakorenený v uzle *root.
node *root = createNode(1,
createNode(2,
createNode(3, NULL, NULL),
createNode(4,NULL,NULL)),
createNode(5,
NULL,
createNode(6, NULL, NULL)));
Cvičenie: nakreslite binárny strom vytvorený predchádzajúcim volaním.
Prehľadávanie stromov a vypisovanie ich uzlov
Často je potrebné prejsť celý strom a spracovať (napríklad vypísať) hodnoty vo všetkých uzloch. Toto prehľadávanie možno, podobne ako pri stromoch pre výrazy, realizovať v troch základných poradiach: preorder, inorder a postorder.
Pri vypisovaní predpokladáme, že pre hodnoty typu dataType máme k dispozícii funkciu printDataType, ktorá ich v nejakom vhodnom formáte vypisuje.
/* Funkcia pre vypis hodnoty typu dataType */
void printDataType(dataType data) {
printf("%d ", data); // pre int
}
/* Vypise podstrom s korenom *root v poradi preorder */
void printPreorder(node *root) {
if (root == NULL) {
return;
}
printDataType(root->data);
printPreorder(root->left);
printPreorder(root->right);
}
/* Vypise podstrom s korenom *root v poradi inorder */
void printInorder(node *root) {
if (root == NULL) {
return;
}
printInorder(root->left);
printDataType(root->data);
printInorder(root->right);
}
/* Vypise podstrom s korenom *root v poradi postorder */
void printPostorder(node *root) {
if (root == NULL) {
return;
}
printPostorder(root->left);
printPostorder(root->right);
printDataType(root->data);
}
Cvičenie: ako by sme spočítali súčet hodnôt uložených v uzloch stromu?
Likvidácia binárneho stromu
Nasledujúca rekurzívna funkcia zlikviduje celý podstrom zakorenený v uzle *root (t. j. uvoľní pamäť pre všetky jeho uzly). Veľmi sa podobá na funkciu pre strom reprezentujúci aritmetický výraz.
/* Zlikviduje podstrom s korenom *root (uvolni pamat) */
void destroyTree(node *root) {
if (root != NULL) {
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
}
Výška binárneho stromu
Hĺbkou uzla binárneho stromu nazveme jeho vzdialenosť od koreňa. Koreň má teda hĺbku 0, jeho deti majú hĺbku 1, atď. Výškou binárneho stromu potom nazveme maximálnu hĺbku niektorého z jeho vrcholov. Strom s jediným vrcholom má teda hĺbku 0; pre ostatné stromy je ich výška daná ako 1 plus maximum z výšok ľavého a pravého podstromu.
Nasledujúca funkcia počíta výšku stromu (kvôli elegancii zápisu pritom pracuje s rozšírením definície výšky stromu na prázdne stromy, za ktorých výšku sa považuje číslo -1).
/* Spocita vysku podstromu s korenom *root. Pre root == NULL vrati -1. */
int height(node *root) {
if (root == NULL) {
return -1;
}
// rekurzivne spocita vysku laveho a praveho podstromu
int hLeft = height(root->left);
int hRight = height(root->right);
// vrati max(hLeft, hRight) + 1
if (hLeft >= hRight) {
return hLeft + 1;
} else {
return hRight + 1;
}
}
Cvičenie: prepíšte funkciu tak, aby triviálnym prípadom bol list, nie prázdny strom. Funkcia teda vždy dostane smerník na neprázdny strom a nebude volať rekurziu na prázdne podstromy. Ktorá verzia je jednoduchšia? Ktorá sa vám zdá jednoduchšia na pochopenie?
Aká môže byť výška binárneho stromu?
Pre výšku h binárneho stromu s n uzlami platia nasledujúce vzťahy:
- Určite h ≤ n-1. Tento prípad nastáva, ak sú všetky uzly „navešané jeden pod druhý”.
- Strom s výškou h má najviac
- uzlov (ako možno ľahko dokázať indukciou vzhľadom na h).
- Z toho h ≥ log2(n+1)-1.
- Dostávame teda log2(n+1)-1 ≤ h ≤ n-1.
- Napríklad strom s milión vrcholmi má teda hĺbku medzi 19 a 999999.
Príklad: plné binárne stromy
Binárny strom výšky h s maximálnym počtom vrcholov 2h+1-1 sa nazýva plný binárny strom. Nasledujúca funkcia createFullTree vytvorí takýto strom a vráti smerník na jeho koreň. Jeho uzly pritom očísľuje 1, 2, 3,... (predpokladáme, že dataType je int) pomocou globálnej premennej count.
// ...
int count;
/* Vytvori plny binarny strom vysky height s datami uzlov count, count + 1, ... */
node *createFullTree(int height) {
if (height == -1) {
return NULL;
}
node *v = createNode(count++, NULL, NULL);
v->left = createFullTree(height - 1);
v->right = createFullTree(height - 1);
return v;
}
int main() {
count = 1;
node *root = createFullTree(3);
printf("Vyska: %d\n", height(root));
printf("Inorder: ");
printInorder(root);
printf("\n");
printf("Preorder: ");
printPreorder(root);
printf("\n");
printf("Postorder: ");
printPostorder(root);
printf("\n");
destroyTree(root);
}
Cvičenie:
- Nakreslite strom aj s hodnotami v uzloch, ktorý vznikne pre výšku 2.
- Vo všeobecnosti opíšte poradie, v ktorom sa v uvedenom programe jednotlivým uzlom priraďujú ich hodnoty.
- Ako by ste v programe odstránili globálnu premennú count?
Program pre aritmetické výrazy ako stromy
#include <cstdio>
#include <cctype>
#include <cassert>
#include <cstring>
using namespace std;
struct treeNode {
// ciselna hodnota (zmysluplna len v listoch)
double val;
// operator vo vnutornych uzloch, pre listy rovny medzere
char op;
// smernik na koren podstromu reprezentujuceho lavy podvyraz
// alebo NULL v liste
treeNode * left;
// smernik na koren podstromu reprezentujuceho pravy podvyraz
// alebo NULL v liste
treeNode * right;
};
treeNode * createOp(char op, treeNode * left, treeNode * right) {
treeNode * v = new treeNode;
v->left = left;
v->right = right;
v->op = op;
return v;
}
treeNode * createNum(double val) {
treeNode * v = new treeNode;
v->left = NULL;
v->right = NULL;
v->op = ' ';
v->val = val;
return v;
}
/** Š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 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 uzlov stromu
typedef treeNode * 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 konvertuje výraz v postfixovom tvare na strom */
treeNode * postfixToTree(tokenSequence & tokens) {
// zásobník, do ktorého ukladáme korene podstromov
stack treeStack;
init(treeStack);
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(treeStack, createNum(curToken.val));
} else {
// spracovanie operátora
treeNode * left, * right;
// najskôr vyberieme 1 alebo 2 podstromy zo zásobníka
// vytvoríme nový koreň, ktorý bude ich rodičom a vložíme na zásobník
if (curToken.op == '~') {
left = pop(treeStack);
push(treeStack, createOp(curToken.op, left, NULL));
} else {
right = pop(treeStack);
left = pop(treeStack);
push(treeStack, createOp(curToken.op, left, right));
}
}
}
// zo zásobníka vyberieme výsledný strom
treeNode * result = pop(treeStack);
// skontrolujeme, že zásobník je prázdny
assert(isEmpty(treeStack));
// uvoľníme pamäť zásobníka
destroy(treeStack);
return result;
}
double evaluateTree(treeNode * root) {
assert(root != NULL);
if (root->op == ' ') {
return root->val;
} else {
double valLeft = evaluateTree(root->left);
double valRight = evaluateTree(root->right);
switch (root->op) {
case '+':
return valLeft + valRight;
break;
case '-':
return valLeft - valRight;
break;
case '*':
return valLeft * valRight;
break;
case '/':
return valLeft / valRight;
break;
default:
assert(false);
break;
}
}
return 0; // realne nedosiahnutelny prikaz
}
void destroyTree(treeNode * root) {
if (root != NULL) {
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
}
void printInorder(FILE * fw, treeNode * root) {
if (root->op == ' ') {
fprintf(fw, "%g", root->val);
} else {
fprintf(fw, "(");
printInorder(fw, root->left);
fprintf(fw, " %c ", root->op);
printInorder(fw, root->right);
fprintf(fw, ")");
}
}
void printPreorder(FILE * fw, treeNode * root) {
if (root->op == ' ') {
fprintf(fw, "%g ", root->val);
} else {
fprintf(fw, "%c ", root->op);
printPreorder(fw, root->left);
printPreorder(fw, root->right);
}
}
void printPostorder(FILE * fw, treeNode * root) {
if (root->op == ' ') {
fprintf(fw, "%g ", root->val);
} else {
printPostorder(fw, root->left);
printPostorder(fw, root->right);
fprintf(fw, "%c ", root->op);
}
}
int main() {
const int maxLine = 100;
char postfix[maxLine];
fgets(postfix, maxLine, stdin);
tokenSequence tokens;
tokenize(postfix, tokens);
treeNode * root = postfixToTree(tokens);
double value = evaluateTree(root);
printf(" value: %g\n", value);
printf(" inorder: ");
printInorder(stdout, root);
printf("\n predorder: ");
printPreorder(stdout, root);
printf("\n postdorder: ");
printPostorder(stdout, root);
printf("\n");
destroy(tokens);
destroyTree(root);
}
