Kurz jazyka C - 9. díl

Vítám Vás u dalšího (pravděpodobně předposledního) pokračování našeho povídání o jazyce C. Dnes zdárně dokončíme to, co jsme minule načali.

Minule jsme vytvořili základ funkce RozeberVyraz, která měla zadaný řetězec rozložit na jednotlivé elementy. Zatím jsme se stále omezovali na výrazy obsahující pouze sčítání a násobení (s případnými závorkami vyznačujícími prioritu). Část, kterou jsme vytvořili, prošla zadaný řetězec a rozdělila jej na jednotlivé elementy - sčítance v 1. úrovni, popř. součinitele v 2. úrovni. Neukázali jsme si však, jak tyto jednotlivé elementy dále zpracovat jedná se totiž opět o samostatné výrazy (např. v závorce můžete mít opět libovolný výraz obsahující sčítání a násobení). To nás čeká právě teď.
Jak jste si jistě všimli, typ výrazu byl vždy určen již při jeho vytváření. Nyní tedy stačí projít vytvořené elementy (= parametry nadřazené operace dané parametrem vyraz, například jednotlivé sčítance). Podle typu elementu budeme pokračovat v jeho zpracování různým způsobem. Zatím uvažované typy zahrnují TE_NASOBENI (násobení), TE_ZAVORKY (výraz v závorkách) a TE_CISLO (číslo v dekadickém zápisu). Vše je opět realizováno pomocí for-cyklu, nebol potřebujeme projít všechny vytvořené elementy. Ukazatel na první parametr = element výrazu jsme uložili do položky parametr struktury vyraz. Stačí tedy použít již nepotřebný ukazatel aktualni, přiřadit mu na počátku ukazatel na první uzel seznamu parametrů a po té vše projít (ukazatel na následující uzel v seznamu je v položce dalsi). Jak víme, poslední uzel seznamu jsme si označili tím, že položka dalsi obsahuje NULL. Při volbě akce pro daný element nám opět pomůže příkaz pro selekci switch opět vybíráme jednu z možností dle typu výrazu (později mohou přibýt různé funkce apod.). Volba je prováděna na základě položky typ ve struktuře Element. Popisovaná část funkce RozeberVyraz je uvedena na jiném místě této dvoustrany.
V případě, že se jedná o číslo (TE_CISLO), stačí ono číslo převést z dekadického zápisu v části řetězce s výrazem na číslo v plovoucí desetinné čárce. Pozice v řetězci je stejně jako u všech dosud nerozebraných výrazů určena položkami zacatek a konec ve struktuře Element. Stačí tedy použít knihovní funkci sscanf (totéž jako scanf, ale načítá formátovaný vstup z řetězce místo z klávesnice). Číslo si ukládáme do položky cislo.
Pokud náš sčítanec byl součin (TE_NASOBENl), je třeba jej rozdělit na jednotlivé součinitele - to můžeme provést pomocí funkce RozeberVyraz (tj. pomocí rekurentního volání - funkce volá sama sebe). Stačí zadat, že se jedná o operaci vyšší prioritou (tedy násobení), kterou jsme minule značili UROVEN_2. Pokud rozbor neuspěje (chyba ve výrazu nebo nedostatek paměti), opouštíme opět funkci a vracíme FALSE = neúspěch; v opačném případě je vše v pořádku.
Poslední zatím uvažovanou variantou jsou závorky (TE_ZAVORKY). V tomto případě řetězec určený položkami zacatek a konec výraz i s krajními závorkami. Tyto závorky ovšem nejsou součástí výrazu, kterému vyznačují prioritu, a je tedy třeba je vynechat. V podstatě nejde o nic jiného než posunout ukazatel zacatek o jeden znak dále a ukazatel konec o znak vpřed. Pak opět stačí zavolat rekurentně naši funkci RozeberVyraz, tentokrát však na nižší úrovni (UROVEN_1), nebol závorky mohou obsahovat i sčítání. Všimněte si, že typ měníme z TE_ZAVORKY na TE_SCITANI tím, že je pro výraz v závorce vytvořen samostatný element, je priorita již vyjádřena a není třeba brát závorky jako zvláštní operátor, vnitřek stačí posčítat.
A to je vše, celá funkce Rozeber Vyraz. Jak vidíte, stačí nám vlastně umět provést rozbor na jedné úrovni (např. rozdělení na sčítance či součinitele) a zbytek zajistí rekurze. Pokud se na celou funkci podíváte, zjistíte, že se v ní na 3 místech opakuje v podstatě tatáž posloupnost úkonů; jedná se o vytvoření další struktury pro parametr = element. V takovém případě je samozřejmě vhodnější vytvořit funkci, která by danou činnost vykonávala, a tuto funkci pouze na příslušných místech zavolat. Ušetříme tím mnoho místa i námahy. Stačí zjistit, které údaje jsou pro vytvoření potřeba a ty použít jako parametry funkce pro vytvoření nového elementu; návratová hodnota je jasná- adresa nově vytvořené struktury nebo NULL v případě neúspěchu. Vše si můžete prohlédnout v zdrojovém kódu programu, který jako obvykle naleznete na coverdisku.

Pomocné funkce
Zbývá doplnit pomocné funkce používali jsme totiž PreskokZavorky a PreskokCisla. Druhou jmenovanou funkci jsme vytvořili již dříve, není proto třeba se jí zabývat. Popišme si, jak přeskočit závorku.
Je to velmi jednoduché. Na počátku deklarujeme proměnnou zavorky, která bude obsahovat počet otevřených závorek. Pokud ukazatel uk umístíme za levou závorku a počet závorek nastavíme na 1, stačí procházet řetězec znak po znaku a měnit počet závorek; pokud narazíme na (, zvětšíme počet závorek, najdeme-li ), počet otevřených závorek naopak snížíme. Jakmile bude počet závorek roven nule, víme, že jsme načetli uzavírací (pravou) závorku k závorce, na niž původně ukazatel uk ukazoval. Stačí vrátit ukazatel na znak za závorkou.
Všimněte si, že testovaná podmínka má tvar *uk && zavorky. Takto ji lze zapsat proto, že nenulová hodnota (tj. nějaké otevřené závorky) reprezentují TRUE (pravda), nulová hodnota (všechny závorky uzavřeny) reprezentuje FALSE (pravda). Podobná situace je u *uk = znak, na nějž ukazuje uk (nulový znak totiž označuje konec řetězce).

Uvolnění paměti
Rozbor výrazu tak, jak jsme si jej popsali, jsme mimo jiné prováděli proto, aby bylo možno rychle a efektivně opakovaně vyhodnocovat výraz. Pokud už daný výraz nepotřebujeme (rozložený na elementy), je nutno ho odstranit. Při vytváření jsme totiž alokovali pro každou strukturu Element paměť = vyžádali jsme ji od operačního systému pro svoje účely. Pokud bychom ji po použití neuvolnili, nebude ji moci nikdo dále používat. A protože struktura Element má velikost 30 bytů a u složitějšího výrazu těchto elementů může být například více než 100, záhy by paměť začala docházet (na jeden výraz by se spotřebovalo více 3 KB). Pokud se nemýlím, podobnou věc v podstatě dělá program Maple - po nějaké době práce prostě dojde paměť a musíte ho ukončit (pak už ji uvolní) a pak znovu spustit.
Uvolnění paměti provedeme rekurentně vytvoříme funkci UvolniVyraz (viz výpis na jiné části této dvoustrany), která nejprve uvolni paměť daného elementu. To provede tak, že nejprve uvolní paměť, v níž jsou struktury odpovídající jednotlivým parametrům, a pak paměť obsahující vlastní výraz. Podívejme se na tuto funkci podrobněji.
K uvolnění paměti slouží funkce free, které stačí zadat adresu, kterou nám vrátila funkce malloc či calloc. Jediným parametrem funkce je ukazatel na uvolňovanou strukturu Element (vyraz). Část pro uvolnění paměti jednotlivých parametrů je velice podobná výše popisované části pro rozebrání již oddělených parametrů ve funkci RozeberVyraz. I zde máme ukazatel na Element, který na počátku nastavíme na první parametr výrazu (vyraz->parametr) a pomocí for-cyklu procházíme jednotlivé parametry. Ukončovací podmínka má tvar pomelem - to stačí, nebol jsme si poslední parametr označili tak, že do položky dalsi jsme uložili NULL. A stejně jako u čísel, kde nulová hodnota znamená FALSE (nepravda) a nenulová TRUE (pravda), se i ukazatel obsahující NULL chápe jako FALSE a ukazatel obsahující cokoliv jiného (adresu) jako TRUE.
Hlavní částí těla cyklu je podmínka. Pokud je totiž typ parametru číslo (TE_CISLO), tak tento parametr již žádné další svoje parametry nemá a stačí uvolnit jen paměť odpovídající struktuře Element (free(pomelem)). V opačném případě je nutno zavolat rekurentně funkci UvolniVyraz pro právě uvolňovaný parametr. Všimněte si jedné drobnosti. Při procházení parametrů ve funkci RozeberVyraz jsme prostě použili ve for-cyklu pro nalezení dalšího parametru příkaz pomelem = pomelem->dalsi. Zde tomu tak není - obsah položky dalsi se ukládá do pomocné proměnné pomelem2 a po uvolnění se paměti se okopíruje do pomelem. Je tomu tak proto, že v momentě, kdy uvolníme paměť ji už nemůžeme používat. Ačkoli to není zcela korektní, mohli byste teoreticky i po uvolnění z tohoto místa v paměti číst, jenže mezi tím si již volnou paměť mohl zabrat jiný program, naplnit ji svými údaji a z vašeho hlediska budou v daném místě paměti nesmysly. Proto je třeba nejprve načíst ukazatel na další parametr (dokud paměť ještě "vlastníme") a po té ji teprve uvolnit.
Jakmile uvolníme paměť použitou pro parametry daného výrazu, zbývá už pouze uvolnit paměť použitou pro strukturu Element popisující daný výraz. Opět používáme funkci free()

Vyhodnocení výrazu
Tak, a teď to hlavní - ukážeme si, jak zjistit hodnotu výrazu, který byl rozebrán na jednotlivé elementy. Znovu můžeme velice efektivně využít rekurze - pokud totiž napíšeme funkci, která na základě parametrů určí hodnotu elementu (např. sečte jednotlivé sčítance), jsme téměř hotovi. Pro jednotlivé parametry dané operace stačí zavolat rekurentně tutéž funkci, která provede vyhodnocení těchto parametrů = menších výrazů a tak stále dokola... Postup se zastaví, narazíme-li na číslo na tom není co rozebírat, jeho hodnotu jsme již zjistili.
Funkce VypoctiVyraz provádí různé věci v závislosti na typu výrazu. Vždy však výsledek uloží do reálné proměnné vysledek, který pak vrátí volající funkci. Dále budeme využívat reálnou proměnnou parametr, která bude sloužit pro uložení hodnoty parametrů.
Pokud je výraz číslo, stačí prostě vzít hodnotu tohoto čísla - tu jsme uložili do položky cislo struktury Element.
Dalším zvláštním případem jsou operace sčítání a násobení. Zvláštní jsou proto, že mají proměnný počet parametrů. Běžné funkce mají totiž zpravidla pevný počet (1 nebo 2) parametry. Vyhodnocení sčítání či násobení probíhá opět v cyklu, kdy procházíme jednotlivé parametry výrazu (první je opět vzat z vyraz-> parametr). Tyto parametry vždy vyhodnotíme pomocí rekurentního volání funkce VypoctiVyraz. Do proměnné vysledek si na počátku uložíme 0 nebo 1 (pro sčítání nebo násobení) a hodnoty jednotlivých parametrů pak této proměnné přičítáme, resp. jimi násobíme (v případě inverzních operací odčítáme a dělíme). Po projití všech parametrů je ve vysledek správná hodnota součtu / součinu.
Poslední případ charakterizovaný příkazem switch je pak vytvořen pro další "klasické" funkce jako je sinus, faktoriál či mocnina. Všimněte si, že závorky nejsou ošetřeny - nahradily jsme je totiž po rozboru operací sčítání.

Kontrola správnosti
Tak toto by mohl být váš domácí úkol zkuste si rozmyslet, jak zkontrolovat správnost výrazu; něco se kontroluje již při rozboru, správnost funkčních hodnot při výpočtu (to teprve uděláme). Každá funkce (od příště) má jistý pevný počet parametrů. Zkuste si rozmyslet, jak by vypadala funkce, která by zkontrolovala správný počet parametrů každé funkce ve výrazu.

Začlenění do programu
Ještě jsme si neukázali, jak toto vše použít - tj. co napsat do funkce main(). Je to docela prosté. Za část, v níž vytváříme řetězec s výrazem, zařadíme následující; nejprve vytvoříme základní strukturu Element pro celý výraz (ukazuje na ni ukazatel vzorec):

vzorec = malloc(sizeof(struct Element));
if (vzorec == NULL)
{
printf("Není dostatek paměti ");
return(20);
}
vzorec->dal.si = NULL;
vzorec->parametr = NULL;
vzorec->typ = TE_SCITANI;
vzorec->inverzni = FALSE;
vzorec->cislo = 0;
vzorec->zacatek = vyraz;
vzorec->konec = vyraz+strlen(vyraz)-1;

V postatě jsme alokovali paměť pro strukturu a pak jsme ji vyplnili údaji. Dalším krokem je provedení rozboru výrazu na jednotlivé části - elementy:

if(!RozeberVyraz(vzorec, UROVEN_1))
{
printf("Není dostatek paměti nebo je chyba ve výrazu ");
return(20);
}

Pak již stačí spustit vlastní výpočet pomocí funkce VypoctiVyraz a vypsat výsledek:

printf("Vysledek: %s = %G ", vyraz, VypoctiVyraz(vzorec));

V závěru bychom měli použitou paměť uvolnit:

UvolniVyraz(vzorec);

Tolik tedy dnešní, předposlední, pokračování našeho seriálu. Příště si povíme, jak naučit naši kalkulačku rozebrat výrazy s funkcemi a také něco o tom, co by se s tímto již vytvořeným jádrem dalo podniknout. Nebude toho málo.

BOOL RozeberVyraz(struct Element *vyraz, int uroven)
/* ... předchází to, co jsme vytvořili již minule */
/* rozbor jednotlivých elementů */
/* projdeme postupně všechny vytvořené parametry */
for( aktualni = vyraz->parametr; aktualni != NULL;
aktualni = aktualni->dalsi )
/* dle typu parametru provedeme další rozbor - u závorek či násobení rozebíráme rekurentně výraz = parametr,
u čísla jej načteme */
switch (aktualni->typ)
{
case TE_CISLO:
sscanf(aktualni->zacatek, "%lg", &aktualni->cislo);
break;
case TE_NÁSOBENI:
if (!RozeberVyraz(aktualni, UROVEN-2))
return(FALSE);
break;
case TE_ZAVORKY:
aktualni->zacatek++;
aktualni->konec-;
aktualni->typ = TE_SCITANI;
if (!RozeberVyraz(aktualni, UROVEN_1))
return(FALSE);
break;
}
/* všechno je v pořádku -> vrátíme TRUE */
return(TRUE);
}

/* pomocná funkce pro přeskočení závorky;
vstup: ukazatel na znak = na řetězec), tj. ukazuje na levou zavorku;
výstup: ukazatel na znak (= na řetězec) - bude =ukazovat na znak;
následující za přeskakovanou závorkou */
char *Preskokzavorky(char*uk)
{
/* počitadlo otevřených závorek na počátku je "otevřená" 1 - ta, na niž =ukazuje ukazatel uk */
int zavorek = l;
/* opakovaně zkoumáme znaky řetězce - ukončíme, pokud narazíme na konec řetězce (*uk == ) nebo na uzavírací závorku (zavorek _= 0) průbežně měníme počet otevřených / uzavřených závorek */
for(uk++; *uk && zavorek; uk++)
if (*uk == ()
zavorek++;
else if (*uk == ))
zavorek--;
/* vrátíme ukazatel na znak za závorkou ... ten je v uk */
return(uk);
}

/* následující funkce vypočte hodnotu zadaného výrazu */
double VypoctiVyraz(struct Element *vyraz)
{
struct Element *pomelem;
double vysledek, parametr, parametr2;
/* postupujeme dle typu výrazu; pokud se jedná o sčítání či násobení, je parametrů libovolný počet - ošetříme zvlášť jinak mají funkce vždy jen jeden či dva operátory, speciální případ je číslo - jeho hodnotu máme zapsána přímo ve struktuře Element */
if (vyraz->typ -= TE_CISLO)
vysledek = vyraz->cislo;
else if ( (vyraz->typ == TE_SCITANI) ||
(vyraz->typ == TE NASOBENI))
{
vysledek = (vyraz->typ == TE_SCITANI) ? 0 : 1;
/* postupně projdeme jednotlivé parametry výrazu, zjistíme i jejich hodnotu a aplikujeme na ně příslušnou operaci (přičtení či násobení) */
for( pomelem = vyraz->parametr; pomelem; pomelem = pomelem->dalsi)
{
parametr = VypoctiVyraz(pomelem);
if (pomelem->inverzni)
if (vyraz->typ == TE_SCITANI)
parametr *= -1;
else parametr = 1 / parametr;
if (vyraz->typ == TE SCITANI)
vysledek += parametr;
else vysledek *= parametr;
}
}
else
/* ostatní operátory, které mají 1 parametr */
{
/* zde budou případné další typy výrazů... */
}
/* vrácení získané hodnoty */
return(vysledek);
}

/* následující funkce !uvolní pamětpoužitou pro lstruktury popisující zadaný výraz */
void UvolniVyraz(struct Element *vyraz)
{
struct Element *pomelem, *pomelem2;
/* postupně projdeme jednotlivé parametry výrazu a uvolníme jejich pamět*/
for(pomelem = vyraz-> parametr; pomelem; )
{
/* zapamatujeme si dalsi parametr, pak rovnou ,uvolníme pamětjedná-li se o číslo, jinak použijeme rekurentně tuto funkci */
pomelem2 = pomelem->dalsi;
if ( pomelem->typ == TE_CISLO)
free(pomelem);
else
UvolniVyraz(pomelem);
pomelem = pomelem2;
}
/* uvolnění paměti vlastní struktury vyraz */
free(vyraz);
}

Vytlačiť článok

Pozn.: články boli naskenované ako text a preto obsahujú aj zopár chýb. Taktiež neručíme za zdrojové kódy (Asm, C, Arexx, AmigaGuide, Html) a odkazy na web. Dúfame, že napriek tomu vám táto databáza dobre poslúži.

Žiadna časť nesmie byť reprodukovaná alebo inak šírená bez písomného povolenia vydavatela © ATLANTIDA Publishing

AMIGA REVIEW

ATLANTIDA NEWS