Když jsem si předmět Programování v jazyce C pro fyziky zapisoval, věděl jsem, že bude zakončen poměrně rozsáhlým projektem. Ale když mi přišlo zadání, poněkud mi přeběhl mráz po zádech. Jako nejjednodušší byl označena hra Labyrint (bludiště je v textovém souboru, algoritmus najde nejkratší cestu), z dalších zadání bych jmenoval ještě Piškvorky, Lodě nebo kecálka Karla.
Příznakem „Dle mého osobního názoru asi nejtěžší“ bylo značeno zadání programu, který měl jako vstup textový řetězec reprezentující matematický výraz a jako výstup tento výraz ve formě stromové struktury. Samozřejmě, nějakým lidským způsobem reprezentovaný.
Tak jsem se pousmál, protože o vlastním parseru aritmetických výrazů sním už od dob, co jsem začal programovat a teď jsem měl konečně příležitost. Řekl jsem si tedy Challenge accepted a začal přemýšlet jak na to. V zadání byl sice návod na nejjednodušší postup, ale trvalo mi asi týden než jsem jej pochopil. Jeho filosofie spočívala v tom, že výraz je tvořen nějakým termem (jeden „sčítanec“), symbolem +/- a případně dalším (pod)výrazem. Je to tedy rekurzivní definice, a když se nad ní zamyslíme, zjistíme, že se vlastně jedná o lineární spojový seznam termů (kde každý term má příznak, jestli se k předchozímu přičítá nebo se od něj odčítá).
Velmi obdobně je definován i onen term – je to součin nebo podíl faktoru s dalším termem. Vyvrcholení nastává při definici faktoru – tedy činitele / dělitele / dělence. Tím může být obyčejné číslo, záporné číslo (v mé reprezentaci obecně funkce), nebo výraz v závorce. Kde pojmem výraz je myšlen opět ten výraz výše.
Krásně je z těchto definic poznat, že jejich rekurze může být ukončena pouze číslem, což nám poté umožní výraz jednoznačně vyčíslit (kromě jeho vypsání a případného vymazání z paměti). Pokud si toto uvědomíte, a nebojíte se pointerů, hloubkové rekurze a předávání odkazů na globální proměnné odkazem je pak implementace hračka.
Opravdu hračka. De facto celý program jsem zvládl za necelý den. Ve skutečnosti výraz a term jsou implementačně velmi podobné (liší se akorát tím, jestli jsou tvořeny termem a výrazem nebo formem a termem), takže je stačilo jen zkopírovat a upravit pár řádků. Nicméně kód tak narostl na přibližně 500 řádků. I já jsem zíral. 500 řádků plných pointerování, a práce s globálním indexem a já jsem to stihl za necelý pátek. O tom, že jsem komplet celý program tvořil v C write’n’run ani nemluvě. Ideální způsob, jak se naučit používat základní vimové příkazy, jako GG nebo / či :%s/foo/bar/g.
Jenže. To byl opravdu základ. Chybělo sice už jen dodělat funkčnost funkcí (s těmi jsem si vyhrál – byly totiž reprezentovány ukazateli na funkce) a ošetřit syntaktické chyby (a varování) vstupu.
Moje první idea byla, že pokud při parsování některého elementu dojde k syntaktické chybě (například 4+*6), vrátí jen jeho první část a to, počínaje chybou bude ignorovat. Až jsem to měl hotové, tak nějak jsem si uvědomil, že to je stejně pitomost. Přece, když je výrazu chyba, tak je ve výrazu chyba. Může to být překlep, ale co když není? Tento algoritmus prostě z chyby udělal varování a opravil ji tím nejjednodušším způsobem. Tím se však výraz stal nekonzistentní, tedy špatný. Takže jsem tam prostě nacpal, že jakmile narazí parser na chybu, nekompromisně vrací NULL s tím, že i procedura která ji volala, pak automaticky také vrací NULL, a tak to probublává až na samotný výraz, který se tím pádem také stane NULL.
Z původního algoritmu mi však ve funkcích na výpočet, vypsání a vymazání zůstaly testovací podmínky na testování konzistence výrazu, tak jsem je tam nechal (i když tam nemají význam).
Několik dní mi pak zabrala snaha vyřešit kontrolu parity závorek. Původní idea byla taková, že přibude další globální proměnná, nazvaná zanoření závorek – z, na počátku inicializovaná na začátku na nulu. Při začátku parsování faktoru „výraz v závorce“ se měla zvýšit o 1 a po dokončení opět snížit. Pokud na konci parsování celého výrazu byla hodnota větší, než 0, nebyla některá závorka uzavřena, a tak se program tvářil, jakoby byla na konci, ale pokud tam byla nějaká uzavírací navíc, tak ji měl přeskočit.
Ale jak chce odchytávat uzavřenou závorku u výrazu, který není výraz v závorce? Nijak. To by prostě nefungovalo. Řešením tedy bylo přesunout obsluhu uzavírající závorky do samotné funkce parsuj_vyraz, do míst, kde se testuje právě nalezený znak. Jenže tím bych totálně zabil přehlednost kódu. Při představě, že otevírání a zavírání závorky jsou každé na úplně jiném konci a v úplně jiné části kódu. Ale ani po mnoha dnech jsem nevymyslel ideální řešení, ale alespoň jsem tu obsluhu rozbil na aplikační a uživatelskou část. Aplikační jsem ponechal přehledně při parsování výrazu závorce (stará se jen o inkrementaci a dekrementaci proměnné z), zatímco uživatelskou jsem tedy rozházel po celém kódu, což už mi nepřišlo tak nehumální, neboť se tak ztratila mezi ostatními chybovými a varovnými hláškami celého programu.
Doufám, že vám program půjde zkompilovat (panu profesor s tím měl na Windows menší problémy). Po zkompilování si jej, linuxáci, můžete hodit do třeba do /bin a pokud si jej lehce zmodifikujete (tady dodávám mou, odevzdávanou verzi, nijak neupravenou), můžete jej volat třeba
|
1 |
mycalc sin0.75*3.14 |
nebo například
|
1 |
cat ten_slozitej_vzorecek | sed 's:x:14.5:g' | mycalc |
který vám samozřejmě ten_slozitej_vzorecek vyčíslí pro x=14.5.
V plánu mám po vzoru z Paradigmat programování 2 (kde jsme něco podobného dělali objektově v Lispu) vytvořit si program na parsování výrazů s proměnnými a derivování/integrování (případně další operace s funkcemi jako tabelace hledání inflexních bodů), přičemž na to asi použiji přecejen C++. Uvidím, jestli bude čas.
