====== 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 (),{},[] ====