Štruktúry (riešené príklady)
Obsah
Štruktúra Zlomok
Úloha:
Zostavte program, ktorý pomôže pri práci so zlomkami – bude vedieť zlomok skrátiť a vypísať ho v čo najvhodnejšom tvare. Program načíta dva zlomky, každý hneď po načítaní upravene vypíše, ďalej vypíše ich súčin, súčet a podiel:
- Zostavte funkciu na načítanie zlomku z klávesnice a funkciu, ktorá vypíše zlomok na obrazovku v tvare „a/b“, napr. „3/4“. Postupne ju zdokonaľujte:
- V prípade, že zlomok má celú časť, vypíše ho v tvare „a b/c“, napr. namiesto „9/4“ bude písať „2 1/4“.
- V prípade, že jeho zvyšná časť je nulová, nebude ju vypisovať, napr. namiesto „6/2“ nebude písať „3 0/2“, ale iba „3“ a podobne, namiesto „0/2“ iba „0“.
- Vytvorte si pomocnú funkciu, ktorá zjednoduší (skráti) zlomok, napr. „36/48“ prevedie na „3/4“ a obohaťte ňou funkciu pre vypísanie zlomku (aby sa zlomok vypisoval už v zjednodušenom tvare).
- Zostavte funkcie, ktoré vypočítajú súčin, súčet a podiel dvoch zlomkov a použite ich v hlavnom programe.
Vzorový vstup:
5 4 1 1/4 6 8 3/4
Vzorový výstup:
sucin: 15/16 sucet: 2 podiel: 1 2/3
Cieľom je precvičiť si prácu so štruktúrou – bolo by vhodné ju v programe využiť. Funkcia na načítanie zlomku môže využiť referenciu alebo štruktúru ako návratovú hodnotu. Pre krátenie zlomku môžeme využiť referenciu a pre matematické operácie so zlomkami zase návratovú hodnotu.
Pre krátenie zlomku treba funkciu na najväčší spoločný deliteľ – použijeme Euklidov algoritmus postupného odpočítavania menšieho čísla od väčšieho a jeho zdokonalenie cez operáciu modulo. Pri matematických funkciách môžeme využiť akýsi „akoby konštruktor“ na vytvorenie zlomku, no nie je to nutné.
Možné riešenie:
1 #include <iostream.h>
2 #include <conio.h>
3 struct TZlomok { int citatel, menovatel; };
4 void CitajZlomok(TZlomok &z)
5 {
6 cin >> z.citatel;
7 cin >> z.menovatel;
8 }
9
10 int NSD(int a, int b)
11 {
12 while (b)
13 {
14 int c = a % b;
15 a = b;
16 b = c;
17 }
18 return a;
19 }
20
21 void SkratZlomok(TZlomok &z)
22 {
23 int nsd = NSD(z.citatel, z.menovatel);
24 z.citatel /= nsd;
25 z.menovatel /= nsd;
26 }
27
28 void VypisZlomok(TZlomok z)
29 {
30 SkratZlomok(z);
31 int cela_cast = z.citatel / z.menovatel;
32 if (cela_cast)
33 {
34 cout << cela_cast;
35 int zvysok = z.citatel % z.menovatel;
36 if (zvysok) cout << " " << zvysok << "/" << z.menovatel;
37 }
38 else
39 {
40 cout << z.citatel;
41 if (z.citatel) // ak je nula, napise len ju a nie napr. 0/1
42 cout << "/" << z.menovatel;
43 }
44 cout << endl;
45 }
46
47 TZlomok Zlomok(int cit, int men)
48 {
49 TZlomok z;
50 z.citatel = cit;
51 z.menovatel = men;
52 SkratZlomok(z);
53 return z;
54 }
55
56 TZlomok SucinZlomkov(TZlomok z1, TZlomok z2)
57 {
58 return Zlomok(z1.citatel * z2.citatel, z1.menovatel * z2.menovatel);
59 }
60
61 TZlomok SucetZlomkov(TZlomok z1, TZlomok z2)
62 {
63 return Zlomok(z1.citatel * z2.menovatel + z2.citatel * z1.menovatel,
64 z1.menovatel * z2.menovatel);
65 }
66
67 TZlomok PodielZlomkov(TZlomok z1, TZlomok z2)
68 {
69 return Zlomok(z1.citatel * z2.menovatel, z1.menovatel * z2.citatel);
70 }
71
72 void main()
73 {
74 TZlomok z1, z2;
75 CitajZlomok(z1); VypisZlomok(z1);
76 CitajZlomok(z2); VypisZlomok(z2);
77 cout << "sucin: "; VypisZlomok(SucinZlomkov(z1, z2));
78 cout << "sucet: "; VypisZlomok(SucetZlomkov(z1, z2));
79 cout << "podiel: "; VypisZlomok(PodielZlomkov(z1, z2));
80 getch();
81 }
Zásobník - pamäť typu LIFO
Intepreter postfixových aritmetických výrazov
Zadanie:
Vytvorte program v jazyku C, ktorý po spustení načíta od používateľa postfixový aritmetický výraz, vyhodnotí ho, vypíše jeho hodnotu do konzoly (na monitor) a skončí.
Analýza:
V postfixovom aritmetickom výraze sa operátor zapisuje vždy po svojich dvoch operandoch, ako to môžeme vidieť v nasledujúcom takomto výraze
5 9 8 + 4 6 * * 7 + *
ktorý má hodnotu 2075. Každý infixový aritmetický výraz, môže byť prepísaný na postfixový. Infixová verzia uvedeného postfixového výrazu je nasledovná:
5 * ( ( (9 + 8) * (4 * 6) ) + 7)
a tá má samozrejme po vyhodnotení rovnakú hodnotu 2075.
Pomocou abstraktného dátového typu (ADT) zásobníka sa dajú veľmi dobre vyhodnocovať práve postfixové aritmetické výrazy. Každý operátor si z vrcholu zásobníka načíta svoje dva operandy a po vykonaní operácie na nich vráti jej výsledok namiesto týchto dvoch operandov na vrchol zásobníka (využitie princípu dátovej štruktúry typu LIFO). Nasledujúci obrázok demonštruje tento jednoduchý princíp na vyhodnocovaní vyššie uvedeného postfixového aritmetického výrazu.
| index v pamati zásobníka číslo kroku |
0 | 1 | 2 | 3 | 4 | operácia |
|---|---|---|---|---|---|---|
| 1 | 5 | |||||
| 2 | 5 | 9 | ||||
| 3 | 5 | 9 | 8 | |||
| 4 | 5 | 8+9 | ||||
| 5 | 5 | 17 | ||||
| 6 | 5 | 17 | 4 | |||
| 7 | 5 | 17 | 4 | 6 | ||
| 8 | 5 | 17 | 6 * 4 | |||
| 9 | 5 | 17 | 24 | |||
| 10 | 5 | 24*17 | ||||
| 11 | 5 | 408 | ||||
| 12 | 5 | 408 | 7 | |||
| 13 | 5 | 408 + 7 | ||||
| 14 | 5 | 415 | ||||
| 15 | 415 * 5 | |||||
| 16 | 2075 |
Tabuľka ukazuje použitie zásobníka reprezentovaného celočíselným poľom (zasobnik.pamat[ ]) pre vyhodnotenie postfixového výrazu 5 9 8 + 4 6 * * 7 + * uloženého v znakovom poli (vyraz[ ]). Tento výraz postupne prechádzame zľava doprava. Ak narazíme na znak reprezentujúci číslo, vložíme ho na vrchol zásobníka (zasobnik.pamat[zasobnik.vrchol]), ak narazíme na znak reprezentujúci operátor, potom vyberieme z vrcholu zásobníka 2 operandy, aplikujeme na ne operátor a namiesto týchto dvoch operandov vložíme na vrchol zásobníka výsledok samotnej operácie. Na reprezentáciu zásobníka použijeme štruktúru LIFO. Pre základné operácie so zásobníkom, vloženie položky na vrchol zásobníka a vybratie položky z jeho vrcholu, si vytvoríme dve funkcie:
stav zasobnika push(LIFO &zasobnik, int x);
int pop(LIFO &zasobnik);
Príklad vstupu do programu:
5 9 8 + 4 6 * * 7 + *
Príklad výstupu z programu:
2075
Možné riešenie:
1 #include<iostream>
2 #include <string.h>
3 using namespace std;
4
5 #define MAX_PAMAT 40
6
7 enum stav_zasobnika{OK=-1, FULL=INT_MAX, EMPTY=INT_MIN};
8
9 typedef struct {
10 double pamat[ MAX_PAMAT ];
11 int vrchol;
12 } LIFO;
13
14 /** pre ucely ladenia */
15 void show(LIFO &zasobnik){
16 cout<<"|";
17 for(int i=0; i<zasobnik.vrchol; i++) {
18 cout<<zasobnik.pamat[i]<<"|";
19 }
20 cout<<endl;
21 }
22
23 //VLOZI novu polozku 'x' do pola 'zasobnik.pamat' (do zasobnika) a zvacsi indexovu premennu //'zasobnik.vrchol' o 1
24 stav_fronty push(LIFO &zasobnik,double x) {
25
26 if(zasobnik.vrchol<MAX_PAMAT)
27 zasobnik.pamat[zasobnik.vrchol++]=x;
28 else
29 return FULL;
30 return OK;
31 }
32
33 //zmensi indexovu premennu 'zasobnik.vrchol' o 1 a VYBERIE poslednu vlozenu polozku z pola //'zasobnik.pamat' (zo zasobnika)
34 double pop(LIFO &zasobnik) {
35 if(zasobnik.vrchol>0)
36 return zasobnik.pamat[--zasobnik.vrchol];
37 else
38 return EMPTY;
39 }
40
41 int main()
42 {
43 LIFO f; //deklaracia strukturovej premennej typu 'LIFO' reprezentujucej zasobnik
44 f.vrchol=0;
45 int i,j,N;
46 char vyraz[40];
47
48 //cout<<"Vlozte postfixovy vyraz na vyhodnotenie:\n";
49 cin.getline(vyraz,39)
50
51 N=(int)strlen(vyraz); //v 'X' je dlzka nacitaneho retazca zo standardneho vstupu
52
53 // v cykle 'for' prechadzame vstupny vyraz ulozeny v poli 'vyraz' zlava doprava.
54 // Ak narazime na znak reprezentujuci cislo, vlozime ho na vrchol
55 // zasobnika ('f.pamat[f.vrchol]'), ak narazime na znak
56 // reprezentujuci operator, potom vyberieme z vrcholu zasobnika 2 operandy, aplikujeme na ne
57 // operator a namiesto tychto dvoch operandov vlozime na vrchol zasobnika vysledok samotnej
58 // operacie
59
60 for(i=0; i<N; i++)
61 {
62 if (vyraz[i]==' ') {
63 continue;
64 }
65 if (vyraz[i]=='+') {
66 push(f, (pop(f) + pop(f)));
67 continue;
68 }
69
70 if (vyraz[i]=='*') {
71 push(f, (pop(f) * pop(f)));
72 continue;
73 }
74
75 if (vyraz[i]=='/') {
76 push(f, (pop(f) / pop(f)));
77 continue;
78 }
79
80 if (vyraz[i]=='-') {
81 push(f, (pop(f) - pop(f)));
82 continue;
83 }
84
85 j=0;
86 while((vyraz[i]>='0' && vyraz[i]<='9') || vyraz[i]=='.') {
87 buffer[j] = vyraz[i];
88 i++;
89 j++;
90 }
91 buffer[j]=0;
92 x = atof (buffer);
93 if(FULL == push(f,x)){
94 cout<<"LIFO overflow";
95 break;
96 }
97 }
98 //na vrchole zasobnika je uz vysledok vyhodnoteneho postfixoveho aritmetickeho vyrazu, takze ho
99 //vypiseme
100 cout<<pop(f);
101 return 0;
102 }
