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

C++ Pokročilé konstrukce Zdrojákoviště 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.

 

Stáhnout

Staženo 28x (34.69 kB)
Aplikace je včetně zdrojových kódů v jazyce C

 

  Aktivity (3)

Program pro vás napsal David Novák
Avatar
Autor v současné době studuje FIT VUT Brno a zajímá se především o nízkoúrovňové programování (C/C++, ASM) a návrh hardwaru (VHDL). Je zde také členem výzkumného týmu ANT@FIT (Accelerated Network Technologies).

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 



 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!