calc - kombinatorická kalkulačka s podporou výrazů

Jednoduchý program, který jsem vytvořil čistě pro procvičení vyčíslení matematického výrazu zadaného v infixovém tvaru. Výraz je nejprve převeden na postfixový tvar (s pomocí zásobníku) a následně vyčíslen.

Program je včetně zdrojových kódů, připraveného Makefile a 64b binárek pro Linux a Windows.

Při běžném spuštění očekává program na standardním vstupu výraz ke spočtení. Program také můžete spustit s přepínačem --help (zobrazí nápovědu) nebo -f nazev_souboru (načte výraz ze souboru). Příklad výrazu s ukázkou všech možností programu:

p(5) * (v(3,7) + v'(3,7) - 4^2) - (15 / 3)*c(2, 5) + c'(3,6)

Některé části programu byly udělány dost na rychlo a nejsou to dobré praktiky (např. ošetření chybného vstupu s pomocí exit() ). Cílem bylo, jak jsem již řekl, vyzkoušení algoritmů pro převod infixové notace na postfixovou a její následné vyčíslení. Do budoucna by mohlo být zajímavé rozšířit program, aby zvládal pracovat s více než 64b čísly.

Verze

0.3 - přidána podpora pro přímý výpočet faktoriálu (operátor !)
0.2 - prvotní verze

Postfix

Nebo také "obrácená polská notace". Polskou (prefixovou) notaci vymyslel v roce 1924 polský matematik Jan Łukasiewicz. Její zápis se podobá například zápisu funkce:

add(int a, int b)
+ab

Pro účely zpracování matematického výrazu se nám bude hodit obrácená verze:

ab+

Nejspíš od pohledu může každý říct, jak se tvoří z běžně používané, infixové notace (a+b) - jednoduše dáme operátor až za jeho operandy. Proč vlastně používat takovýto zápis výrazů?

• bezzávorkový (odpadá složitá analýza, která závorka patří k čemu)
• jednoduché vyčíslení (jdeme postupně a vykonáváme jednotlivé operace)

Převod infixu na postfix

Nejprve si ukážeme, jak vlastě převést běžný zápis (infix) na postfixovou notaci.

(a+b)*(c-d)/(e+f)*(g-h)=

Převod a+b je jednoduchý. Jak ale převést výraz se závorkami? Postfix se vykonává postupně, takže pokud chceme, aby se něco vykonalo dřív, než něco jiného, dáme to na začátek:

ab+cd-

Po vyčíslení takového výrazu nám zůstanou dva výsledky - a+b a c-d. Tyto výsledky jsou operandy násobení.

ab+cd-*

Tímto je první část výrazu převedena. Stejným způsobem budeme postupovat i pro zbytek výrazu.

ab+cd-*ef+/gh-*=

Takto vypadá celý výraz zapsaný v postfixové notaci. Nesmíme zapomenout na =, které označuje konec výrazu.

Algoritmus

Pro vytvoření postfixové notaca budeme zpracovávat infixový výraz zleva doprava - položku po položce a budeme využívat zásobník. Pro zpracování výrazu jsem si vytvořil jednoduchý konečný automat (FSM) a výstup ukládal do seznamu.

1. Je-li zpracovávanou položkou operand, přidej ho na konec vznikajícího výstupního řetězce.
2. Je-li zpracovávanou položkou levá závorka, vlož ji na vrchol zásobníku.
3. Je-li zpracovávanou položkou operátor, vlož ho na zásobník, pokud je na vrcholu levá závorka, operátor s nižší prioritou nebo je zásobník prázdný. Pokud je na vrcholu zásobníku operátor s vyšší nebo shodnou prioritou, vlož ho na konec výstupního řetězce a odstraň ze zásobníku. Opakuj krok 3, než se ti podaří vložit zpracovávaný operátor.
4. Je-li zpracovávanou položkou pravá závorka, odebírej z vrcholu položky a vkládej je na konec výstupního řetězce než narazíš na levou závorku.
5. Je-li zpracovávanou položkou omezovač '=', odstraňuj prvky z vrcholu zásobníku a přidávej je na konec výstupního řetězce. Až je zásobník zcela prázdný, přidej '='.

Vyčíslení postfixu

Máme převedený výraz - teď už jen zbývá ho vyčíslit.

ab+cd-*ef+/gh-*=

Vždy vezmeme příslušný počet operandů a provedeme operaci. Tedy sečteme a a b, odečteme d od c a tyto dvě čísla spolu vynásobíme. Dále sečteme e a f - teď máme dvě čísla - výsledek násobení a výsledek sčítání - ty podělíme (první operand / druhý operand) a máme další mezivýsledek. A takto postupujeme, než vyřešíme celý výraz.

Algoritmus

Algoritmus pro vyčíslení postfixového výrazu je jednoduchý a využívá zásobník. Výraz je zpracováván zleva doprava.

1. Je-li zpracovávaným prvkem operand, vlož ho do zásobníku.
2. Je-li zpracovávaným prvkem operátor, vyjmi ze zásobníku příslušný počet operandů, proveď operaci a výsledek ulož zpět na zásobník.
3. Je-li zpracovávaným prvkem omezovač '=', je výsledek na vrcholu zásobníku.

Galerie

Program byl vytvořen v roce 2016.