====== 9. Abstraktní datový typ, zásobník, fronta ====== ===== Zásobník ===== LIFO - Last In First Out

Obrázek převzat z https://commons.wikimedia.org/wiki/File:Lifo_stack.svg


class Zasobnik:
    def __init__(self,data=[]):
        self.data = data
    
    def push(self,item):
        self.data += [item]
    
    def pop(self):
        if self.data: # true pokud self.data != [], alternativa len(self.data)
            return self.data.pop(-1)
        else:  # pokud self.data == []
            return None

    def is_empty(self):  # zjisti, jestli je zasobnik prazdny
        return self.data == []  # alternativa return len(self.data)


s = Zasobnik()

N = 4
for i in range(N):
    print("zapisuji do zasobniku cislo: {}".format(i))
    s.push(i)  #

for i in range(N+1):
    print("vycitam ze zasobniku cislo: {}".format(s.pop()))

==== Úloha 1 - Dekódujte zprávu ze standardního vstupu pomocí zásobníku: ====


* Písmeno znamená *push* znaku (toho písmena) do zásobníku
* Hvězdička znamená *pop* znaku ze zásobníku na výstup
* Pokud je znak malé písmeno, před vložením do zásobníku jej převeďte na velké písmeno
* Jiné znaky se ignorují

* Dekódujte vstup ''%%TE*A*QYS***SEU****ni*O**%%''


zprava = 'TE*A*QYS***SEU****ni*O**'

s = Zasobnik()

#

==== Úloha 2 - Napište program, který s využitím zásobníku zkontroluje zda výraz obsahuje párové závorky (). ====


s = Zasobnik()

vyraz = 'asdfdasfdsa)()'

#

==== Úloha 3 - Převod čísla do zvolené číselné soustavy ==== Pomocí zásobníku realizujte funkci, která převede dekadické číslo do zvolené číselné soustavy

==== Úloha 4 - Napište program, který bude fungovat jako prefixový kalkulátor ==== * Ze škol známá infixová notace je například: ''%%(4 - 1) x 5%%'' * V přednáškách máte příklad na postfixovou notaci * Prefixovou notací bychom stejný příklad zapsali jako: ''%%x - 4 1 5%%'' * Nejrpve se počítá ''%%4 - 1%%'' a výsledek se zapíše místo trojice znaků ''%%- 4 1%%'', čímž dostaneme: ''%%x 3 5%%'' * Nakonec se spočítá ''%%3 x 5%%'' a výsledek je ''%%15%%'' * K implementaci je možné využít zásobník a postupně procházet sekvenci argumentů od zadu * Pokud argument je číslo, vkládáme jej do zásobníku * Pokud argument je operátor, vyjmeme dvě naposled vložená čísla ze zásobníku a provedeme matematickou operaci, jejíž výsledek vložíme do zásobníku * Po projití všech argumentů zbyde v zásobníku výsledek

===== Fronta ===== FIFO - First In First Out

Obrázek převzat z https://cs.m.wikipedia.org/wiki/Soubor:Data_Queue.svg


class Fronta:
    def __init__(self,data=[]):
        self.data = data
    
    def enque(self,item):
        self.data += [item]
    
    def deque(self):
        if self.data: # true pokud self.data != [], alternativa len(self.data)
            return self.data.pop(0)
        else:  # pokud self.data == []
            return None

    def is_empty(self):  # zjisti, jestli je zasobnik prazdny
        return self.data == []  # alternativa return len(self.data)


s = Fronta()

N = 4
for i in range(N):
    print("zapisuji do fronty cislo: {}".format(i))
    s.enque(i)  #

for i in range(N+1):
    print("vycitam z fronty cislo: {}".format(s.deque()))

===== Úlohy ve zbytku cvičení nebo na doma ===== ==== Úloha 5 - Rozšiřte program z úlohy 2 tak, aby fungoval také pro další párové závorky (),{},[] ====