Kurz jazyka C - 8. díl

V dalším pokračování kurzu C se pokusíme využít znalostí o dynamickém zpracování dat z minulého dílu. Doufejme, že je již všichni vstřebali.

Dnes bychom se měli pokusit o zpracování výrazu do snadno "dekódovatelné" podoby - chceme, aby splňovala všechny již dříve vznesené požadavky. Rekurze i seznamy struktur nám při tom budou dobrým pomocníkem.

Popis výrazu
Když si vezmeme jakýkoli matematický výraz, můžeme na něj pohlížet jako na nějakou složenou funkci. Jak to? Nu, výraz se skládá z číselných konstant, operací +, -, *, /, závorek a funkcí jako je sinus či mocnina. Číslo lze chápat jako funkci snadno - je to konstanta, nemá žádné parametry, vrací stále tutéž hodnotu. Operátory sčítání a odčítání, násobení a dělení jsou také funkce - mají alespoň dva parametry (ale mohou jich mít neomezeně) = svoje sčítance či součinitele. Výpočet funkční hodnoty při + se pak provede jako sečtení hodnot jednotlivých parametrů. Závorky jsou taky funkce - vyznačují prioritu; mají jeden parametr (= to, co je uvnitř) a jeho hodnota je zároveň hodnotou "funkce závorka". No a funkce klasické - těm rozumíte sami.
Důvodem pro toto povídání je následující poznání: základem výrazu je nějaká funkce = základní element, a z těchto elementů lze skládat složitější výrazy; každá funkce má totiž nějaké parametry, a ty nejsou ničím jiným než opět výrazy (resp. elementy). Celý výraz lze tedy popsat systémem struktur téhož typu Element, které tvoří jakýsi obecný strom. Zde je definice příslušné struktury:

struct Element
{
struct Element *dalsi;
struct Element *parametr;
enum TypyElementu typ;
BOOL inverzní;
double cislo;
char *zacatek, *konec;
};

Popišme si strukturu popisující naši základní jednotku výrazu podrobněji. Struktura Element má několik základních položek. Položka typ udává konkrétní typ výrazu (funkce). Jak je vidět není žádného běžného typu - položka typ je tzv. výčtového typu. Tento typ si definuje programátor pro proměnné, které mohou nabývat předem daných pevných hodnot, pro něž máme symbolická označení. V našem případě by výčtový typ enum TypyElementu mohl vypadat například takto:

enum TypyElementu (TE_NEZNAMY= 0, TE_CISLO = 1, TE_SCITANI, TE_NASOBENI, TE_ZAVORKY);

Jak vidíte, je definice výčtového typu uvozena klíčovým slovem enum následovaným jménem typu a dále seznamem možných hodnot (symbolických označení), které jsou uvedeny ve složených závorkách. Tyto symbolické hodnoty lze jak dosazovat do proměnné daného výčtového typu. Pozn.: interně si tyto konstanty kompilátor reprezentuje jako celá čísla typu int, pokud nám záleží na hodnotě, lze ji specifikovat přímo v deklaraci (např. TE_CISLO = 1).
Vraťme se ale k naší struktuře. Položka typ je tedy výčtového typu a bude nám určovat, o jakou funkci se jedná. Zatím jsme definovali v typu TypyElementu pouze číslo, sčítání, násobení a závorky, snadno však můžeme později přidat další funkce (sinus ... TE_SINUS, odmocnina ... TE_ODMOCNINA, proměnná x ... TE_X apod.). Chtěl bych upozornit na jednu věc - jak jste si asi všimli, chybí např. definice odčítání nebo dělení. Aby rozbor výrazu nebyl příliš komplikovaný, budeme inverzní funkci (k + ... -, k sin(x) ... arcsin(x)) reprezentovat tak, že u parametru, na nějž má být aplikována inverzní funkce, bude nastavena další z položek struktury inverzni. Jedná se o proměnou, jejíž hodnoty budeme chápat jako pravda (TRUE) / nepravda (FALSE). Poslední ze skupinky tří proměnných je proměnná číslo. Tato položka bude mít význam pouze tehdy, bude-li se jednat přímo o číslo (typ TE_CISLO) - pak bude obsahovat konstantní hodnotu této funkce - tj. číslo, které je danou položkou reprezentováno. Pozn.: u ostatních typů funkcí tato položka nemá smysl, hodnota se musí vypočítat z parametrů funkce.
Dalšími položkami, kterými jsme se ještě nezabývali jsou dalsi a parametr. Jak jsem již objasnil, každá funkce ve výrazu má nějaké parametry (s výjimkou čísla), které nejsou opět ničím jiným než výrazy (např. sin(2x - 5) - parametrem funkce sin(x) je výraz 2x -5). Položka parametr je proto ukazatel na první parametr funkce strukturou Element reprezentované. Protože obecně nevíme, kolik parametrů ta která funkce má (+ jich má např. proměnný počet), budou parametry spojeny do jednosměrného seznamu (o němž jsme si povídali minule). Položka parametr pak bude ukazatelem na první výraz = parametr v seznamu. Jednotlivé položky seznamu budou spojeny (budou na sebe ukazovat) pomocí dalsi - prvky seznamu = elementy budou tedy položku dalsi využívat jako ukazatel na následující parametr. Poslední parametr bude mít samozřejmě v této položce NULL..
Nyní již svítá, jak bude výraz reprezentován. Základem bude struktura Element pro operaci (funkci) sčítání, která bude mít za parametry jednotlivé sčítance výrazu. Tyto sčítance budou opět výrazy (funkce, např. násobení nebo závorky), které budou mít jiné parametry a tak dále. Pro lepší představu se podívejte na obrázek. Na obrázku je napsán výraz a zároveň je rozebrán výše popsaným způsobem. Jednotlivá kolečka obrázku reprezentují jednotlivé struktury Element, v nich je vždy uveden typ operace (+ - sčítání, * - násobení, () - závorky, je-li uvedeno číslo, jedná se o číselnou konstantu s příslušnou hodnotou). Každé kolečko = element má (pokud se nejedná o číslo) vedenu spojnici směrem dolů k dalším kolečkům = svým parametrům Ty šikmé spojnice směrem dolů vlastně představují odkaz pomocí položky parametr. Jednotlivé parametry jsou pak spojeny do seznamu pomocí položek dalsi = vodorovných spojnic vedle ležících koleček. Pokud je u kolečka = elementu poznámka INV, značí to, že na daný parametr se má provést opačná operace (místo + se má provést - ...).
Je vám již jasno jak výraz reprezentovat? Zdá se vám to složité? Možná, nicméně tento popis nám umožní snadné a rychlé vyhodnocování výrazu. Pokud budeme mít totiž funkci pro výpočet jednotlivých funkcí jako je sčítání, mocniny, sinh apod. - nazvěme ji např. VyhodnoceniVyrazu pak pro výpočet potřebných parametrů pro výpočet požadované funkce stačí pouze rekurentně zavolat tutéž funkci s ukazatelem na příslušný parametr element. Pokud tomu nevěříte, promyslete si to (nebo to uvidíte příště, jak je to jednoduché).

Rozbor výrazu
Ha, vzkřiknou ti pozornější. Zatajili nám, k čemu jsou dobré položky zacatek a konec (ukazatelé na znak). Je jasné, že takovouto rekurentně definovanou a vyhodnocovanou strukturu bude dobré také rekurentně vytvářet. Při rozboru výrazu budeme postupovat shora. Nejprve v zadaném výrazu najdeme na nejvyšší úrovni všechny sčítance - to uděláme tak, že budeme procházet zadaný výraz = řetězec, čísla přeskočíme pomocí funkce PreskokCisla() (tu máme z minula), závorky pomocí PreskokZavorky() (tu teprve vytvoříme), násobení a dělení ignorujeme. Tak zjistíme začátky a konce jednotlivých parametrů = sčítanců. Tak máme odseparovány jednotlivé sčítance - ale ne ve formě výrazů ze struktur Element, ale jako část řetězce. A právě začátek a konec této části řetězce si uložíme do položek struktury Element zacatek a konec. Tyto informace jsou pouze dočasné - jsou potřeba v době, kdy víme, jaká část řetězce tvoří daný výraz, ale nemáme ještě rozebrány parametry tohoto výrazu; ty musíme zjistit opětovným (rekurentním) aplikováním rozboru na onu menší část řetězce. Až rozborem parametry daného elementu získáme nastavíme položku parametr a údaje v zacatek a konec budou již zbytečné.
Jak vidno, dobrali jsme se přes vysvětlení významu jednotlivých položek až k samotnému algoritmu pro rozbor zadaného výrazu.

Popis algoritmu
Popišme si nyní vlastní algoritmus. Zdrojový kód příslušné funkce (jmenuje se RozeberVyraz) naleznete na jiné části této stránky. Vstupem naší funkce je výraz = element a úroveň, která se má při rozboru používat. Neboť nejprve je třeba provést rozbor vzhledem ke sčítání (rozdělit výraz na jednotlivé sčítance) a ty teprve rozebrat vzhledem k násobení, které má vyšší prioritu, budeme používat parametr uroven pro rozlišení rozboru vzhledem ke sčítání (hodnota parametru UROVEN_1) a násobení (hodnota parametru UROVEN_2). Jak vyplývá z výše uvedeného popisu, řetězec, který budeme rozebírat, je určen položkami zacatek a konec ve struktuře Element parametru vyraz. Po rozboru už tyto položky nebudou mít smysl, ale budou již doplněny parametry výrazu.
V rámci funkce se používají následující proměnné: struktura pomelem typu Element nám slouží k uchování údajů o právě procházeném parametru. Když zjistíme, že jsme na konci právě procházeného parametru (např. zkoumáme sčítanec a narazíme na +), stačí vytvořit novou strukturu Element (pomocí dynamické alokace paměti), která bude parametr popisovat a obsah proměnné pomelem do ní okopírovat. Pomocný ukazatel aktualni nám bude sloužit pro udržování adresy právě alokované struktury Element, která se bude zařazovat do seznamu, a ukazatel poslední bude ukazatel na naposledy přidaný parametr (přidaný do seznamu parametrů právě zadaného Elementu vyraz ).
Ukazatel na znak uk bude ukazovat na právě zpracovávaný znak vstupního řetězce. Proměnné našeho logického typu BOOL slouží v rámci rozboru aktuálního parametru k udržování informace o výskytu závorek, operací sčítání a násobení a čísel. Ty nám potom pomohou určit typ daného parametru.
Před započetím vlastního rozboru výrazu nastavíme v naší pomocné struktuře pomelem položky na standardní hodnotu a ukazatel poslední na NULL (ještě nebyl přidán žádný parametr). Vlastní průchod podřetězcem je realizován pomocí for cyklu, v němž je na počátku do uk přiřazen ukazatel na počátek zpracovávaného úseku a ukončovací podmínka (uk <= vyraz->konec) testuje, zda jsme již nedošli na konec tohoto úseku.
Vlastní tělo for-cyklu Je tvořeno příkazem switch; jak víte, je to příkaz pro selekci jedné z možností. Parametrem zde je *uk, tj. právě zpracovávaný znak. Podle hodnoty tohoto znaku se pak rozlišuje, co se má provést. Každá možnost je uvozena klíčovým slovem case za nímž následuje příslušná hodnota (znak, např. 0). Pokud má zadaný znak hodnotu uvedenou za klíčovým slovem case , budou se provádět příkazy za touto položkou uvedené až do výskytu klíčového slova break; to znamená, že pokud např. za case 1: nic nenásleduje, pokračuje se prováděním toho, co je uvedeno za case 2: atd. Toho je zde bohatě využito. Proberme si nyní jednotlivé možnosti:
- case *: case /: v tomto případě si samozřejmě nastavíme proměnnou bylo_nasobeni na TRUE (pravda). Pokud není úroveň rozboru UROVEN_2 (tj. nerozebíráme výraz na součinitele, ale na sčítance), není třeba nic jiného dělat (kromě přesunu ukazatele uk na další znak - to se však dělá jednotně přímo v hlavičce for-cyklu). Pokud tomu tak není, měli bychom provést alokaci nové struktury Element, doplnit všude příslušné údaje atd. To je ve výpisu vynecháno, protože v podstatě totéž se provede (při nižší úrovni) také u operace sčítání.
- case +: case -: v tomto případě nejprve prohlédneme předchozí znak je-li to také operátor, je toto znaménko unární a je součástí čísla. V tomto případě se přeskočí tělo podmíněného příkazu a protože nenásleduje break, pokračuje se příkazy pro zpracování čísla. Pokud se má naopak chápat + či - jako běžná operace sčítání či odčítání, postupujeme podobně jako u násobení a dělení. Nastavíme proměnnou bylo_plus, pokud provádíme rozbor na nižší úrovni (UROVEN_1), víme, že je ukončen právě zpracovávaný parametr. Nastavíme tedy v pomocné struktuře pomelem zbývající položky, t.j. konec parametru (= ukazatel na předchozí znak před +) a typ parametru. Ten určíme snadno právě pomocí BOOL proměnných. Pokud se vyskytlo násobení je typ parametru TE_NASOBENI; pokud se vyskytly závorky (násobení nikoliv), pak je typ parametru TE_ZAVORKY a pokud se vyskytlo pouze jedno číslo, je typ parametru TE_CISLO. Jiné typy zatím nemáme. Zbývá pouze pomocí funkce malloc() získat paměť pro novou strukturu Element (všimněte si, že v případě neúspěchu - malloc() vrátí NULL - opouštíme funkci a vracíme hodnotu FALSE na znamení, že došlo k chybě). Do této paměti překopírujeme obsah pomocné struktury pomelem na to stačí přiřazovací příkaz neboť jej lze použít i pro celé struktury (v ANSI C). A takto vytvořený parametr zařadíme do seznamu parametrů Elementu vyraz. Pokud je v ukazateli poslední NULL (je to první přidávaný parametr), stačí nastavit ukazatel vyraz>parametr. V opačném případě poslední obsahuje adresu naposledy přidávaného parametru - pak nastavíme položku dalsi tohoto posledního parametru = elementu, neboť jsme si řekli, že právě tato položka bude sloužit ke spojení jednotlivých parametrů do seznamu.
Tím je přidání nového parametru dokončeno, zbývá nastavit naše průběžně udržované proměnné na správné hodnoty: ve struktuře pomelem nastaví me začátek a konec dalšího výrazu (= ukazatel na znak následující za právě rozebíraným + nebo -), nastavíme také položku inverze (dle toho, zda se další parametr příčí tá nebo odčítá), opravíme ukazatel poslední a nastavíme všechny BOOL proměnné na FALSE (začínáme s dalším výrazem, nic v něm ještě nebylo). A to je vše.
- case 0: až case .: zde se má zpracovat číslo. Opět nastavíme příslušnou boolevskou proměnnou bylo cislo a pomocí funkce PreskokCisla() toto číslo přeskočíme.
- case (: totéž jako u čísel poznamenáme si, že jsme narazili na závorku a přeskočíme ji pomocí funkce PreskokZavorky().
- default: všechno ostatní pro nás zatím znamená chybu - takže vrátíme FALSE a funkci ukončíme. Příště si sem
doplníme zpracování funkce a proměnných.
Tím je popsán celý rozbor výrazu na jednotlivé sčítance/součinitele. A nic víc nepotřebujeme. To jak rekurentně zpracujeme právě vytvořené parametry = elementy součtu či součinu, si povíme příště. V příštím pokračování si také povíme, jak vyhodnotit výraz popsaný takovouto strukturou a jak tuto strukturu opět odstranit z paměti. Jak již příští měsíc zjistíte, bude nyní naše Kalkulačka schopná zpracovat a vypočítat již libovolně složitý výraz. Dnes to bylo asi trochu náročné, těm z vás, kterým to nevzalo vítr z plachet však doporučuji zkusit si doma vytvořit funkci pro přeskok závorky .

#define UROVEN_1 1
#define UROVEN_2 2
/* lokální deklarace funkcí pro rozbor */
char *PreskokCisla(char *uk);
char *PreskokZavorky(char *uk);
/* tato funkce rozebere zadaný výraz v zadané úrovni; vrací, zda je vše OK (TRUE) nebo zda nastala chyba ve výrazu či došla paměť (FALSE) */
BOOL RozeberVyraz(struct Element *vyraz, int uroven)
{
struct Element pomelem, *posledni, *aktualni;
char *uk, znak;
BOOL bylo_plus = FALSE bylo_krat = FALSE;
BOOL byla zavorka = FALSE, bylo cislo = FALSE;
/* vlastní rozbor výrazu na elementy; tento ukazatel ukazuje na první parametr v seznamu parametrů výrazu - pokud žádný parametr nebude, zůstane NULL */
vyraz. parametr = NULU
/* příprava pomocné struktury */
pomelem.dalsi = NULL; pomelem.parametr = NULL;
pomelem.inverze = FALSE;
pomelem.zacatek = pomelem.konec = vyraz->zacatek;
poslední = NULL;
/* vlastní prochození výrazem */
for(uk = vyraz->zacatek; uk <= vyraz->konec; uk++)
{
switch (*uk)
{
case *: case /:
bylo krat = TRUE;
if (uroven != UROVEN_2) break;
/* zde by bylo totéž, jako při vytvoření parametru v níže uvedeném případě operací + a -; je to zde vynecháno */
break;
case +: case -
znak = *(uk-1);
if ((uk != vyraz->zacatek) && (znak !=+) && (znak !=-) && (znak !=*) && (znak !=/))
{
bylo_plus = TRUE;
if (uroven != UROVEN_1) break;
/* nutno vytvořit nový Element */
pomelem.konec = uk - 1;
/* číslo... dosadíme později při rozboru */
if (bylo krat)
pomelem.typ = TE_NASOBENI;
else if (byla zavorka)
pomelem.iyp = TE_ZAVORKY;
else pomelem.typ = TE CISLO;
/* tvoříme novy výraz = strukturu Element */
aktualni = malloc(sizeof(struct Element));
if (aktualni == NULL)
return(FALSE);
else *aktualni = pomelem;
/* zapojíme ho do seznamu parametrů */
if (poslední == NULL)
vyraz->parametr = aktualni;
else poslední->dalsi = aktualni;
/* nastaví se pro další průběh */
poslední = aktualni;
pomelem.inverze = (*uk ==-) ? TRUE : FALSE;
pomelem.zacatek = pomelem.konec = uk + 1;
/* zrušit nastavení bylo něco.. */
bylo_plus = FALSE; bylo_krat = FALSE;
byla_zavorka = FALSE; bylo_cislo =FALSE;
break;
}
/* v opačném případě je to číslo */
case 0: case 1: case 2: case 3: case 4:
case 5: case 6: case 7: case 8: case 9: case .:
bylo_cislo = TRUE; uk = PreskokCisla(uk);
break;
case (:
byla_zavorka = TRUE; uk = PreskokZavorky(uk);
break;
default: return(FALSE);
}
}
/* zde by bylo totéž, jako při vytvoření parametru v níže uvedeném případě operací + a -; je to zde vynecháno */
/* rozbor jednotlivých elementů - příště */
}

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