====== Cvičení 8, Fronta, zásobník ======

===== náplň cvičení =====

==== Úkol 1: třídění karet ====

Uvažujme [[ https://en.wikipedia.org/wiki/Playing_card#/media/File:Svg-cards-2.0.svg |  hrací karty ]].

  * Máme karty čtyř barev, každá barva má dále karty 2,3,4,5,6,7,8,9,10,J,Q,K,A
  * Kartu budeme reprezentovat 1D polem, kde:
     *  první prvek je barva karty (0,1,2,3). Tento prvek bude ''int''
     *  druhý prvek je typu ''string'' a je to hodnota karty, tedy např. "Q" nebo "1"
     * Příklad karty: ''[1,"2"], [2,"A"], [0,"K"]''
  * Pořadí karet v dané barvě je toto: 2,3,4,5,6,7,8,9,10,J,Q,K,A, kde
     * 2 má nejmenší hodnotu
     * A má největší hodnotu
     * platí že $2<3$, $3<4$, ... Q $<$ K, J $>$ 10, atd.
    
Napište funkci, který **vzestupně** třídí karty podle jejich barvy a podle jejich hodnoty.
   * na vstupu je seznam (pole) karet
   * funkce vrátí setříděné pole tak, že na začátku budou karty barvy 0, pak karty barvy 1,atd., přičemž v každé skupině budou karty setříděny podle jejich hodnot.
   * Využijte bublinkové třídění, nebo Vaše oblíbené třídění z přednášky
   * Příklad: 
  
<code python>  
cards = [  [3,"A"],  [3,"Q"],  [0,"2"],  [1,"10"]  ]
</code>

výsledek pro setřídění:

<code python>
[  [0, "2"],  [1, "10"],  [3, "Q"],  [3, "A"]  ]
</code>

Seřaďte toto pole:

<code python>
cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]
</code>

==== Úloha 2 Dekódování zprávy ====
  * Dekódujde zprávu ze standardního vstupu pomocí zásobníku:
    * Písmeno znamená push znaku na zásobník
    * Hvězdička znamená pop znaku ze zásobníku na výstup
    * Mezery se ignorují
  * Dekódujte následující vstup
<code>
T E * A * Q Y S * * * S E U * * * * N I * O * * 
</code>

==== Úloha 3 Flood fill ====
  * Napište program, který v zadané matici nahradí souvislou oblast 0 ze zadaného bodu hodnotou 2.
  * Matici vezměte jako vnitřní proměnnou:
<code=python>
m=[
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,1,0,1,0,0,0,1],
[0,0,1,0,0,0,1,0,1,0],
[0,0,1,0,0,0,0,1,0,0],
[0,0,1,1,0,1,0,0,0,0],
[0,0,1,0,1,1,1,1,0,0],
[0,0,1,0,0,1,0,1,1,1],
[0,0,1,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,0,0] ]
</code>
  * Program si načte počáteční bod ze standardního vstupu
  * Do zásobníku vložíte vstupní bod
  * Opakuje, dokud není zásobník prázdný:
    * pro každý bod (x,y) ze zásobníku, pokud je hodnota matice v tomto bodu 0 proveďte:
      * pokud jsou body (x-1,y),(x+1,y),(x,y-1),(x,y+1) v matici a jejich hodnota je 0, pak je vložte do zásobníku
  * Vytiskněte výslednou matici
  * Program otestujte pro vstupy: 4,4 a 9,9
  * Co by se stalo, pokud byste na zásobník vložili i body (x-1,y-1),(x+1,y+1),(x+1,y-1),(x-1,y+1)?
  * Jaká je složitost tohoto algoritmu? Uměli byste tento algoritmus zefektivnit, aby nevkládal jedno pole matice do zásobníku vícekrát?


===== domácí práce =====

==== Lehká varianta ====
  * Napište program **postfix.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standardní zápis výrazů, jak jste zvyklí ze školy) do postfixového zápisu ([[https://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace|reverzní polská notace]]) s využitím algoritmu [[https://cs.wikipedia.org/wiki/Shunting-yard_%28algoritmus%29|shunting yard]]. 
  * Vstupní výraz může obsahovat pouze celá kladná čísla, mezery, závorky (, ) a operace +,-,*,/, <nowiki>**</nowiki>. (Priorita +,- je nižší než priorita operací *,/, nejvyšší prioritu má mocnění <nowiki>**</nowiki>)
  * Váš program musí zkontrolovat, že je vstup ve správném formátu, a pokud není, pak vytiskne ERROR (příklady chybných vstupů jsou 1 + * 2, 11 22 -, / 10 20, 1+( 2 - 3 ) 4)
  * Program v souboru **postfix.py** odevzdejte do odevzdávacího systému (úloha HW08).



  * Vstup: 
<code>
3 + 4 * 2 / ( 1 - 5 )
</code>
  * převede na výstup 
<code>
3 4 2 * 1 5 - / +
</code>

==== Těžká varianta ====

  * Napište program **pretoin.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Prefixov%C3%A1_notace|prefixové notace]] do [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] 
  * Vstupní výraz může obsahovat pouze celá kladná čísla, mezery, a operace +,-,*,/,<nowiki>**</nowiki>. (Operace <nowiki>**</nowiki> je mocnina a má nejvyšší prioritu, nejnižší prioritu mají operace +,-, prostřední prioritu *,/)
    * Jakmile se na vstupu vyskytnou dvě hvězdičky bez mezery <nowiki>**</nowiki>, jedná se o mocninu. Dvě hvězdičky s mezerou jsou dvě násobení <nowiki>* *</nowiki>.
    * Operace +,-,*,/ se vyhodnocují zleva, operace <nowiki>**</nowiki> se vyhodnocuje z prava (stejně jako je to v Pythonu)
  * Při převodu musíte otestovat správnost zadaného výrazu a pokud je formát chybný, pak vytisknete ERROR
  * Složitost této úlohy je ve správném doplnění závorek, které musí zaručit správné vyhodnocení zleva doprava, ale nesmíte závorky používat zbytečně
  * Vstup může obsahovat vložené mezery (mezi dvěma číselnými argumenty je mezera samozřejmě povinná), výstup nebude obsahovat žádné mezery.
  * Program v souboru **pretoin.py** odevzdejte do odevzdávacího systému (úloha HW08). 
=== Příklad ===
  * Vstup 
<code>
--1 2 3
</code>
    * převede na výstup:
<code>
1-2-3
</code>
    * Vstup 
<code>
-1-2 3
</code>
    * převede na výstup:
<code>
1-(2-3)
</code>