16. Použitie zásobníka, rad


Posledná zmena: 14.11.2002

Banner Text 14.11.2002

    čo sme sa doteraz naučili

    • poznáme údajovú štruktúru zásobník, ktorá má dve základné operácie: push a pop - vloženie a výber hodnoty
    • pri volaniach procedúr a funkcii počítač využíva mechanizmus zásobníka: pri každom volaní podprogramu sa do zásobníka zapamätá návratová adresa a tiež sa na ňom vytvoria všetky lokálne premenné (aj hodnotové formálne parametre)

    čo sa budeme dnes učiť

    • ukážeme, ako sa dá aj veľmi zložitá rekurzívna procedúra prepísať do nerekurzívneho tvaru - využijeme na to zásobník
    • zásobník použijeme aj na spracovanie rôznych typov aritmetických výrazov - uvidíme, čo sú výrazy v infixovom, prefixovom a postfixovom tvare
    • zadefinujeme ešte jednu údajovú štruktúru: rad (front) - podobá sa na zásobník s tým rozdielom, že hoci hodnoty vkladáme na koniec radu, vyberáme ich zo začiatku radu

Prepis rekurzie na nerekurziu

Máme rekurzívnu korytnačiu metódu, ktorá kreslí špirálu: 

type
  TMojaKor = class(TKor)
    procedure spir(n:integer; s:real);
  end;

procedure TMojaKor.spir(n:integer; s:real);
begin
  if n=0 then Vlavo(180)
  else begin
    Dopredu(s); Vlavo(90);
    spir(n-1,s+1);
    Vpravo(90); Dopredu(-s);
  end;
end;
  • pomocou zásobníka vytvoríme nerekurzívnu metódu
  • najprv zadefinujeme triedu zásobník pre našu konkrétnu úlohu: prvok zásobníka bude záznam, ktorý obsahuje položky v-"adresa", n a s - zapamätávané hodnoty
  • tiež upravíme metódy push a pop tak, aby sa nám so zásobníkom pracovalo pohodlnejšie

prispôsobená trieda TStack: 

type
  TPrvok = record v,n:integer; s:real; end;

  TStack = class
    st:array of TPrvok;
    ...
    procedure push(vv,nn:integer; ss:real);
    procedure pop(var vv,nn:integer; var ss:real);
    ...
  end;

procedure TStack.push(vv,nn:integer; ss:real);
begin
  SetLength(st,Length(st)+1);
  with st[high(st)] do begin
    v:=vv; n:=nn; s:=ss;
  end;
end;

procedure TStack.pop(var vv,nn:integer; var ss:real);
begin
  if empty then chyba('Prázdny zásobník');
  with st[high(st)] do begin
    vv:=v; nn:=n; ss:=s;
  end;
  SetLength(st,Length(st)-1);
end;

prepíšme procedúru na nerekurzívnu pomocou nášho nového zásobníka: 

type
  TMojaKor = class(TKor)
    procedure spirN(n:integer; s:real);
  end;

procedure TMojaKor.spirN(n:integer; s:real);
var
  z:TStack;
  v:integer;   // niečo ako "návratová adresa"
begin
  z:=TStack.Create;
  z.push(1,n,s);
  while not z.empty do begin
    z.pop(v,n,s);
    case v of
      1:
        if n=0 then Vlavo(180)
        else begin
          Dopredu(s); Vlavo(90);
          z.push(2,n,s);        // návrat po "rekurzívnom volaní"
          z.push(1,n-1,s+1);    // "rekurzívne volanie"
        end;
      2:
        begin
          Vpravo(90); Dopredu(-s);
        end;
    end;
  end;
  z.Free;             // mal by existovať deštruktor TStack.Destroy
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  k:TMojaKor;
begin
  k:=TMojaKor.Create;
  k.spirN(100,1);
  k.Free;
end;

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

procedure TMojaKor.spirN(n:integer; s:real);
var
  z:TStack;
  v:integer;
begin
  z:=TStack.Create; v:=1;
  while v<>0 do begin
    case v of
      1:
        if n=0 then begin
          Vlavo(180); v:=0;                  // bude treba robiť pop
        end
        else begin
          Dopredu(s); Vlavo(90);
          z.push(2,n,s);
          v:=1; n:=n-1; s:=s+1;
        end;
      2:
        begin
          Vpravo(90); Dopredu(-s); v:=0;     // bude treba robiť pop
        end;
    end;
    if (v=0) and not z.empty then z.pop(v,n,s);
  end;
  z.Free;
end;

Príklad:

prepíšeme rekurzívnu procedúru na kreslenie stromu pomocou korytnačej grafiky na nerekurzívnu: 

procedure TMojaKor.strom(n:integer; s:real);
begin
// časť 1:
  if n=0 then begin
    Dopredu(s); Dopredu(-s);
  end
  else begin
    Dopredu(s); Vlavo(45);
    strom(n-1,s*0.6);
// časť 2:
    Vpravo(90);
    strom(n-1,s*0.7);
// časť 3:
    Vlavo(45); Dopredu(-s);
  end;
end;

nerekurzívna verzia:

 
procedure TMojaKor.stromN(n:integer; s:real);
var
  z:TStack;
  v:integer;
begin
  z:=TStack.Create; z.push(1,n,s);
  while not z.empty do begin
    z.pop(v,n,s);
    case v of
      1:
        if n=0 then begin
          Dopredu(s); Dopredu(-s);
        end
        else begin
          Dopredu(s); Vlavo(45);
          z.push(2,n,s);
          z.push(1,n-1,s*0.6);
        end;
      2:
        begin
          Vpravo(90);
          z.push(3,n,s);
          z.push(1,n-1,s*0.7);
        end;
      3:
        begin
          Vlavo(45); Dopredu(-s);
        end;
    end;
  end;
  z.Free;
end;
  • Touto "zásobníkovou" metódou nevieme robiť funkcie. V nasledujúcom príklade si to ukážeme na Fibonacciho postupnosti. Definovaná je rekurentne takto:
          F(0)=1; F(1)=1; F(N)=F(N-1)+F(N-2) pre N>1

rekurzívna procedúra, ktorá počíta N-té Fibonacciho číslo: 

var
  ff:integer;       // globálna premenná, v ktorej je vypočítaná hodnota

procedure fib(n:integer);
var
  f:integer;
begin
//časť 1:
  if n<2 then ff:=1
  else begin
    fib(n-1);
//časť 2:
    f:=ff;
    fib(n-2);
//časť 3:
    ff:=ff+f;
  end;
end;

nerekurzívny tvar predchádzajúcej procedúry (TPrvok v TStack je už teraz iného typu):

 
procedure fibN(n:integer);
var
  f,v:integer;
  z:TStack;
begin
  z:=TStack.Create; z.push(1,n,f);
  while not z.empty do begin
    z.pop(v,n,f);
    case v of
      1:
        if n<2 then ff:=1
        else begin
          z.push(2,n,f);               // návrat
          z.push(1,n-1,f);             // rekurzívne volanie
        end;
      2:
        begin
          f:=ff; z.push(3,n,f);       // návrat
          z.push(1,n-2,f);            // fib(n-2)
        end;
      3: ff:=ff+f;
    end;
  end;
  z.Free;
end;

Príklad:

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

procedure TMojaKor.vlocka(n:integer; s:real);
begin
  if n=0 then Dopredu(s)
  else begin
    vlocka(n-1,s/3);
    Vpravo(60);
    vlocka(n-1,s/3);
    Vlavo(120);
    vlocka(n-1,s/3);
    Vpravo(60);
    vlocka(n-1,s/3);
  end;
end;

nerekurzívna verzia: 

procedure TMojaKor.vlockaN(n:integer; s:real);
var
  z:TStack;
  v:integer;
begin
  z:=TStack.Create; z.push(1,n,s);
  while not z.empty do begin
    z.pop(v,n,s);
    case v of
      1:
        if n<=0 then Dopredu(s)
        else begin
          z.push(2,n,s); z.push(1,n-1,s/3);
        end;
      2:
        begin
          Vpravo(60); z.push(3,n,s); z.push(1,n-1,s/3);
        end;
      3:
        begin
          Vlavo(120); z.push(4,n,s); z.push(1,n-1,s/3);
        end;
      4:
        begin
          Vpravo(60); z.push(1,n-1,s/3);
        end;
    end;
  end;
  z.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  k:TMojaKor;
  i:integer;
begin
  k:=TMojaKor.Create;
  for i:=1 to 3 do begin k.vlockaN(4,100); k.vlavo(120); end;
  k.Free;
end;

Aritmetické výrazy

  • v matematike aj v programovaní je zvykom používať tzv. infixový zápis aritmetických výrazov; je definovaný nasledovne:
    • operand (napr. číslo alebo premenná) je infixový výraz
    • ak X a Y sú infixové výrazy, tak infixovými výrazmi sú aj
          -X (X) X+Y X-Y X*Y X/Y
    • pri vyhodnocovaní sa využíva obvyklá precendencia operátorov
  • v istých (programátorských) aplikáciách sa využíva aj Poľský zápis, buď prefix alebo postfix (tzv. prevrátený Poľský zápis)

Prefix:

  • operátor je pred operandami
  • napr. "+ 1 2" môžeme prečítať ako "sčítaj 1 a 2"

Postfix:

  • operátor je za operandami
  • napr. "1 2 +" môžeme prečítať ako "zober 1 a 2; potom ich sčítaj"

Poľské formy majú oproti infixu tú výhodu, že nepotrebujeme zátvorky na určenie precendencie operátorov - vždy je jednoznačne dané poradie vyhodnocovania.

Vďaka tomu je aj vyhodnocovanie takýchto výrazov veľmi jednoduché (pomocou zásobníka).

Napr.

  • pre infix: ( 3 + 4 ) * 5
  • prefix: * + 3 4 5           { používa sa v iných jazykoch, napr. LISP }
  • postfix: 3 4 + 5 *

Problémy s unárnym operátorom "-", treba ho rozlíšiť od binárneho "-", zvykne sa značiť iným znamienkom (napr. s bodkou alebo "_").

program na vyhodnotenie postfixu načítaného zo vstupu:

 
...
uses StackUnit;     // type TPrvok = integer;

...

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
var
  z:TStack;
  x,y,i:integer;
  s:string;
begin
  if Key<>#13 then exit;
  z:=TStack.Create;
  s:=Edit1.Text; Edit1.Text:='';
  i:=1;
  while i<=Length(s) do begin
    case s[i] of
      '0'..'9':
        begin
          x:=0;
          while s[i] in ['0'..'9'] do begin
            x:=x*10+ord(s[i])-ord('0'); inc(i);
          end;
          z.push(x); dec(i);
        end;
      '_': begin z.pop(x); z.push(-x) end;           // unárne mínus
      '+': begin z.pop(x); z.pop(y); z.push(y+x) end;
      '-': begin z.pop(x); z.pop(y); z.push(y-x) end;
      '*': begin z.pop(x); z.pop(y); z.push(y*x) end;
      '/': begin z.pop(x); z.pop(y); z.push(y div x) end;
    end;
    inc(i)
  end;
  z.pop(x); z.Free;
  Memo1.Lines.Add(s+' = '+IntToStr(x));
end;

NDÚ:

  • upravte program na postfix s reálnou aritmetikou
  • vyhodnotiť prefix
  • prepis infixu do postfixu, 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))
    kvôli precendencii operátorov
    • urobte prevody z/do úplne uzátvorkovaného do/z pre/post-fixu
    • vyhodnoťte úplne uzátvorkovaný výraz
  • prepis prefixu do postfixu a naopak
  • vyhodnocujte výrazy s premennými, príp. s unárnymi funkciami (spracujú sa rovnako ako unárne mínus)

RAD - QUEUE, FRONT, FIFO

  • dátová štruktúra, postupnosť položiek zoradených za sebou,
  • ak príde nová položka, pridá sa na koniec radu (rear, tail, chvost)
  • vyberať položky zo začiatku radu (front, head, hlavička)
  • metódy:
    • serve = obslúž
    • append = pridaj na koniec

QueueUnit.pas: 

unit QueueUnit;

interface

type
  TQPrvok = string;
  TQueue = class
    q:array of TQPrvok;
    constructor Create;
    procedure serve(var p:TQPrvok);
    procedure append(p:TQPrvok);
    function empty:boolean;
  end;

implementation

uses
  Dialogs;

procedure chyba(const s:string);
begin
  ShowMessage(s); halt;
end;

constructor TQueue.Create;
begin
  q:=nil;
end;

procedure TQueue.serve(var p:TQPrvok);
begin
  if empty then chyba('Rad je prazdny');
  p:=q[0];
  q:=copy(q,1,maxint);
end;

procedure TQueue.append(p:TQPrvok);
begin
  SetLength(q,Length(q)+1);
  q[High(q)]:=p;
end;

function TQueue.empty:boolean;
begin
  Result:=q=nil;
end;

end.
  • Napíšeme program, ktorý číta textový súbor iba raz a vytvára nový súbor tak, že v tomto súbore sú všetky riadky vstupného súboru a za nimi ešte raz tie isté riadky:

zdvojený súbor:

 
...
uses
  QueueUnit;

...

procedure TForm1.Button1Click(Sender: TObject);
var
  q:TQueue;
  f,g:TextFile;
  t:TQPrvok;
begin
  q:=TQueue.Create;
  AssignFile(f,'Unit1.pas'); Reset(f);
  AssignFile(g,'test.pas'); Rewrite(g);
  while not eof(f) do begin
    readln(f,t); q.append(t); writeln(g,t);
  end;
  while not q.empty do begin
    q.serve(t); writeln(g,t)
  end;
  CloseFile(g); CloseFile(f);
  q.Free;
  Memo1.Lines.Add('hotovo');
end;

NDÚ:

  • prerobte triedu TQueue tak, aby sa nie pri každej operácii append alebo serve musela meniť veľkosť dynamického poľa q, 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
  • reprezentácia radu v poli:
    • cyklické pole - tvárime sa, že statické pole, čo máme k dispozícii, je cyklické, t.j. keď by chvost prišiel na koniec poľa, presunieme ho znovu na začiatok
    • problémy s rozpoznaním prázdneho a plného radu, riešenie - pamätáme si počet položiek
  • prerobte triedu TQueue tak, aby ste využili cyklické pole (musíte dodefinovať aj metódu full)
  • rozmýšľať o viac zásobníkoch a radoch, napr. vzájomná simulácia, triedenie pomocou dvoch zásobníkov, zarážka vo fronte, ...

© 2002 AB, KVI
blaho@fmph.uniba.sk