Ciele:

Úloha

Vypracujte aplikáciu, ktorá z jedálneho lístka odfiltruje jedlá, ktorých názov neobsahuje zadaný reťazec.

Aplikácia najprv načíta reťazec, ktorý sa bude vyhľadávať v názvoch jedla. Potom aplikácia načíta jedálny lístok. Položka v jedálnom lístku sa skladá z názvu a ceny uvedených na samostatnom riadku. Ak sa načítanie položky nepodarí, prerušte načítanie. Ak názov jedla obsahuje zadaný reťazec, zobrazte celú položku aj s cenou. Názov jedla ale môže byť mierne skreslený. Na konci zobrazte počet všetkých úspešne načítaných položiek.

Mierna komplikácia je, že na zápis názvu alebo vyhľadávanej suroviny sa používa neštandardný "Hack3r scr1pt", ktorý získava čoraz väčšiu popularitu na sociálnych sieťach. Hacker 5cript sa riadi nasledovným pravidlom - je možné ľubovoľne nahradiť veľké písmená za malé a niektoré písmená za čísla:

0 <=> o
1 <=> i
2 <=> z
3 <=> e
4 <=> a
5 <=> s
6 <=> b
7 <=> t
8 <=> b
9 <=> q

Oštiepkovú pizzu teda môžme zapísať ako:

Ostiepkova pizza
05t13pkova pizza
05t13pkova p1zz4

Príklad použitia programu

Na prvom riadku sa nachádza reťazec na vyhľadávanie. Na ďalších riadkoch sa nachádzajú položky jedálneho lístka v ktorom sa ma vyhľadávať. Jedna položka jedálneho lístka sa skladá z názvu jedla (reťazec) a ceny (reálne číslo).

Príklad na vstup:

bryndz
8rynd20va P1zza
7.50
Ja8lkov4 Pizza
6.50
5penatov3 kal2on3
8.20

Na výstupe programu zobrazte výzvu na zadanie reťazca na vyhľadávanie a výzvu na zadanie jedálneho lístka. Po načítaní a vyhľadávaní zobrazte položky, ktoré vyhovujú vyhľadávacej požiadavke. Na konci vypíšte počet úspešne načítaných položiek.

Výstup:

Zadaj hladanu surovinu:
Zadaj jedalny listok:
8rynd20va P1zza
7.50
Nacitanych 3 poloziek.

Vstup si môžte poznačiť aj do textového súboru vstup.txt aby ste to pri ručnom ladení nemuseli stále vypisovať.

./program < vstup.txt

Ako na to

Pri návrhu riešenia sa snažte celú úlohu rozdeliť na jednoduchšie čiastkové úlohy.

Budete potrebovať:

• vytvoriť štruktúru na uloženie jednej položky jedálneho lístka.
• načítať reťazec pomocou fgets
• implementovať algoritmus naivného vyhľadávania v reťazci
• premeniť reťazec na číslo s desatinnou čiarkou pomocou strtof alebo sscanf.
• overiť úspešnosť načítania alebo premeny pomocou overovania návratovej hodnoty.
• vytvoriť funkciu na transformáciu znaku do normalizovanej podoby "Hacker Scriptu".

Zopakujte si

• program vieme preložiť pomocou prekladača gcc program.c -o program,
• proces prekladu si vieme zjednodušiť pomocou Makefile a príkazu make
• správu vypisujeme pomocou funkcie printf()
• ak chceme použiť funkciu pre prácu s terminálom, musíme priložiť hlavičkový súbor <stdio.h>.
• Ako prvá sa v programe automaticky vyvolá funkcia main().
• Koniec riadka je vyznačený znakom \n.
• Reťazec je pole znakov zakončené nulou.
• Názov poľa je smerník na jeho začiatok.

Určíme, ako uložíme údaje v pamäti

Najpr musíme povedať ako uložíme údaje v pamäti. Na uloženie viacerých položiek je najjednoduchšie použiť pole. Po poľa si uložíme všetky záznamy v jedálnom lístku.

Informácia o jednej pizzi v jedálnom lístku sa bude skladať z názvu a (reťazec) a ceny (desatinné číslo). To sa musí zmestiť do jednej bunky poľa. Na to musíme navrhnúť vhodný dátový typ (štruktúru). Definícia štruktúry a funkcia na načítanie jednej položky sa vám zíde aj v ďalšom cvičení.

// Toto zapíšeme na začiatok súboru, ešte pred funkciu main()
#define LINESIZE 100
struct pizza {
    float prize;
    char name[LINESIZE];
};

Pamäť pre uloženie jednej položky bude vyzerať takto:

struct pizza tuniakova;

struct pizza nulova;
// Nastavíme všetky bajty pamäte na nulu
memset(&tunikova, 0,sizeof(struct pizza));
// Alebo staticky priradime nejake hodnoty
struct pizza tuniakova = {
    .name="Tuniakova",
    .prize=2.3
};
// Pozor, táto inicializácia funguje iba na novších prekladačoch

Na uloženie viacerých záznamov typu struct pizza použijeme pole:

struct pizza jedalny_listok[POCET_JEDAL];
// Na začiatku celé pole vynulujeme, všetky pizze sú nulové
memset(jedalny_listok, 0,sizeof(struct pizza)*POCET_JEDAL);

Vytvorte funkciu na načítanie jednej položky jedálneho lístka

Vytvoríme si pomocnú funkciu na načítanie jednej položky jedálneho lístka do pamäte. Ak vieme správne načítať jednu položku, tak vieme správne načítať všetky.

Na načítanie do konkrétneho miesta do pamäte musíme využiť jeho adresu. Adresu si vieme poznačiť do smerníkovej premennej. Adresa prvého miesta v poli je:

struct pizza *prva = jedalny_listok;

Adresa druhého miesta v poli:

struct pizza *druha = jedalny_listok + 1;

Pre zistenie adresu ľubovoľného miesta môžeme využiť aj operátor pre n-té miest v poli [] a operátor pre zistenie adresy &:

struct pizza *tretia = &jedalny_listok[2];

Funkcia na načítanie do konkrétneho miesta bude spĺňať tento predpis:

int read_pizza(struct pizza* item);

Pomocou návratovej hodnoty bude signalizovať či sa načítanie podarilo alebo nepodarilo. Funkcia vráti nulu, ak je záznam o pizzi neplatný a ukončuje jedálny lístok. Funkcia vráti nenulovú hodnotu ak sa načítanie mena aj ceny podarilo.

Argument item je miesto v pamäti, kde sa má načítať záznam. Dátový typ item je smerník na štruktúru. Pomocou operátora -> vieme pristupovať k členom štruktúry ako keby to bola klasická premenná:

printf("%s má cenu %.2f\n",item->name,item->prize);

Do tela funkcie doplňte kód pre načítanie.

Najprv načítajte riadok s názvom do pomocného poľa podľa kódu ktorý už máte. Ak sa načítanie podarí, načítajte ďalší riadok do nového poľa, ktorý obsahuje zápis čísla s desatinnou čiarkou. Ak sa načítanie riadku podarí, skúste znaky premeniť na číslo s desatinnou čiarkou pomocou funkcie strtof:

float value = strtof(line2);
// Ak je návratová hodnota nula, premena reťazca sa nepodarila.
if (value == 0.0F){
   return 0;
}

Ak sa podarilo načítanie názvu aj ceny, skopírujte načítané hodnoty a signalizujte úspech.

item->prize = value;
strcpy(item->name, line);
return 1;

Overte si výsledok

Upravte program tak, aby načítal prvý riadok do poľa a potom v cykle postupne načítavajte záznamy o pizzi až pokiaľ nenatrafíte na neplatný záznam. Ak je záznam platný, vypíšte ho:

struct pizza item;
int counter = 1;
while(read_pizza(stdin,&item)){
    counter += 1;
    printf("%s",item->name);
    printf("%.2f",item->prize);
}

Pár krát vyskúšajte Váš program aby ste sa uistili, že funguje správne. Použite aj poocníka valgrind aby ste overili prácu s pamäťou.

Implementujte vyhľadávanie

V ďalšom kroku si napíšeme funkciu, ktorá označí záznamy z jedálneho lístka, ktoré neobsahujú zadaný reťazec.

Najpr potrebujeme vyriešiť vyhľadávanie v ľubovoľných reťazcoch. Na to potrebujeme funkciu, ktorá bude vyhľadávať reťazec (označíme ho needle) v zadanom reťazci (heap).

int search_string(const char* heap, const char* needle);

Funkcia bude využívať dve slučky. Jedna z nich bude prechádzať reťazec heap a druhá needle. V prípade, že reťazec needle sa nachádza v reťazci heap, funkcia vráti index jeho začiatku. V prípade, že reťazec nenašla, vráti -1.

Viac informácií o tomto algoritme nájdete pod heslom "naive string search"

Pri práci s indexami a poliami dávajte pozor, aby ste nepracovali s pamäťou mimo vyhradeného rozsahu. Dávajte pozor ak sa v tele slučky nachádza odčítanie alebo pripočítanie k indexu. Takýto program bude určite nesprávny:

int pole[5]="abcd";
for (int i = 0; i < 5; i++){
  printf("%c",pole[i+1]);
}

Zlepšite vyhľadávanie tak, aby bralo do úvahy skreslenie

Upravte vyhľadávanie tak, aby bralo do úvahy rôzne možné podoby znakov. Funkcia by mala ľubovoľný znak premeniť do normalizovanej podoby ktorá berie do úvahy vlastnosti Hacker Scriptu.

Môže vyzerať napr. takto:

char hacker_script(char c);

Vo vnútri funkcie definujte pravidlá na prepis znaku do Hacker scriptu:

• Ak je znak veľký, prepíšte ho na malý;
• Ak je znak v zozname "špeciálnych znakov", tak ho prepíšte do pôvodnej podoby.

Pravidlo nahradí všetky veľké písmená za malé a niektoré písmená za čísla podľa tabuľky:

Pôvodný znak	Zakódovaný znak
o	0
i	1
z	2
e	3
a	4
s	5
b	6
t	7
b	8
q	9
veľké písmeno	malé písmeno

Porovnanie potom robíte v oblasti zakódovaných znakov.

Je pravda že možností zápisu pôvodného reťazca je viac. To ale nevadí, lebo funkcia pre kódovanie bude prepisovať viaceré možnosti prepísať na práve jednu.

Napr.

Ostiepkova pizza => 05t13pkova p1zz4

Ostiepkova pizz4 => 05t13pkova p1zz4

O5tiepkova pizz4 => 05t13pkova p1zz4

a tak ďalej.

Pred vyhľadávaním stačí aplikovať prepisovaciu funkciu na oba reťazce a je to.

Aby ste vo funkcii nemali príliš veľa podmienok, uložte si špeciálne znaky do poľa a použite cyklus na vyhľadávanie v poli:

char numbers[] = "0123456789";
char letters[] = "oizeasbtbq";
for (int i = 0; i < 10; i++){
    if (c == numbers[i]){
        return letters[i];
    }
}

K tomuto kódu pridajte premenu všetkých veľkých znakov na malé. Túto funkciu Vám stačí aplikovať na každý znak vo vyhľadávacom algoritme.

Odovzdanie

• do 5.10.2023 do súboru 'cv1/program.c' v repozitáti usaa23 na GITe
• max 5 bodov, automatické hodnotenie Traktor

Vytvorte si GIT repozitár s názvom usaa23. Viditeľnosť repozitára nastavte na Private aby ste ochránili unikátnosť Vášho riešenia. V repozitári si vytvorte adreár cv1 a v ňon súbor program.c. Ǩed budete mať funkčnú verziu, odošlite súbor pomocou príkazu git push.

Automatické hodnotenie získate pomocou systému Traktor. Prihláste sa pomocou Vašich školských prihlasovacích údajov.

Next Post