| Posledná zmena: 1.11.2002

zásobník, aritmetické výrazy

## Zásobník znakov

metóda top:
medzi metódy na prácu so zásobníkom pridáme novú funkciu top, ktorá vráti hodnotu na vrchu zásobníka, pričom v zásobníku ju ponechá |
    type
      TPrvok = char;
      TStack = class
        st:array of TPrvok;
        constructor Create;
        procedure push(p:TPrvok);
        procedure pop(var p:TPrvok);
        function top:TPrvok;
        function empty:boolean;
      end;
    ...
    function stack.top:TPrvok;
    begin
      if empty then chyba('Prázdny zásobník');
      Result:=st[High(st)];
    end;

- v nasledujúcich úlohách predpokladáme, že máme k dispozícii jednu znakovú premennú, jeden znakový zásobník a čítame jeden riadok textového súboru (ukončený napr. znakom #13). Úlohou je napísať funkciu, ktorá zistí, či vstupný riadok súboru je nejakého konkrétneho tvaru

najprv len a, potom rovnaký počet len b:
anbn, 0<=n |
    function test(var t:TextFile):boolean;
    var
      s:TStack;
      c:char;
    begin
      s:=TStack.Create;
      read(t,c);
      while c='a' do begin
        s.push(c); read(t,c);
      end;
      while (c='b') and not s.empty do begin
        s.pop(c); read(t,c);
      end;
      Result:=(c=#13) and s.empty;
      s.Free;
    end;
najprv len a, potom rovnaký alebo väčší počet b:
anbm, 0<=n<=m |
    function test(var t:TextFile):boolean;
    var
      s:TStack;
      c:char;
    begin
      s:=TStack.Create;
      read(t,c);
      while c='a' do begin
        s.push(c); read(t,c);
      end;
      while c='b' do begin
        if not s.empty then s.pop(c);
        read(t,c);
      end;
      Result:=(c=#13) and s.empty;
      s.Free;
    end;
je palindrom:
wcwr kde w je z abecedy {a,b} wr je zrkadlový obraz slova w |
    function test(var t:TextFile):boolean;
    var
      s:TStack;
      c:char;
    begin
      s:=TStack.Create;
      read(t,c);
      while c in ['a','b'] do begin
        s.push(c); read(t,c);
      end;
      if c='c' then begin
        read(t,c);
        while not s.empty and (c=s.top) do begin
          s.pop(c); read(t,c);
        end;
        Result:=(c=#13) and s.empty;
      end
      else Result:=false;
      s.Free;
    end;
rovnaký počet a a b:
#a = #b, rovnaký počet a-čok aj b-čok |
    function test(var t:TextFile):boolean;
    var
      s:TStack;
      c:char;
    begin
      s:=TStack.Create;
      read(t,c);
      while c in ['a','b'] do begin
        if s.empty or (c=s.top) then s.push(c)
        else s.pop(c);
        read(t,c);
      end;
      Result:=(c=#13) and s.empty;
      s.Free;
    end;
rovnaký počet a, b a c:
logická funkciu abc, ktorá vráti true, ak je vo vstupnom riadku rovnaký počet a-čok, b-čok a c-čok využite dve inštancie TStack okrem dvoch zásobníkov môžete použiť už len jednu znakovú pomocnú premennú |
    function abc(var t:TextFile):boolean;
    var
      s1,s2:TStack;
      c:char;
    begin
      s1:=TStack.Create; s2:=TStack.Create;
      read(t,c);
      while c in ['a','b','c'] do begin
        case c of
         'a':
           begin
            if s1.empty or ('a'=s1.top) then s1.push('a')
            else s1.pop(c);
            if s2.empty or ('a'=s2.top) then s2.push('a')
            else s2.pop(c);
           end;
         'b':
           if s1.empty or ('b'=s1.top) then s1.push('b')
           else s1.pop(c);
         'c':
           if s2.empty or ('c'=s2.top) then s2.push('c')
           else s2.pop(c);
        end;
        read(t,c);
      end;
      Result:=(c=#13) and s1.empty and s2.empty;
      s1.Free; s2.Free;
    end;

### Ďalšie úlohy

- anbicabs(n-i)
- vyriešte úlohu abc len pomocou jedného zásobníka - ak pritom využijete rekurziu, tak ste vlastne použili druhý zásobník

- môžete vyskúšať použitie jedného zásobníka a rekurzie

## Zásobník celých čísel

- máme definovaný zásobník celých čísel, t.j. TPrvok = integer;

vyhoď všetky nulové prvky:
pomocou pomocného zásobníka spracujte čísla v zásobníku tak, že vyhádžete všetky nulové prvky |
    procedure vyhod0(s:TStack);
    var
      p:TStack;
      i:integer;
    begin
      p:=TStack.Create;
      while not s.empty do begin
        s.pop(i);
        if i<>0 then p.push(i);
      end;
      while not p.empty do begin
        p.pop(i); s.push(i);
      end;
      p.Free;
    end;
nulové prvky zásobníka na spodok:
pomocou pomocného zásobníka spracujte čísla v zásobníku tak, že všetky nulové prvky premiestnite na spodok zásobníka |
    procedure presun0(s:TStack);
    var
      p:TStack;
      i,j:integer;
    begin
      p:=TStack.Create; j:=0;
      while not s.empty do begin
        s.pop(i);
        if i<>0 then p.push(i)
        else inc(j);
      end;
      while j>0 do begin
        s.push(0); dec(j);
      end;
      while not p.empty do begin
        p.pop(i); s.push(i);
      end;
      p.Free;
    end;

### Ďalšie úlohy

- naprogramujte takéto triedenie, ktoré využije dva zásobníky:

- na začiatku máme čísla v prvom zásobníku
- vyberieme prvé dve čísla, porovnáme ich - menšie z nich vložíme do druhého zásobníka
- vyberieme ďalšie číslo z prvého zásobníka - porovnáme ho s číslom, ktoré nám ostalo pri predchádzajúcom porovnávaní - menšie číslo vložíme do druhého zásobníka
- opakujeme, až kým prvý zásobník nie je prázdny (pri tomto presýpaní, sme mohli spočítať počet triedených čísel)
- teraz máme v druhom zásobníku všetky čísla, pritom na vrchu je najväčšie z nich
- podobne presypeme čísla z druhého zásobníka do prvého, ale teraz vkladáme do prvého zásobníka väčšie z porovnávaných čísel
- po dostatočnom opakovaní tohto algoritmu budú čísla v zásobníku utriedené

## Aritmetické výrazy

postfixový zápis:
7 4 * 9 2 4 - * 6 / +

- vyhodnoťte
- prepíšte do infixu a prefixu

    7 4 * 9 2 4 - * 6 / +
    (7 4 *) 9 (2 4 -) * 6 / +
    (7 4 *) (9 (2 4 -) *) 6 / +
    (7 4 *) ((9 (2 4 -) *) 6 /) +
    (7 * 4) + ((9 * (2 - 4)) / 6) = 25   ... infix
    + (* 7 4) (/ (* 9 (- 2 4)) 6)
    + * 7 4 / * 9 - 2 4 6 ... prefix

prefixový tvar:
+ * - + 1 2 3 4 * 5 - 6 + 7 8

- prepíšte do infixu a postfixu
- vyhodnoťte

    + * - + 1 2 3 4 * 5 - 6 + 7 8
    + (* (- (+ 1 2) 3) 4) (* 5 (- 6 (+ 7 8)))
    (((1 + 2) - 3) * 4) + (5 * (6 - (7 + 8)))
    (((1 2 +) 3 -) 4 *) (5 (6 (7 8 +) -) *) +
    1 2 + 3 - 4 * 5 6 7 8 + - * +
    = 45

infixový zápis:
3*(4+5)-6*7/(8+6)

- prepíšte do prefixu a postfixu

    3*(4+5)-6*7/(8+6)

    (3 * (4 + 5)) - ((6 * 7) / (8 + 6))
    - (* 3 (+ 4 5)) (/ (* 6 7) (+ 8 6))
    - * 3 + 4 5 / * 6 7 + 8 6
    (3 (4 5 +) *) ((6 7 *) (8 6 +) /) -
    3 4 5 + * 6 7 * 8 6 + / -

### Ďalšie úlohy

- navrhnite algoritmus na vyhodnocovanie výrazov v prefixovom tvare (asi sa použije jeden alebo aj viac zásobníkov)
- navrhnite algoritmus na vyhodnocovanie výrazu v tvare úplne uzátvorkovaného infixu (napr. nájdeme prvú pravú zátvorku, potom hľadáme ku nej prislúchajúcu ľavú, vyhodnotíme podvýraz medzi zátvorkami a nahradíme ho výsledkom)
- navrhnite algoritmus na prepis aritmetického výrazu z prefixového tvaru do postfixového tvaru

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