====== Cvičení 9, Fronta, Stavový automat ======

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

==== Úloha 1 Fronta ====

  * Přeměňte řešení úlohy 3 Flood fill z cvičení 8 na frontu.
  * Postupnou animací zjistěte jak se změnilo vyplňování prostoru
  * Zjistěte, zda potřebuje více paměti zásobník, nebo fronta

==== Úloha 2 Komentáře - rozšíření ====

  * Upravte program na odstraňování komentářů z přednášky tak:
    * aby program bral v úvahu řetězce začínající a končící znakem '
    * aby správně interpretoval znaky \' a \"
    * aby pokud řádka končí znakem \ dovedl řetězec prodloužit přes více řádek
  * Program otestujte na následujících datech
<code>
a='b\'c#d' #e
i="j\"k'l#m" #n
</code>
  * Program z přednášky:
<code python>
def preskoc_komentare(line):
  # vytiskne obsah souboru 'f' s vynechanymi komentari
  stav=0          # počáteční stav automatu
  for c in line:  # přečti jeden znak
    if stav==0:   # počáteční stav
      if c=="#":  # začátek komentáře
        stav=1
        continue        
      elif c=='\"':
        stav=2    # začátek řetězce
    elif stav==1: # 1="komentar"
      continue
    elif stav==2:
      if c=='\"':
        stav=0
    print(c,end="") # vytiskni znak

i=input()
preskoc_komentare(i)  # nacti radku a preskakuj
</code>
==== Úloha 3 Kontrola reálného čísla ====

  * Reálné číslo v pythonu je zadána touto [[https://cs.wikipedia.org/wiki/Rozvinut%C3%A1_Backusova-Naurova_forma|EBNF]] gramatikou:
<code BNF>
floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit { digit }
fraction      ::=  "." digit { digit }
exponent      ::=  ("e" | "E") ["+" | "-"] digit { digit }
digit         ::=  "0"..."9"
</code>
  * Vymyslete a naprogramujte stavový automat, který bude zjišťovat, zda je řetězec na řádce reálným číslem.
==== Úloha 4 Obsahy závorek ====
  * Uvažujme řetězec obsahující závorky () a [].
  * Napište program, který bude testovat, zda je výraz správně uzávorkován a zjistí text uvnitř závorek
  * Závorky mohou být do sebe vnořeny a pak text patří do poslední úrovně závorek
  * Program tedy text:
<code>
aa[bb(cc)dd(ee)fff[gggg]]hhh
</code>
  * převede na výstup:
<code>
()cc
()ee
[]gggg
[]bbddfff
</code>
  * písmena 'aa' a 'hhh' se zahodí, nejsou uvnitř žádných závorek

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

==== Lehká varianta:====
  * Napište program **students.py**, který načtěte databázi adres z textového souboru, jehož jméno je první argument programu, podle níže uvedeného formátu:
<code BNF>
zaznam      ::= cele_jmeno ";" studium
cele_jmeno  ::= jmeno "(" jmena ")" "{" rodne_prijmeni "}" prijmeni |
                jmeno "(" jmena ")" prijmeni |
                jmeno "{" rodne_prijmeni "}" prijmeni | 
                jmeno prijmeni
jmeno, rodne_prijmeni, prijmeni ::= pismeno { pismeno }
jmena       ::= jmeno { ","jmeno }
pismeno     ::= "a"..."z"|"A"..."Z"
studium     ::= typ "," rocnik "," obor
typ         ::= ( "Bc." | "Ing." | "Ph.D." )
rocnik      ::= cislo { cislo }
cislo       ::="0"..."9"
obor        ::= pismeno { pismeno }
</code>

  * Jeden záznam je vždy na jednom řádku, pokud záznam neodpovídá formátu data celý řádek se zahodí.
  * Mezi jednotlivými položkami záznamu může být i několik mezer.
  * Pokud záznam odpovídá formátu, vytiskne se na výstup informace o záznamu ve tvaru:
    * pokud má jen jedno křestní jméno:
      * příjmení, křestní jméno, obor, typ  
    * pokud má více křestních jmen (v tomto případě David a Václav, vytisknou se jen iniciály a tečka):
      * příjmení, D. V., obor, typ
  * Program odevzdejte do HW09. 
  * Výstup programu pro vstup ze souboru {{courses:b3b33alp:cviceni:studium_test1.txt|studium_test1.txt}} bude:
<code>
Novak, Jaroslav, oi, Bc.
Novak, J. D., kybernetika, Ph.D.
Novy, J. M. Z., robotika, Ing.
Nova, Jarmila, robotika, Ing.
Novak, Jara, kybernetika, Ph.D.
Novotny, J. D. I., robotika, Ing.
Nowotnny, Y. D. Y., robotika, Ing.
</code>


==== Těžká varianta:====
  * Proveďte předzpracování (pre-processing) programu v jazyce C.
  * Ve programu zadaném jako parametr Vašeho programu proveďte textové záměny:
    * ''#define name replacement''
    * ''#define name(x,y,z) replacement''
    * ''#undef aa''
    * ''#ifdef aa''
    * ''#endif''
    * odstraňte komentáře
  * Funkčnost těchto příkazů
    * ''#define řetězec zbytek_do_konce_řádky''
      * nadefinuje náhradu řetězce novým řetězce, který je definován za prázdnými znaky řetezce až do konce řádky
    * ''#define řetězec( seznam parametrů ) zbytek_do_konce_řádky''
      * nadefinuje náhrazu řetezce se zadanými parametry. Při náhradě budou parametry ve zbytku řádky nahrazeny zadanými řetězci
      * direktiva '#define' umožňuje volání dalších direktiv, tj. v řetězci ''zbytek_do_konce_řádky'' mohou být volána další makra
<code c>
#define MIN_VALUE -1.0f
#define normalize(_x) _x - MIN_VALUE
</code>
    * ''#undef řetězec''
      * zruší definici náhrady řetězec
    * ''#ifdef řetězec''
      * pokud je definována náhrada řetězec, pak následující řádky jsou kopírovány na výstup. Pokud není, jsou všechny řádky do příkazu ''#endif'' zahozeny
    * ''#endif'' 
      * ukončuje platnost předchozího příkazu ''#ifdef''

  * **Upřesnění zadání:**
    * Pokud řádek obsahuje definici výše uvedených příkazů, pak od začátku řádku do znaku # mohou být pouze mezery, nebo znak TAB.
    * Každý řádek může obsahovat nejvýše jeden příkaz
    * Při zadání senzamu parametrů příkazu #define nesmí být mezi koncem řetězce a znakem '(' mezera.
    * Příkazy #ifdef mohou být vnořeny
  * Náhrada se provádí v textu programu, který není komentářem a který není v řetězci
    * Komentáře v jazyce C jsou:
      * od znaků <nowiki>'//'</nowiki> do konce řádky
      * od znaků <nowiki>'/*'</nowiki> do znaků <nowiki>'*/'</nowiki> i přes více řádků
      * předpokládejte, že komentáře nebudou vzájemně vnořeny, tedy situace <nowiki>/* /* */ */</nowiki>, nebo <nowiki>/* // */</nowiki> nenastanou
      * veškerý text komentářů bude odstraněn a neobjeví se na výstupu 
    * Řetězce v jazyce C začínají znakem " nebo ' a končí stejným znakem. Řetězce v této úloze nemohou být přes více řádek, ale mohou obsahovat sekvence \' a <nowiki>\"</nowiki>.
  * Program **preprocessing.py** načte soubor zadaný jako vstupní parametr a vytiskne na výstup zpracovaný výstup, který obsahuje pouze aktivní řádky. 

  * Program odevzdejte do HW09.  

=== Příklad ===
  * Následující vstup
<code c>
#define MIN_VALUE -1.0f
#define _normalize(_x) ff((_x) - MIN_VALUE)
#define ff cos
float last_value = get_value();

#ifdef output
// Print if defined
std::cout << "Normalized: " << _normalize(last_value);
#endif

auto y = 2.0f * _normalize(atan2(last_value,-last_value)+0.5f);
#define MIN_VALUE -10.0f
#undef ff
auto y2 = 2.0f * _normalize(last_value);
</code>

  * převede preprocessor.py na následující výstup:
<code c>
float last_value = get_value();
 
 
auto y = 2.0f * cos((atan2(last_value,-last_value)+0.5f) - -1.0f);
auto y2 = 2.0f * ff((last_value) - -10.0f);
</code>
  * direktivy #define, #ifdef, #endif, #undef se netisknou, příkaz std::cout je v neaktivním bloku, v ostatních řádcích jsou pak nahrazená makra.