calc - kombinatorické kalkulačka s podporou výrazov

Jednoduchý program, ktorý som vytvoril čisto pre precvičenie vyčíslenie matematického výrazu zadaného v infixovém tvare. Výraz je najprv prevedený na postfixový tvar (s pomocou zásobníka) a následne vyčíslený.

Program je vrátane zdrojových kódov, pripraveného Makefile a 64b binárek pre Linux a Windows.

Pri bežnom spustení očakáva program na štandardnom vstupe výraz ku spočítané. Program tiež môžete spustiť s prepínačom --help (zobrazuje pomoc) alebo -f nazev_souboru (načíta výraz zo súboru). Príklad výrazu s ukážkou všetkých možností programu:

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

Niektoré časti programu boli spravené dosť na rychlo a nie sú to dobré praktiky (napr. Ošetrenie chybného vstupu s pomocou exit ():) ). Cieľom bolo, ako som už povedal, vyskúšanie algoritmov pre prevod infixové notácie na postfixovou a jej následné vyčíslenie. Do budúcnosti by mohlo byť zaujímavé rozšíriť program, aby zvládal pracovať s viac ako 64b číslami.

Verzia

0.3 - pridaná podpora pre priamy výpočet faktoriálu (operátor!)
0.2 - prvotné verzia

Postfix

Alebo tiež "obrátená poľská notácie". Poľskú (prefixové) notáciu vymyslel v roku 1924 poľský matematik Jan Łukasiewicz. Jej zápis sa podobá napríklad zápisu funkcie:

add(int a, int b)
+ab

Na účely spracovania matematického výrazu sa nám bude hodiť obrátená verzia:

ab+

Najskôr od pohľadu môže každý povedať, ako sa tvorí z bežne používané, infixové notácie (a+b) - jednoducho dáme operátor až za jeho operandy. Prečo vlastne používať takýto zápis výrazov?

• bezzávorkový (odpadá zložitá analýza, ktorá zátvorka patrí k čomu)
• jednoduché vyčíslenie (ideme postupne a vykonávame jednotlivé operácie)

Prevod infixi na postfix

Najprv si ukážeme, ako Vlaste previesť bežný zápis (infixi) na postfixovou notáciu.

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

Prevod a+b je jednoduchý. Ako ale previesť výraz sa zátvorkami? Postfix sa vykonáva postupne, takže ak chceme, aby sa niečo vykonalo skôr, než niečo iné, dáme to na začiatok:

ab+cd-

Po vyčíslení takého výrazu nám zostanú dva výsledky - a+b a cd. Tieto výsledky sú operandy násobenie.

ab+cd-*

Týmto je prvá časť výrazu prevedená. Rovnakým spôsobom budeme postupovať aj pre zvyšok výrazu.

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

Takto vyzerá celý výraz zapísaný v postfixové notáciu. Nesmieme zabudnúť na =, ktoré označuje koniec výrazu.

Algoritmus

Pre vytvorenie postfixové notácie budeme spracovávať infixový výraz zľava doprava - položku po položke a budeme využívať zásobník. Pre spracovanie výrazu som si vytvoril jednoduchý konečný automat (FSM) a výstup ukladal do zoznamu.

1. Ak je spracovávanú položkou operand, pridaj ho na koniec vznikajúceho výstupného reťazca.
2. Ak je spracovávanú položkou ľavá zátvorka, vlož ju na vrchol zásobníka.
3. Ak je spracovávanú položkou operátor, vlož ho na zásobník, pokiaľ je na vrchole ľavá zátvorka, operátor s nižšou prioritou alebo je zásobník prázdny. Ak je na vrchole zásobníka operátor s vyššou alebo zhodnú prioritou, vlož ho na koniec výstupného reťazca a odstráň zo zásobníka. Opakuj krok 3, než sa ti podarí vložiť spracovávaný operátor.
4. Ak je spracovávanú položkou pravá zátvorka, odoberajte z vrcholu položky a vkladaj je na koniec výstupného reťazca než narazíš na ľavú zátvorku.
5. Ak je spracovávanú položkou obmedzovač '=', odstraňuj prvky z vrcholu zásobníka a pridávaj je na koniec výstupného reťazca. Až je zásobník úplne prázdny, pridaj '='.

Vyčíslenie Postfix

Máme prenesený výraz - teraz už len zostáva ho vyčísliť.

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

Vždy vezmeme príslušný počet operandov a prevedieme operáciu. Teda sčítame a a b, odpočítame d od c a tieto dve čísla spolu vynásobíme. Ďalej sčítame e a f - teraz máme dve čísla - výsledok násobenia a výsledok sčítania - tie podelíme (prvý operand / druhý operand) a máme ďalšie medzivýsledok. A takto postupujeme, ako vyriešime celý výraz.

Algoritmus

Algoritmus pre vyčíslenie postfixového výrazu je jednoduchý a využíva zásobník. Výraz je spracovávaný zľava doprava.

1. Ak je spracovávaným prvkom operand, vlož ju do zásobníka.
2. Ak je spracovávaným prvkom operátor, vyber zo zásobníka príslušný počet operandov, vykonaj operáciu a výsledok ulož späť na zásobník.
3. Ak je spracovávaným prvkom obmedzovač '=', je výsledok na vrchole zásobníka.

Galéria