Parser jednoduchých matematických výrazů v C#

Tento jednoduchý parser je postaven na algoritmu Shunting-Yard. Zpracování matematického výrazu je rozděleno do 3 částí. V první části se výraz rozbije na tzv. Tokeny pomocí Tokenizeru(Lexeru). Token je jedna samostatná část výrazu s určitým významem. Jedná se o čísla, operátory a funkce.

Tokenizer může být hodně jednoduchý nebo i poměrně komplexní podle toho, jak benevolentní zápis matematických výrazů budeme chtít zpracovávat. Jedná se hlavně o mezery mezi jednotlivými prvky výrazu, závorky u funkcí s jedním parametrem, zápis unárních operátorů apod.

Tento parser využívá trochu složitější Tokenizer, kterému nevadí mezery mezi jednotlivými prvky výrazu. Dokáže rozdělit i funkci s jedním parametrem bez závorek (abs(5); abs5) a to i s unárním operátorem negace (abs-5). Rozezná implicitní násobeni apod.

V další fázi následuje převod z infixové notace na postfixovou (tzv. Reverse-Polish notation). Převod probíhá proto, protože matematický výraz v infixové notaci se nedá zpracovat pouze čtením a počítáním zleva doprava. Operátory v infixové notaci mají dvě důležité vlastnosti. A jsou to přednost (Precedence) a Asociativita (Associativity).

V Postfixové notaci jsou však tyto vlastnosti zanedbatelné, protože jednotlivé prvky matematického výrazu jsou zapsány v konkrétním pořadí, kdy jsou nejprve uvedeny operandy a až poté operátor, který provádí akci na těchto operandech. Díky tomuto zápisu se poté dá převedený výraz zpracovat čtením zleva doprava. Př.

Infixová notace: 3 + 3 Postfixová notace: 3 3 +

Když se podíváme na trochu složitější příklad, ve kterém budeme muset vzít v úvahu i přednost operátorů:

Infixová notace: 2 + 3 * 4 Postfixová notace: 2 3 4 * +

V poslední fázi dochází k samotnému výpočtu, který probíhá tak, že se postupuje zleva doprava. když se narazí na operátor, tak se vezme konkrétní počet parametrů vlevo od operátoru (zde 2 a 3) a provede se daná akce (zde násobení). Tím dostaneme výraz 2 12 +. Následuje poslední operand (+), který sečte zbývající čísla a tím dostaneme výsledek 14.

Detailní popis způsobu převodu lze najít na Wikipedii.

Když si program spustíte, tak budete moci zapsat matematický výraz, jehož výsledek si chcete nechat zobrazit. Zároveň se vám zobrazí jednotlivé Tokeny, na které byl výraz rozdělen a také jak daný výraz vypadá v postfixové notaci.

Galerie