17.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
17. Prednáška

úlohy | cvičenie


Výnimky

Z doterajších našich programátorských skúseností vieme, čo sa deje s programom, keď sa počas behu narazí na nejakú chybu:

  • preruší sa vykonávanie programu
  • vypíše sa chybová správa (najčastejšie v nejakom dialógovom okienku)
  • program väčšinou potom skončí

Takejto situácii hovoríme, že vznikol výnimočný stav (výnimka, po anglicky exception) a takýto výnimočný stav sa v počítači správa inak ako normálny beh programu.

Čo by mohol robiť programátor, keď vie, že nejaký blok príkazov (napr. procedúra) niekedy môže spadnúť na chybe, teda môže vzniknúť výnimka. Free Pascal mu poskytuje dva rôzne spôsoby spracovania výnimky:

  • ak nastane výnimka, tento výnimočný stav zruš a ak treba, pritom ešte urob nejaké akcie (napr. niečo vypíš, zapíš o tom informáciu do súboru, zmeň obsah nejakej premennej, ...)
  • pre tento spôsob spracovania výnimky bude slúžiť nová konštrukcia:
try
  príkazy
except
  príkazy
end
  • ak nastane výnimka, iba uprac rozrobené veci a vyskoč z momentálneho bloku - chybový stav stále trvá a ak nebude spracovaný neskôr (napr. v nadradenom bloku), tak program spadne a oznámi chybovú správu
  • pre tento spôsob spracovania výnimky bude slúžiť nová konštrukcia:
try
  príkazy
finally
  príkazy
end

Tiež ukážeme, ako môžeme v konštrukcii try...except...end rozpoznávať rôzne typy vzniknutých chýb, a tiež ako môžeme "vyrábať" aj svoje vlastné typy chýb.



Vyvolanie výnimky



Najčastejšie výnimočné stavy v našich programoch vyvolávajú rôzne chyby, napr.

  • pretečenie indexu poľa,
  • práca s chybne vytvorenou inštanciou nejakej triedy,
  • chybná aritmetika (napr. pretečenie, delenie nulou),
  • chybný formát pri čítaní údajov zo súboru.

Vo všetkých týchto prípadoch (ak nie je v nastaveniach kompilátora vypnutá kontrola) sa zastaví vykonávanie programu, programu sa nastaví chybový stav a vyskočí sa z práve vykonávaného bloku (napr. procedúry) na vyššiu úroveň. Aj na tejto vyššej úrovni (napr. tiež v nejakom podprograme, ktorý volal procedúru s chybou) sa výpočet zastaví a vyskakuje sa z neho s chybovým stavom. Takto vyskakovanie pokračuje, až kým

  • buď vyskočíme z hlavného programu - vtedy sa oznámi chybová správa,
  • alebo pri vyskakovaní natrafíme na konštrukciu try...except...end, ktorá chybový stav zruší a od toho miesta program ďalej pokračuje normálne.

Tento mechanizmus (vyskakovanie z programových blokov) môžeme využiť aj pri našom programovaní bez toho, aby sme museli vyvolávať niektorú z klasických chýb (napr. úmyselné delenie nulou). Napr. v našej procedúre POP na vyberanie údaja z vrchu zásobníka, v prípade, že je zásobník prázdny, vyvoláme úplne novú chybu, ktorá spôsobí spadnutie celého programu - samozrejme, keď nebude ošetrená pomocou try...except...end.

Príkaz na vyvolanie výnimky má tvar

raise výnimka;

kde ako výnimka musíme uviesť nejakú inštanciu preddefinovanej triedy Exception (táto trieda je definovaná v štandardnej jednotke SysUtils, preto ju nesmieme zabudnúť pridať medzi jednotky v uses). Najčastejšie to bude v našich programoch vyzerať takto:

if vážny problém then
  raise Exception.Create('nejaká chybová správa');

Ak teda nastane nejaký vážny problém, program sa prepne do chybového stavu, čo väčšinou spôsobí spadnutie programu, ale s našou chybovou správou. Definíciu metódy Pop triedy Stack by sme mohli zapísať takto:

uses
  SysUtils;
 
...
 
procedure TStack.Pop(var P: TPrvok);
begin
  if Empty then
    raise Exception.Create('TStack: chybna operacia POP s prazdnym zasobníkom');
  P := Pole[High(Pole)];
  SetLength(Pole, Length(Pole) - 1);
end;
 
function TStack.Pop: TPrvok;
begin
  Pop(Result);
end;

Aj verzia Pop ako funkcia spôsobí v prípade prázdneho zásobníka spadnutie programu. Všimnite si, že takto definovaný unit (nepoužíva ani WriteLn ani ShowMessage) je univerzálny pre grafický aj konzolový režim.

Otestovať takto upravený zásobník môžeme týmto programom:

uses
  StackUnit;
 
var
  S: TStack;
  I: Integer;
begin
  S := TStack.Create;
  for I := 1 to 5 do
    S.Push(I * I);
  for I := 1 to 10 do
    WriteLn(S.Pop);
  S.Free;
  WriteLn('hotovo');
  ReadLn;
end.

Program najprv vloží 5 čísel do zásobníka (1, 4, 9, 16, 25) a potom sa snaží z tohto zásobníka vybrať 10 čísel a vypísať ich. Zrejme prvých päť čísel sa podarí (program vypíše 25 16 9 4 1) a šieste sa mu už nepodarí, a preto spadne - dostávame chybovú správu.

Ďalej ukážeme, ako môžeme túto chybu zachytiť a nedovoliť, aby takýto program spadol.



Strážené príkazy



Programová konštrukcia try...except...end slúži na zachytenie prípadnej chyby, ošetrenie takejto situácie a zrušenie chybového stavu. Základný tvar takéhoto príkazu vyzerá takto:

try
  príkaz11;
  príkaz12;
  príkaz13;
  ...
except
  príkaz21;
  príkaz22;
  príkaz23;
  ...
end;

Pracuje nasledovne:

  • podobne ako v konštrukcii begin ... end, sa postupne vykonávajú príkazy medzi try a except, teda príkaz11; príkaz12; ...
  • ak počas ich vykonávania nenastane žiadny výnimočný stav, príkazy medzi except a end sa preskočia
  • ak nastane nejaká chyba (napr. chceme vybrať neexistujúci prvok zo zásobníka), vykonávanie tejto postupnosti príkazov sa preruší a ďalej sa pokračuje na príkazoch medzi except a end, t.j. príkaz21; príkaz22; ...
    • zároveň sa zruší chybový stav, a teda po skončení celej konštrukcie try...except...end by mal program pokračovať tak, ako keby žiadna chyba ani nebola

Program, ktorým sme vyvolali chybu pri čítaní zásobníka, by sme mohli upraviť takto:

var
  S: TStack;
  I: Integer;
begin
  S := TStack.Create;
  for I := 1 to 5 do
    S.Push(I * I);
  try
    for I := 1 to 10 do
      WriteLn(S.Pop);
  except
    WriteLn('nepodarilo sa citat zo zasobnika');
  end;
  S.Free;
  WriteLn('hotovo');
  ReadLn;
end.

Pri spustení programu sa vypíše prvých päť čísel a za tým správa o tom, že sa nepodarilo čítať zo zásobníka. Na koniec sa vypíše riadok s textom hotovo. Uvedomte si, že ak by v stráženom bloku chyba nenastala (druhý cyklus by bol napr. len do 5), príkaz medzi except a end sa nevykoná - teda sa nevypíše žiadna správa o nepodarenom čítaní zo zásobníka.

Ak by sme konštrukciu try posunuli do vnútra cyklu:

var
  S: TStack;
  I: Integer;
begin
  S := TStack.Create;
  for I := 1 to 5 do
    S.Push(I * I);
  for I := 1 to 10 do
    try
      WriteLn(S.Pop);
    except
      WriteLn('nepodarilo sa citat zo zasobnika');
    end;
  S.Free;
  WriteLn('hotovo');
  ReadLn;
end.

Teraz je strážený len jeden príkaz na vypísanie prečítaného čísla zo zásobníka a preto v prípade chyby sa preruší vykonávanie len tohto jediného príkazu a cyklus pokračuje ďalej. Preto program vypíše 5 čísel a za tým päťkrát správu, že sa nepodarilo čítať zo zásobníka.

Pri spúšťaní našich programov priamo z prostredia Lazarus, tieto bežia v ladiacom režime a preto sa pri každej výnimke program pozastaví a ladiace prostredie sa nás opýta, či chceme program zastaviť alebo pokračovať v normálnom behu (zvolíme Pokračovať). Mohli by sme to vypnúť vo voľbách prostredia v záložke Debugger.

Doterajšie naše riešenie stráženého bloku príkazov zachytí ľubovoľnú chybu a bez ohľadu na to, čo sa naozaj stalo, chyba sa zruší a vypíše sa správa o nepodarenom čítaní zo zásobníka. Ak by sa napr. vyskytla nejaká iná chyba, my sa to vôbec nedozvieme a budeme si myslieť, že bol vadný príkaz Pop.

Konštrukcia try...except...end dokáže rozlišovať typy chýb a správať sa rôzne pre rôzne chyby. Každá štandardná výnimka má svoj preddefinovaný typ, napr EDivByZero, EWin32Error, EInOutError, ... Ak chceme aby except vedel rozlíšiť aj nami vygenerovanú výnimku, musíme príkaz raise trochu skomplikovať. Doteraz sme ho používali v tvare

if vážny problem then
  raise Exception.Create('nejaká chybová správa');

a teda vždy to bola len inštancia triedy Exception (tak ako sú aj všetky osotané výnimky). Preto najprv vytvoríme svoj vlastný "výnimkový" typ a až s týmto novým typom budeme vyvolávať výnimku. Najprv teda zadeklarujeme odvodenú triedu od Exception, napr.

type
  EMojaVynimka = Class(Exception);

a teraz ju môžeme vyvolať

if vážny problém then
  raise EMojaVynimka.Create('nejaká chybová správa');

Program sa teraz bude správať presne rovnako ako predtým, ale konštrukcia try...except...end takúto chybu už bude vedieť rozpoznať čo môžeme využiť pri spracovávaní chyby. Teraz náš testovací program môžeme prepísať

var
  S: TStack;
  I: Integer;
begin
  S := TStack.Create;
  for I := 1 to 5 do
    S.Push(I * I);
  try
    for I := 1 to 10 do
      WriteLn(S.Pop);
  except
    on EMojaVynimka do
      WriteLn('nepodarilo sa citat zo zasobnika');
  end;
  S.Free;
  WriteLn('hotovo');
  ReadLn;
end.

Takéto vylepšenie konštrukcie except spôsobí, že len chyba typu EMojaVynimka sa spracuje a všetky ostatné typy chýb ostávajú chybami a spôsobia normálne spadnutie programu.



Chránené príkazy



Pri programovaní sa často stretávame so situáciou, že niektoré príkazy potrebujeme bezpodmienečne vykonať, aj keď sa z nejakých dôvodov preruší výpočet, napr. pre výskyt chyby alebo ukončenie procedúry pomocou Exit. Napr. vždy, keď v procedúre vytvoríme pomocnú bitmapu, pred ukončením procedúry ju musíme zrušiť. Podobne, vždy, keď otvoríme súbor, na záver ho musíme zatvoriť, Môžeme na to použiť konštrukciu try...finally...end. Vyzerá veľmi podobne ako konštrukcia try...except...end, ale má veľmi dôležité rozdiely:

try
  príkaz11;
  príkaz12;
  príkaz13;
  ...
finally
  príkaz21;
  príkaz22;
  príkaz23;
  ...
end;

Pracuje nasledovne:

  • podobne ako v konštrukcii begin ... end, sa postupne vykonávajú príkazy medzi try a finally, teda príkaz11; príkaz12; ...
  • ak počas ich vykonávania nenastane žiadny výnimočný stav, pokračuje sa vo vykonávaní príkazov za finally, t.j. príkaz21; príkaz22; ...
  • ak nastane nejaká chyba (napr. chceme vybrať neexistujúci prvok zo zásobníka), vykonávanie tejto postupnosti príkazov sa preruší a ďalej sa pokračuje na príkazoch medzi finally a end, t.j. príkaz21; príkaz22; ...
    • chybový stav ale stále ostáva nastavený a teda po skončení celej konštrukcie try...finally...end program bude pokračovať spracovávaním výnimočného stavu, teda pravdepodobne spadne.

Program, ktorým sme vyvolali chybu pri čítaní zásobníka by sme mohli upraviť takto:

var
  S: TStack;
  I: Integer;
begin
  S := TStack.Create;
  for I := 1 to 5 do
    S.Push(I * I);
  try
    for I := 1 to 10 do
      WriteLn(S.Pop);
  finally
    WriteLn('koniec cyklu');
    S.Free;
  end;
  WriteLn('hotovo');
  ReadLn;
end.

Pri spustení programu sa vypíše prvých päť čísel a za tým správa o skončení cyklu. Keďže chránené príkazy medzi try a finally spôsobili výnimočný stav (bola tam chyba prázdny zásobník), výpočet sa preruší a teda sa už nevypíše riadok s textom hotovo. Zrejme program teraz spadne aj s chybovou správou.

Uvedomte si, že ak by v chránenom bloku chyba nenastala (druhý cyklus by bol napr. len do 5), príkazy medzi finally a end by sa tiež vykonali - teda sa vypíše nielen správa o konci cyklu ale aj riadok s textom hotovo.

Chránené príkazy konštrukciou try...finally...end fungujú nielen pre chybové stavy ale aj pre rôzne typy vyskakovania, napr. príkazmi Exit a Break.

Ak sa napr. v časti medzi try a finally objaví Exit, skôr ako sa naozaj opustí podprogram, vykonajú sa ešte príkazy medzi finally a end. Môžeme to vidieť na nasledujúcej ukážke:

var
  T: TextFile;
  I, Pocet: Integer;
begin
  AssignFile(T, 'cisla.txt');
  Reset(T);
  Pocet := 0;
  try
    while not EOF(T) do
    begin
      Read(T, I);
      if I < 0 then
        Exit;
      Inc(Pocet);
    end;
  finally
    CloseFile(T);
  end;
  WriteLn('pocet = ', Pocet);
  ReadLn;
end.

Ak textový súbor obsahuje len nezáporné čísla, program vypíše ich počet, inak ak obsahuje aspoň jedno záporné číslo, program nič nevypíše. V oboch prípadoch sa korektne zatvorí otvorený textový súbor.

Práve takýto spôsob práce so súborom, keď jeho zatvorenie sa nachádza v časti finally, sa považuje za veľmi korektné:

  ...
  AssignFile(t, 'subor.txt');
  Rewrite(t);                       // alebo Reset(t);
  try
    ...
    // práca so súborom
    ...
  finally
    CloseFile(t);
  end;)
  ...

Analogicky sa zvykne pracovať aj s bitmapami:

  ...
  Bmp := TBitmap.Create;
  try
    ...
    // práca s bitmapou
    ...
  finally
    Bmp.Free;
  end;
  ...


Generické triedy

Pozrime programovú jednotku, ktorá definuje triedu TStack, teda zásobník. Je tu už pridané spracovanie chybných stavov pomocou výnimiek:

unit StackUnit;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils;
 
type
  TPrvok = Integer;
 
  { TStack }
 
  TStack = class
    Pole: array of TPrvok;
    procedure Push(P: TPrvok);
    procedure Pop(var P: TPrvok);
    function Pop: TPrvok;
    function Top: TPrvok;
    function Empty: Boolean;
  end;
 
implementation
 
{ TStack }
 
procedure TStack.Push(P: TPrvok);
begin
  SetLength(Pole, Length(Pole) + 1);
  Pole[High(Pole)] := P;
end;
 
procedure TStack.Pop(var P: TPrvok);
begin
  if Empty then
    raise Exception.Create('chybna operacia POP so Stackom');
  P := Pole[High(Pole)];
  SetLength(Pole, Length(Pole) - 1);
end;
 
function TStack.Pop: TPrvok;
begin
  Pop(Result);
end;
 
function TStack.Top: TPrvok;
begin
  if Empty then
    raise Exception.Create('chybna operacia TOP so Stackom');
  Result := Pole[High(Pole)];
end;
 
function TStack.Empty: Boolean;
begin
  Result := Pole = nil;
end;
 
end.

Túto dátovú štruktúru otestujeme takto:

var
  I: Integer;
  Stack: TStack;
begin
  Stack := TStack.Create;
  for I := 1 to 10 do
    Stack.Push(I * I);
  while not Stack.Empty do
    WriteLn(Stack.Pop);
  Stack.Free;
  WriteLn('hotovo');
  ReadLn;
end.

Problém vznikne vtedy, keď chceme v tomto programe otestovať aj zásobník reálnych čísel. Nemôžeme opraviť StackUnit, tak že zmeníme TPrvok na typ Real. Potom by nechodili celé čísla. Museli by sme teraz vytvoriť kópiu tohto unitu a v ňom vyrobiť novú triedu, napr. TStackReal.

Naučíme sa iný spôsob na riešenie takýchto úloh. Novú triedu môžeme definovať tak, že pri jej deklarácii určíme nejaký typ ako parameter. V skutočnosti nebudeme definovať triedu, ale len šablónu, na základe ktorej sa neskôr môžu vytvoriť nové triedy dosadením konkrétneho typu za parameter. Takýmto šablónam hovoríme generická trieda.

Pri definovaní generickej triedy

  • pred meno triedy musíme zapísať rezervované slovo generic
  • za meno triedy do špicatých zátvoriek < a > musíme zapísať parameter, t.j. identifikátor typu. Keďže je to parameter, tento označuje nie existujúci typ, ale v budúcnosti ľubovoľný typ. My sme sem zapísali _TPrvok, aby sme zvýraznili, že je to parameter. Hoci tento parameter sa mohol volať aj TPrvok.
unit StackUnit;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils;
 
type
   TPrvok = Integer;
 
 { TStack }
 
  generic TStack<_TPrvok> = class   // parameter šablóny
    Pole: array of _TPrvok;
    procedure Push(P: _TPrvok);
    procedure Pop(var P: _TPrvok);
    function Pop: _TPrvok;
    function Top: _TPrvok;
    function Empty: Boolean;
  end;
 
implementation
 
{ TStack }
 
procedure TStack.Push(P: _TPrvok);
begin
  SetLength(Pole, Length(Pole) + 1);
  Pole[High(Pole)] := P;
end;
 
procedure TStack.Pop(var P: _TPrvok);
begin
  if Empty then
    raise Exception.Create('chybna operacia POP so Stackom');
  P := Pole[High(Pole)];
  SetLength(Pole, Length(Pole) - 1);
end;
 
function TStack.Pop: _TPrvok;
begin
  Pop(Result);
end;
 
function TStack.Top: _TPrvok;
begin
  if Empty then
    raise Exception.Create('chybna operacia TOP so Stackom');
  Result := Pole[High(Pole)];
end;
 
function TStack.Empty: Boolean;
begin
  Result := Pole = nil;
end;
 
end.

Ak teraz budeme chcieť využiť túto šablónu v našom programe, musíme najprv vyrobiť novú triedu dosadením parametra. Slúži na to zápis na vytvorenie nového typu pomocou specialize. Napr.

type
  TStackInt  = specialize TStack<Integer>;
  TStackReal = specialize TStack<Real>;
  TStackStr  = specialize TStack<string>;

Takto sa zadefinovali tri nové triedy: TStackInt, TStackReal, TStackStr. Teraz funguje nielen

var
  I: Integer;
  Stack: TStackInt;
begin
  Stack := TStackInt.Create;
  for I := 1 to 10 do
    Stack.Push(I * I);
  while not Stack.Empty do
    WriteLn(Stack.Pop));
  Stack.Free;
  WriteLn('hotovo');
  ReadLn;
end.

ale aj

var
  I: Integer;
  Stack: TStackReal;
begin
  Stack := TStackReal.Create;
  for I := 1 to 10 do
    Stack.Push(I * I / 10);
  while not Stack.Empty do
    WriteLn(Stack.Pop));
  Stack.Free;
  WriteLn('hotovo');
  ReadLn;
end.

alebo

var
  I: Integer;
  Stack: TStackStr;
begin
  Stack := TStackStr.Create;
  for I := 1 to 10 do
    Stack.Push(IntToStr(I) + '. riadok');
  while not Stack.Empty do
    WriteLn(Stack.Pop);
  Stack.Free;
  WriteLn('hotovo');
  ReadLn;
end.


Aritmetické výrazy

Infix



Z matematiky a aj z programovania poznáme takýto spôsob zápisu aritmetických výrazov:

2 + 5
2 + 5 * 6
4 + (2 + 5) * 6

Znamienko operácie je medzi svojimi operandmi. Niektoré operácie (napr. *, /) majú vyššiu prioritu ako iné (napr. +, -) a preto vieme, že 2 + 5 * 6 = 32 a nie 42 (ak by + malo vyššiu prioritu ako *). Poradie vyhodnocovania operácií vo výraze môžeme ešte zmeniť pomocou okrúhlych zátvoriek. Ak by sme chceli tieto výrazy zapísať trochu formálnejšie, mohlo by to vyzerať napr. takto:

výraz == operand operácia operand
operácia == +, -, *, /
operand == číslo, výraz, ( výraz )

Takémuto zápisu, keď operácia je medzi operandmi, hovoríme in-fixový zápis. V niektorých (programátorských) aplikáciách sa využíva pre-fixový (tzv. poľský) zápis alebo post-fixový (tzv. prevrátený poľský) zápis.



Prefix



Prefixový zápis sa líši od infixového umiestnením znaku operácie vzhľadom k operandom: znamienko nie je medzi ale pred operandmi. Formálny zápis by mohol byť:

výraz == operácia operand operand
operácia == +, -, *, /
operand == číslo, výraz

Pre tento zápis nepotrebujeme rozlišovať prioritu operácií (všetky sú rovnocenné) a ani nepotrebujeme zátvorky.



Postfix



Postfixový zápis je veľmi podobný prefixovému, len znak operácie je za operandmi. Formálne to vyzerá takto:

výraz == operand operand operácia
operácia == +, -, *, /
operand == číslo, výraz

Aj v tomto zápise nie sú ani priority operácií ani zátvorky. Ukážme zápis niekoľkých aritmetických výrazov v rôznych zápisoch:

infix prefix postfix
4 + 5 * 7 + 4 * 5 7 4 5 7 * +
(4 + 5) * 7 * + 4 5 7 4 5 + 7 *
1 * 2 * 3 * 4 * 5 * * * * 1 2 3 4 5 1 2 3 4 5 * * * *
9 - 3 / 1 + 2 + - 9 / 3 1 2 9 3 1 / - 2 +
(9 - 3) / (1 + 2) / - 9 3 + 1 2 9 3 - 1 2 + /

Oba tieto zápisy (prefix aj postfix) sú zaujímavé aj tým, že algoritmy, ktoré ich vyhodnocujú sú výrazne jednoduchšie ako pre infixový zápis. Ukážme vyhodnocovanie postfixového zápisu:

  • postupne čítame výraz zľava doprava - na vstupe je buď operand alebo znak operácie,
  • keď je na vstupe operand (pre jednoduchosť predpokladajme, že je to číslo), tak ho vložíme do zásobníka (teda Push(číslo)),
  • keď je na vstupe znak operácie, tak zrejme sme už predtým museli do zásobníka vložiť minimálne 2 čísla, tieto dve čísla zo zásobníka vyberieme, vykonáme operáciu (napr. +) a opäť vložíme do zásobníka (teda Push(Pop + Pop)),
  • po skončení vyhodnocovania celého výrazu na zásobníku ostane výsledná hodnota.

Program na vyhodnotenie postfixu ako konzolová aplikácia:

uses
  StackUnit;
 
type
  TStackInt = specialize TStack<Integer>;
 
var
  S: string;
  I, J: Integer;
  Cislo1, Cislo2: Integer;
  Stack: TStackInt;
begin
  Stack := TStackInt.Create;
  Write('zadaj: ');
  ReadLn(S);
  S := S + ' ';
  I := 1;
  while I <= Length(S) do
  begin
    case S[I] of
      '0'..'9':
        begin
          J := 0;
          while S[I] in ['0'..'9'] do
          begin
            J := J * 10 + Ord(S[I]) - Ord('0');
            Inc(I);
          end;
          Stack.Push(J);
          Dec(I);
        end;
      '+':
        begin
          Stack.Pop(Cislo1);
          Stack.Pop(Cislo2);
          Stack.Push(Cislo2 + Cislo1);
        end;
      '-':
        begin
          Stack.Pop(Cislo1);
          Stack.Pop(Cislo2);
          Stack.Push(Cislo2 - Cislo1);
        end;
      '*':
        begin
          Stack.Pop(Cislo1);
          Stack.Pop(Cislo2);
          Stack.Push(Cislo2 * Cislo1);
        end;
      '/':
        begin
          Stack.Pop(Cislo1);
          Stack.Pop(Cislo2);
          Stack.Push(Cislo2 div Cislo1);
        end;
    end;
    Inc(I);
  end;
  WriteLn('vysledok = ', Stack.Pop);
  Stack.Free;
  ReadLn;
end.

Malými zmenami vyrobíme aj verziu s reálnou aritmetikou:

type
  TStackReal = specialize TStack<Real>;
 
var
  S: string;
  I, J: Integer;
   Stack: TStackReal;
begin
  Stack := TStackReal.Create;
  repeat
    Write('zadaj: ');
    ReadLn(S);
    if S = '' then
      Break;
    S := S + ' ';
    I := 1;
    while I <= Length(S) do
    begin
      case S[I] of
        '0'..'9':
          begin
            J := 0;
            while S[I + J] in ['0'..'9', '.'] do
              Inc(J);
            Stack.Push(StrToFloat(Copy(S, I, J)));
            Inc(I, J - 1);
          end;
        '+':
          Stack.Push(Stack.Pop + Stack.Pop);
        '-':
          Stack.Push(- Stack.Pop + Stack.Pop);
        '*':
          Stack.Push(Stack.Pop * Stack.Pop);
        '/':
          Stack.Push(1 / Stack.Pop * Stack.Pop);
      end;
      Inc(I);
    end;
    WriteLn('vysledok = ', Stack.Pop:0:2);
    while not Stack.Empty do
      Stack.Pop;
  until False;
  Stack.Free;
end.

Všimnite si, ako sme využili funkciu Pop a tým ušetrili pomocné premenné Cislo1 a Cislo2. Hoci takýto zápis nemusí vždy fungovať - závisí to od optimalizácií v kompilátore.

Na konci repeat cyklu ešte pred until sme vyčistili zásobník, lebo v ňom mohli ostať ešte nejaké nespracované čísla (mohli by sme vtedy vypísať nejakú chybovú správu).

Ďalšie námety:

  • navrhnite program, ktorý bude vyhodnocovať výrazy v prefixovom zápise
  • navrhnite algoritmus na prepis infixového zápisu do postfixového, resp. prefixu (nie je to triviálne)
  • úplne uzátvorkovaný výraz: je infix, v ktorom je každá operácia uzátvorkovaná, napr.
3*4+5*6-7*8 -> (((3*4)+(5*6))-(7*8))
vďaka tomu nepotrebujeme prioritu operátorov
  • urobte prevody z/do úplne uzátvorkovaného do/z pre/post-fixu
  • vyhodnoťte úplne uzátvorkovaný výraz
  • navrhnite algoritmus na prepis prefixu do postfixu a naopak
  • vyhodnocujte výrazy s premennými, príp. s unárnymi operáciami a funkciami (napr. unárne mínus, funkcia abs, sqr, sqrt a pod.)
  • porozmýšľajte nad analógiou s logickými výrazmi a operáciami and, or, xor a not, resp. s relačnými operátormi =, <>, ´<=, ...


Prepis rekurzie

Máme rekurzívnu metódu pre robota, ktorá kreslí špirálu:

type
  TMojRobot = class(TRobot)
    procedure Spir(N: Integer; Dlzka: Real);
  end;
 
procedure TMojRobot.Spir(N: Integer; Dlzka: Real);
begin
  if N = 0 then
    Lt(177)
  else
  begin
    Fd(Dlzka);
    Lt(90);
    Spir(N - 1, Dlzka + 1);
    Rt(90);
    Fd(-Dlzka);
  end;
end;

Na nerekurzívnu metódu využijeme trochu upravený zásobník. Najprv zadefinujeme triedu zásobník pre našu konkrétnu úlohu takto: prvok zásobníka bude záznam, ktorý obsahuje položky Adr - "skoková adresa", N a Dlzka - zapamätávané hodnoty formálnych parametrov procedúry. Tiež upravíme metódy Push a Pop tak, aby sa nám so zásobníkom pracovalo pohodlnejšie: nebudeme pracovať naraz s celým prvkom zásobníka (na to by sme potrebovali nejakú premennú typu záznam, t.j. TPrvok), ale Push a Pop budú pracovať priamo s položkami tohto záznamu. Prispôsobená trieda TStack môže vyzerať takto:

type
  TStack = class
    Pole: array of record
      Adr: Integer;     // adresa skoku
      N: Integer;       // zapamätaná hodnota formálneho parametra
      Dlzka: Real;      // zapamätaná hodnota formálneho parametra
    end;
 
    ...
    procedure Push(Aadr, Nn: Integer; Ddlzka: Real);
    procedure Pop(var Aadr, Nn: Integer; var Ddlzka: Real);
    ...
  end;
 
procedure TStack.Push(Aadr, Nn: Integer; Ddlzka: Real);
begin
  SetLength(Pole, Length(Pole) + 1);
  with Pole[High(Pole)] do
  begin
    Adr := Aadr;
    N := Nn;
    Dlzka := Ddlzka;
  end;
  
end;
 
procedure TStack.Pop(var Aadr, Nn: Integer; var Ddlzka: Real);
begin
  if Empty then
    raise Exception.Create('Prázdny zásobník');
  with Pole[High(Pole)] do
  begin
    Aadr := Adr;
    Nn := N;
    Ddlzka := Dlzka;
  end;
  SetLength(Pole, Length(Pole) - 1);
end;

Rekurzívnu procedúru najprv logicky rozdelíme na časti, z ktorých potom budeme skladať nerekurzívne riešenie:

  • prvá časť začína začiatkom procedúry - sem sa "skáče" pri prvom zavolaní procedúry ale aj pri každom ďalšom rekurzívnom volaní; prvá časť končí prvým rekurzívnym volaním - začiatok prvej časti označíme "adresa 1"
  • za prvým rekurzívnym volaním začína druhá - sem sa skáče po návrate z rekurzívneho volania, t.j. túto adresu si treba zapamätať pri rekurzívnom volaní, t.j. "adresa 2"
procedure TMojRobot.Spir(N: Integer; Dlzka: Real);
begin
// 1:
  if N = 0 then
    Lt(177)
  else
  begin
    Fd(Dlzka);
    Lt(90);
    Spir(N - 1, Dlzka + 1);
// 2:
    Rt(90);
    Fd(-Dlzka);
  end;
end;

Rekurzívnu procedúru teraz prepíšeme na cyklus, v ktorom sa budú vykonávať buď prvá časť alebo druhá časť, pričom cyklus skončí a teda aj celá procedúra, keď už sa vykonalo príslušný počet krát návrat z rekurzie. Zásobník použijeme takto:

  • každý záznam v zásobníku reprezentuje vykonanie jednej z dvoch častí nášho rozdeleného programu, pričom si budeme pamätať aj lokálne premenné (t.j. formálne parametre), ktoré tejto časti prislúchajú,
  • na začiatku do zásobníka vložíme jedinú informáciu, že chceme začať vykonávať prvú časť (Adr=1) a pričom hodnoty premenných N a Dlzka sú presne tie, ktoré prišli ako hodnoty formálnych parametrov - vykonáme Push(1, N, Dlzka);
  • potom prichádza cyklus, ktorý zo zásobníka vyberie vrchnú hodnotu (teda trojicu Adr, N, Dlzka) a podľa Adr skočí buď na prvú alebo druhú časť,
  • zrejme, ak je zásobník prázdny, už sme vykonali všetko, čo bolo treba a procedúru treba skončiť (preto je cyklus while not Zasobnik.Empty do),
  • najdôležitejšie je správne zrealizovať rekurzívne volanie: vtedy treba do zásobníka uložiť dve informácie - zapamätať si návratovú adresu Push(2, N, Dlzka); a zabezpečiť, aby sa znovu začala vykonávať rekurzívna procedúra od začiatku, teda Push(1, N-1, Dlzka+1);
  • keďže Zasobnik je objektová premenná, treba ju na začiatku programu vytvoriť: Zasobnik := TStack.Create a na konci zase uvoľniť: Zasobnik.Free.

Nerekurzívna verzia kreslenia špirály môže vyzerať napr. takto:

type
  TMojRobot = class(TRobot)
    procedure Spir(N: Integer; Dlzka: Real);
    procedure SpirN(N: Integer; Dlzka: Real);
  end;
 
procedure TMojRobot.SpirN(N: Integer; Dlzka: Real);
var
  Zasobnik: TStack;
  Adr: Integer;             // adresa skoku do príslušnej časti
begin
  Zasobnik := TStack.Create;
  Zasobnik.Push(1, N, Dlzka);
  while not Zasobnik.Empty do
  begin
    Zasobnik.Pop(Adr, N, Dlzka);
    case Adr of
      1:
        if N = 0 then
          Lt(177)
        else
        begin
          Fd(Dlzka);
          Lt(90);
          Zasobnik.Push(2, N, Dlzka);        // návrat po rekurzívnom volaní
          Zasobnik.Push(1, N - 1, Dlzka + 1);    // rekurzívne volanie
        end;
      2:
        begin
          Rt(90);
          Fd(-Dlzka);
        end;
    end;
  end;
  Zasobnik.Free;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  Robot: TMojRobot;
begin
  Robot := TMojRobot.Create;
  Robot.SpirN(100, 1);
  Robot.Free;
end;

procedúra sa dá upraviť tak, aby sa nerobila operácia Push, ak to nie je nevyhnutné:

procedure TMojRobot.SpirN(N: Integer; Dlzka: Real);
var
  Zasobnik: TStack;
  Adr: Integer;
begin
  Zasobnik := TStack.Create;
  Adr := 1;
  repeat
    case Adr of
      1:
        if N = 0 then
        begin
          Lt(177);
          Adr := 0;                  // bude treba robiť Pop
        end
        else
        begin
          Fd(Dlzka);
          Lt(90);
          Zasobnik.Push(2, N, Dlzka);
          Adr := 1;
          N := N - 1;
          Dlzka := Dlzka + 1;
        end;
      2:
        begin
          Rt(90);
          Fd(-Dlzka);
          Adr := 0;                // bude treba robiť Pop
        end;
    end;
    if (Adr = 0) and not Zasobnik.Empty then
      Zasobnik.Pop(Adr, N, Dlzka);
  until Adr = 0;
  Zasobnik.Free;
end;



Binárny strom



Ilustrujme tento postup aj rekurzívnu procedúru na kreslenie stromu. Najprv rekurzívna verzia:

procedure TMojRobot.Strom(N: Integer; Dlzka: Real);
begin
// časť 1:
  if N = 0 then
  begin
    Fd(Dlzka);
    Fd(-Dlzka);
  end
  else
  begin
    Fd(Dlzka);
    Lt(45);
    Strom(N - 1, Dlzka * 0.6);
// časť 2:
    Rt(90);
    Strom(N - 1, Dlzka * 0.7);
// časť 3:
    Lt(45);
    Fd(-Dlzka);
  end;
end;

Nerekurzívna verzia môže vyzerať takto:

procedure TMojRobot.StromN(N: Integer; Dlzka: Real);
var
  Zasobnik: TStack;
  Adr: Integer;
begin
  Zasobnik := TStack.Create;
  Zasobnik.Push(1, N, Dlzka);
  while not Zasobnik.Empty do
  begin
    Zasobnik.Pop(Adr, N, Dlzka);
    case Adr of
      1:
        if N = 0 then
        begin
          Fd(Dlzka);
          Fd(-Dlzka);
        end
        else
        begin
          Fd(Dlzka);
          Lt(45);
          Zasobnik.Push(2, N, Dlzka);       // návrat bude na začiatok 2. časti
          Zasobnik.Push(1, N - 1, Dlzka * 0.6);
        end;
      2:
        begin
          Rt(90);
          Zasobnik.Push(3, N, Dlzka);       // návrat bude na začiatok 3. časti
          Zasobnik.Push(1, N - 1, Dlzka * 0.7);
        end;
      3:
        begin
          Lt(45);
          Fd(-Dlzka);
        end;
    end;
  end;
  Zasobnik.Free;
end;



Rekurzívna funkcia



Fibonacciho postupnosť je definovaná rekurentne, napr. takto:

F(0)=0; F(1)=1; F(N)=F(N-1)+F(N-2); pre N > 1

A rekurzívna funkcia:

function Fibonacci(N: Integer): Integer;
begin
  if N < 2 then
    Result := N
  else
    Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;

Postup, pomocou ktorého vieme prepisovať rekurzívne procedúry na nerekurzívne, takto jednoducho nefunguje ani na funkcie ani na var-parametre. Preto najprv túto elegantnú rekurzívnu funkciu prepíšeme na nie veľmi peknú procedúru s jednou globálnou premennou, v ktorej budeme uchovávať výsledok funkcie:

var
  FibResult: Integer;    // globálna premenná - vypočítaná hodnota
 
procedure Fibonacci(N: Integer);
var
  F: Integer;           // pomocná premenná pre uchovanie medzivýpočtu
begin
// časť 1:
  if N < 2 then
    FibResult := N
  else
  begin
    Fibonacci(N - 1);
// časť 2:
    F := FibResult;
    Fibonacci(N - 2);
// časť 3:
    FibResult := FibResult + F;
  end;
end;

Nerekurzívny tvar predchádzajúcej procedúry (všetky tri položky v poli v TStack musia byť teraz typu Integer):

procedure FibonacciN(N: Integer);
var
  F, Adr: Integer;
  Zasobnik: TStack;
begin
  Zasobnik := TStack.Create;
  Zasobnik.Push(1, N, F);
  while not Zasobnik.Empty do
  begin
    Zasobnik.Pop(Adr, N, f);
    case Adr of
      1:
        if N < 2 then
          FibResult := N
        else
        begin
          Zasobnik.Push(2, N, F);               // návrat
          Zasobnik.Push(1, N - 1, F);           // rekurzívne volanie Fibonacci(N-1)
        end;
      2:
        begin
          F := FibResult;
          Zasobnik.Push(3, N, F);               // návrat
          Zasobnik.Push(1, N - 2, F);           // Fibonacci(N-2)
        end;
      3:
        FibResult := FibResult + F;
    end;
  end;
  Zasobnik.Free;
end;



Snehová vločka



Na záver napíšeme nerekurzívny variant procedúry na kreslenie snehovej vločky:

procedure TMojRobot.Vlocka(N: Integer; Dlzka: Real);
begin
  if N <= 0 then
    Fd(Dlzka)
  else
  begin
    Vlocka(N - 1, Dlzka / 3);
    Rt(60);
    Vlocka(N - 1, Dlzka / 3);
    Lt(120);
    Vlocka(N - 1, Dlzka / 3);
    Rt(60);
    Vlocka(N - 1, Dlzka / 3);
  end;
end;

A jej nerekurzívna verzia:

procedure TMojRobot.VlockaN(N: Integer; Dlzka: Real);
var
  Zasobnik: TStack;
  Adr: Integer;
begin
  Zasobnik := TStack.Create;
  Zasobnik.Push(1, N, Dlzka);
  while not Zasobnik.Empty do
  begin
    Zasobnik.Pop(Adr, N, Dlzka);
    case Adr of
      1:
        if N <= 0 then
          Fd(Dlzka)
        else
        begin
          Zasobnik.Push(2, N, Dlzka);
          Zasobnik.Push(1, N - 1, Dlzka / 3);
        end;
      2:
        begin
          Rt(60);
          Zasobnik.Push(3, N, Dlzka);
          Zasobnik.Push(1, N - 1, Dlzka / 3);
        end;
      3:
        begin
          Lt(120);
          Zasobnik.Push(4, N, Dlzka);
          Zasobnik.Push(1, N - 1, Dlzka / 3);
        end;
      4:
        begin
          Rt(60);
          // tu už nemusíme uložiť adresu návratu
          // po návrate sa totiž nemusí robiť nič
          Zasobnik.Push(1, N - 1, Dlzka / 3);
        end;
    end;
  end;
  Zasobnik.Free;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  Robot: TMojRobot;
  I: Integer;
begin
  Robot := TMojRobot.Create;
  for I := 1 to 3 do
  begin
    Robot.VlockaN(4, 100);
    Robot.Lt(120);
  end;
  Robot.Free;
end;


Dátová štruktúra rad

Dátovej štruktúre rad hovoríme aj front alebo aj FIFO (z anglického First In First Out). Takémuto radu zvykneme hovoriť spravodlivý rad. Po anglicky queue.

Táto údajová štruktúra sa veľmi podobá zásobníku. Tiež má jednu operáciu na pridávanie do štruktúry a vyberanie zo štruktúry. Táto štruktúra sa ale podobá na ozajstný rad zákazníkov napr. v obchode: ten, kto príde do obchodu prvý, bude prvý obslúžený (teda FIFO).

Do radu pridávame nové prvky na koniec - hovoríme tomu rear, tail, chvost - operáciou Append (po anglicky: pridaj na koniec, niekedy sa nazýva aj Enqueue). Z radu vyberáme prvý (a nie posledný) prvok - hovoríme tomu front, head, hlavička - operáciou Serve (po anglicky: obslúž, niekedy sa nazýva Dequeue). Vytvoríme triedu TQueue. Veľmi sa podobá definícii zásobníka:

unit QueueUnit;
 
{$mode objfpc}{$H+}
 
interface
 
type
  TQPrvok = string;
  TQueue = class
    Pole: array of TQPrvok;
    constructor Create;
    procedure Serve(var Prvok: TQPrvok);
    procedure Append(Prvok: TQPrvok);
    function Empty: Boolean;
  end;
 
implementation
 
constructor TQueue.Create;
begin
  Pole := nil;
end;
 
procedure TQueue.Serve(var Prvok: TQPrvok);
begin
  if Empty then
    raise Exception.Create('Rad je prázdny pre metódu Serve');
  Prvok := Pole[0];
  if Length(Pole) = 1 then
    Pole := nil
  else                                           // vyhoď prvý prvok poľa
    Pole := Copy(Pole, 1, MaxInt);   // takto to funguje, len ak výsledok nie je prázdne pole
end;
 
procedure TQueue.Append(Prvok: TQPrvok);
begin
  SetLength(Pole, Length(Pole) + 1);
  Pole[High(Pole)] := Prvok;
end;
 
function TQueue.Empty: Boolean;
begin
  Result := Pole = nil;
end;
 
end.

Štruktúru rad ukážeme na programe, ktorý číta textový súbor iba raz a vytvára nový zdvojený súbor:

...
uses
  QueueUnit;
 
var
  Rad: TQueue;
  Subor1, Subor2: TextFile;
  Prvok: TQPrvok;          // kde TQPrvok = string
begin
  Rad := TQueue.Create;
  AssignFile(Subor1, 'Unit1.pas');
  Reset(Subor1);
  AssignFile(Subor2, 'test.txt');
  Rewrite(Subor2);
  while not Eof(Subor1) do
  begin
    Readln(Subor1, Prvok);
    Rad.Append(Prvok);
    Writeln(Subor2, Prvok);
  end;
  CloseFile(Subor1);
  while not Rad.Empty do
  begin
    Rad.Serve(Prvok);
    Writeln(Subor2, Prvok);
  end;
  CloseFile(Subor2);
  Rad.Free;
end.

Ďalšie námety:

  • vytvorte generickú triedu rad
  • prerobte triedu TQueue tak, aby sa nie pri každej operácii Append alebo Serve musela meniť veľkosť dynamického poľa Pole, ale aby sa podobne ako pri zásobníku pamätal aktuálny počet a zmena veľkosti poľa sa teda robila menej často
  • reprezentujte rad v statickom poli veľkosti N:
    • tzv. cyklické pole - s poľom pracujeme tak, ako keby bol zacyklený: za posledným prvkom nasleduje prvý; pamätáme si index na prvý prvok radu (odtiaľ budeme odoberať) a a buď na posledný prvok (sem budeme pridávať) alebo počet prvkov radu;
    • treba správne rozpoznať situáciu, keď je rad plný (metóda Full)
  • viac zásobníkov a radov môžeme využiť v rôznych situáciách, napr. vzájomná simulácia (napr. jedného zásobníka pomocou jedného alebo viacerých radov a naopak), triedenie nejakých čísel pomocou dvoch zásobníkov (bez ďalšieho poľa), využitie zarážky vo fronte, ...


späť | ďalej