Cvičení 9, Fronta, Stavový automat

• 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

• 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

a='b\'c#d' #e
i="j\"k'l#m" #n

• Program z přednášky:

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

• Reálné číslo v pythonu je zadána touto EBNF gramatikou:

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"

• Vymyslete a naprogramujte stavový automat, který bude zjišťovat, zda je řetězec na řádce reálným číslem.

• 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:

aa[bb(cc)dd(ee)fff[gggg]]hhh

• převede na výstup:

()cc
()ee
[]gggg
[]bbddfff

• písmena 'aa' a 'hhh' se zahodí, nejsou uvnitř žádných závorek

• 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:

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 }

• 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 studium_test1.txt bude:

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.

• 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

#define MIN_VALUE -1.0f
#define normalize(_x) _x - MIN_VALUE

• #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ů '//' do konce řádky
    • od znaků '/*' do znaků '*/' i přes více řádků
    • předpokládejte, že komentáře nebudou vzájemně vnořeny, tedy situace /* /* */ */, nebo /* // */ 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 \".
• 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.

• Následující vstup

#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);

• převede preprocessor.py na následující výstup:

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);

• 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.