Štruktúry (riešené príklady)

Š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:

1. 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:
   1. 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“.
   2. 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“.
2. 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).
3. 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.

Spracovanie postfixového výrazu 5 9 8 + 4 6 * * 7 + *

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=-2, EMPTY=-3}; 
 8 
 9 struct LIFO
10 {
11       int pamat[MAX_PAMAT]; //pole reprezentujuce ADT zasobnik
12       int vrchol; //index vrcholu zasobnika, indexova premenna
13 
14 }; 
15 
16 //VLOZI novu polozku 'x' do pola 'zasobnik.pamat' (do zasobnika) a zvacsi indexovu premennu //'zasobnik.vrchol' o 1
17 stav_zasobnika push(LIFO &zasobnik, int x)
18 {
19       if(zasobnik.vrchol<MAX_PAMAT)
20             zasobnik.pamat[zasobnik.vrchol++]=x;
21       else
22             return FULL;
23       return OK;
24 } 
25 
26 //zmensi indexovu premennu 'zasobnik.vrchol' o 1 a VYBERIE poslednu vlozenu polozku z pola //'zasobnik.pamat' (zo zasobnika)
27 int pop(LIFO &zasobnik)
28 {
29       if(zasobnik.vrchol>0)
30             return zasobnik.pamat[--zasobnik.vrchol];
31       else
32             return EMPTY;
33 } 
34 
35 int main()
36 {
37       LIFO f; //deklaracia strukturovej premennej typu 'LIFO' reprezentujucej zasobnik
38       f.vrchol=0;
39       int X, i;
40       char vyraz[40];
41 
42       //cout<<"Vlozte postfixovy vyraz na vyhodnotenie:\n";
43       cin.getline(vyraz,39)
44 
45       X=(int)strlen(a); //v 'X' je dlzka nacitaneho retazca zo standardneho vstupu 
46       //v cykle 'for' prechadzame vstupny vyraz ulozeny v poli 'vyraz' zlava doprava. Ak narazime na znak
47       //reprezentujuci cislo, vlozime ho na vrchol zasobnika ('f.pamat[f.vrchol]'), ak narazime na znak
48       //reprezentujuci operator, potom vyberieme z vrcholu zasobnika 2 operandy, aplikujeme na ne
49       //operator a namiesto tychto dvoch operandov vlozime na vrchol zasobnika vysledok samotnej
50       //operacie
51 
52       for(i=0; i<X; i++)
53       {
54             if (vyraz[i]=='+')
55                   push(f, (pop(f) + pop(f)));
56             if (vyraz[i]=='*')
57                   push(f, (pop(f) * pop(f)));
58             if ((vyraz[i]>='0') && (vyraz[i]<='9'))
59                   push(f, 0);
60 
61             //vlozenie cisla (v datovom type 'int') reprezentovaneho jednym alebo viacerymi znakmi v poli
62             //'a' na vrchol zasobnika
63             while ((vyraz[i]>='0') && (vyraz[i]<='9'))
64                   push(f, (10 * pop(f) + (vyraz[i++] - '0')));
65             //obsluzenie //ziskanie cisla typu 'int' reprezentovaneho
66             //viaccifernych cis. //znakom ulozenym v 'a[i]' a zvascsenie 'i' o 1
67             //pre posun na dalsiu iteraciu cyklu 'while'
68      }
69       //na vrchole zasobnika je uz vysledok vyhodnoteneho postfixoveho aritmetickeho vyrazu, takze ho
70       //vypiseme
71       cout<<pop(f); 
72       return 0;
73 }