Úkol SymCalc je nepovinný. Úloha je zajímavá, odhaluje způsob, jakým jsou prováděny výpočty matematických výrazů v počítačích obecně. Její zpracování je ale poměrně obtížné, a proto ji doporučujeme zejména těm z vás, pro které jsou ostatní úkoly příliš jednoduché.
Úloha současně představuje jakéhosi žolíka - jejím vyřešením můžete nahradit body za libovolnou úlohu, kterou jste nestihli nebo nezvládli vyřešit v průběhu semestru.
std::shared_ptr
Implementujte aplikaci pro příkazovou řádku, která bude číst matematické výrazy ze standardního vstupu a provádět nad nimi operace specifikované v argumentech z příkazové řádky (výpis, vyhodnocení, derivace, zjednodušení) 1). Až program narazí na konec vstupu (EOF), skončí.
Detailní zadání je uvedeno níže.
Protože implementovat celou aplikaci od nuly je poměrně dost práce, připravili jsme pro vás šablonu, která je dostupná na gitlabu. Součástí jsou Catch testy, pomocí kterých si můžete program postupně testovat. V upload systému se ale bude hodnotit pouze chování aplikace jako celku (byť pokrytí by mělo být stejné).
Pokud forknete repozitář se zadáním, nastavte Visibility2) na Private, abyste se vyhnuli problémům s plagiátorstvím.
Do upload systému tentokrát nahrajte všechny zdrojové soubory3). Soubory s
testy (podadresář tests
) a knihovnu mapbox
neodevzdávejte.
Na gitlabu je i konfigurace pro Gitlab CI4)
.gitlab-ci.yml
pro možnost spuštění testů tam. Více informací na
stránce o gitu
a stránce o semestrálce.
Jméno souboru v hranatých závorkách vyjadřuje doporučené místo implementace.
expr_base
pro každou matematickou operaci (samozřejmě to mohou být i nepřímí potomci, tedy “vnoučata”). [expr_impl.cpp
a expr_impl.hpp
]
write
. Všechny ostatní implementujte pomocí dummy kódu throw std::logic_error(“not implemented yet”);
.
expr
. Dále implementujte statické metody expr::number
a expr::variable
[expr.cpp
]
create_expression_tree
. Doporučujeme použít dodaný tokenizer. Při chybě parsování vyhoďte výjimku parse_error
.
handle_expr_line
, která bere seznam příkazů a řádku standardního vstupu. Výstup pak vypisuje do předaného výstupního proudu. [app.cpp
]
parse_command
, stačí použít a doplnit kostru funkce process_expr
.
main
: [main.cpp
]
parse_command
.
evaluate
. Měly by začít procházet testy ze sekce “Evaluate”.
expr::ZERO
, expr::ONE
jsou už definované v expr.cpp
.
derive
. Příslušné testy by měly začít procházet.
equals
. Zde se bude hodit dynamic_cast
.
simplify
. Příslušné testy by měly začít procházet.
Výchozí kód používá std::shared_ptr
, což je další chytrý ukazatel. Na rozdíl
od std::unique_ptr
ale jde kopírovat – interně si počítá, kolik instancí
shared_ptr
ukazuje na daný objekt, a teprve když zaniká poslední reference,
paměť dealokuje.
Někdy nastane situace, že z metody objektu spravovaného pomocí shared_ptr budete
chtít vrátit shared_ptr na this
. To nejde udělat prostým voláním
std::make_shared(this)
, protože this
už je někým spravován (nějakým
jiným shared pointrem). Takto by měl this
dva vlastníky (s různými reference
county) a nastaly by problémy s pamětí (double free, use after free). My chceme
využít již existující shared_ptr a pouze zvýšit jeho reference count. Ale jak ho
získat? Přesně k tomu slouží pomocná třída std::enable_shared_from_this
, od
které podědíme náš objekt, a v něm už pak jen zavoláme shared_from_this()
(viz
reference)
Reference:
Na každém neprázdném řádku standardního vstupu bude jeden výraz (a každý výraz bude právě na jednom řádku).
Evaluátor musí podporovat čísla, proměnné, funkce sin
, cos
, log
a 5
základních matematických operátorů, včetně jejich priorit a asociativity.
Zároveň musí podporovat změnění asociativity a priorit pomocí závorek.
Operátor | Priorita | Asociativita |
---|---|---|
^ 5) | 3 | Pravá |
* , / | 2 | Levá |
+ , - | 1 | Levá |
Vstup se skládá z čísel, identifikátorů, operátorů, závorek a blíže
nespecifikovaného množství whitespace. To znamená, že 1 + 2
je ekvivalentní
1+2
, ale i 1 +2
, 1+ 2
, (1 + 2)
nebo dokonce ((1) + (2))
.
Pokud je vstup chybný, to jest, obsahuje špatně ozávorkované výrazy (např. )2 + 1(
),
přebytečné operátory (např. 1 + 1 +
), neplatné znaky (1+5%
), neznámou
funkci (tanh(x)
) a podobně, program vypíše chybu a dál daný výraz nezpracovává.
Unární mínus (tedy negace) není pro jednoduchost zahrnuto – výraz -x
se dá ekvivalentně zapsat jako 0-x
.
V parseru doporučujeme použít dodaný Tokenizer
. Jeho popis je v hlavičkovém
souboru a příklad jeho funkce naleznete v testech.
Jako parametry přebírá program pouze sekvenci příkazů, které se postupně provedou nad každým zadaným výrazem. Každý parametr určuje jeden příkaz.
Vytiskne aktuální výraz v prefixové notaci. Čísla a proměnné se vypíšou bez závorek. Pokud jste někdy potkali nějakou variantu jazyka LISP, bude vám formát výstupu povědomý.
Příklad6):
$ ./symcalc print > 1 1 > variable variable > 1+x (+ x 1) > 1 * sin(x) (* 1 (sin x))
Vyhodnotí aktuální výraz a vypíše výsledek. Přiřazení hodnot proměnných má tvar
proměnná=číslo
, jednotlivá přiřazení jsou oddělena dvojtečkou. Není chybou,
pokud se např. uvedená varB
ve výrazu nevyskytuje. Pokud je ale ve výrazu proměnná,
která nemá přiřazenou hodnotu, je to chyba.
Příklad:
$ ./symcalc evaluate:x=1:y=2 > x+y 3 > z ! error: unbound variable > 42 42
Zderivuje aktuální výraz podle proměnné x
. Proměnná se ve výrazu nemusí vyskytovat.
Další příkazy pak pracují nad zderivavaným výrazem.
Aby se dala správnost výstupu rozumně vyhodnotit, použijte přesně pravidla
uvedená v dokumentaci metody derive
.
\begin{align*} (f+g)' &= f' + g' \\ (f-g)' &= f' - g' \\ (f\cdot g)' &= f'\cdot g + f\cdot g' \\ (f/g)' &= (f'\cdot g - f\cdot g')/g^2 \\ (f^g)' &= f^g \cdot ( (f'\cdot g)/f + log(f)\cdot g' ) \\ sin(f)' &= cos(f) \cdot f' \\ cos(f)' &= (0-sin(f)) \cdot f' \\ log(f)' &= f' / f \\ \end{align*} kde ' značí derivaci dle dané proměnné.
Příklad:
$ ./symcalc derive:x print > 42 0 > x 1 > y 0 > 1*x (+ (* 0 x) (* 1 1))
Zjednoduší aktuální výraz dle daných pravidel.
Další příkazy pak pracují nad zjednodušeným výrazem.
Přesný seznam pravidel je v dokumentaci metody simplify
.
\begin{align*}
0+x &= x \\
x+0 &= x \\
x-0 &= x \\
0\cdot x &= 0 \\
x\cdot 0 &= 0 \\
1\cdot x &= x \\
x\cdot 1 &= x \\
0/0 &= 0/0 \\
0/x &= 0 \\
x/1 &= x \\
x^1 &= x \\
0^0 &= 1 ~~ † \\
x^0 &= 1 \\
0^x &= 0 \\
log(1) &= 0 \\
\end{align*}
kde x
je jakýkoliv výraz.
† To striktně vzato nemusí být pravda, nicméně toto je častá interpretace a je konzistentní s chováním std::pow.
==
pro expr
(který volá metodu equals
) a konstanty expr::ZERO
, expr::ONE
Pokud nějaký příkaz selže (např. chybějící proměnná pro evaluate), měl by vypsat chybu. Text chyby by měl být ideálně smysluplný a popisovat její příčinu, pro testy však dostačuje vypsat řádek, který začíná vykřičníkem, zbytek se nekontroluje:
$ ./symcalc evaluate > x ! error: 26unbound_variable_exception: no value given for variable x
Program by měl také po vyhlášení chyby pokračovat čtením dalšího výrazu.
$ ./symcalc evaluate:x=2 derive:x simplify print > 1+2.5*x 6 2.5 > x*x 4 (+ x x) > sin(0.5*x) 0.841471 (* (cos (* 0.5 x)) 0.5) > x/y ! error: unbound variable y > x/5 0.4 (/ 5 (^ 5 2))
V tomto příkladu se zadaný výraz nejdříve vyhodnotí (a vypíše výsledek), pak se
zderivuje podle proměnné x
, zderivovaný výraz se zjednoduší, a až tento
zjednodušený výraz se vypíše. Pokud některý z příkazů pro výraz selže, vypíše se
chyba a další příkazy se pro tento výraz již nevykonávají. Program ale pokračuje
dál čtením dalšího výrazu ze standardního vstupu.
Takto vypadá výrazový strom (expression tree) pro výraz “sin(x) + 2*6”. Každý uzel stromu je sám o sobě výrazem (a tedy jde vypsat, zderivovat, vyhodnotit, atd.) a obsahuje své podvýrazy (pokud nějaké má).
Pro strojové zpracování je LISPovská prefixová notace výpisu výrazů ideální,
pro lidi se ale spíš hodí klasický infixový výpis. Hodilo by se tedy, kdyby
šlo výraz vypsat oběma způsoby. To je poměrně přímočaré na úrovni virtuální metody
write
(stačí přidat parametr), ale jak tuto variabilitu přenést do veřejného rozhraní?
Formátovaný výstup do streamu používá pro rozlišení formátů manipulátory, které mění interní stav streamu. Tady se ukazuje jedna ze slabin tohoto přístupu – není zrovna rozšiřitelný na další specifikace formátu. Mohli bychom zneužít nějaký flag, který náš výstup jinak neovlivní (např boolalpha), ale to je poměrně ošklivé řešení.
Mnohem lepší je zabalit expr
do nového pomocného typu, který si s
sebou ponese i informace o formátování, které můžeme využít v přetíženém operátoru
zápisu do streamu.
struct fmt_expr {const expr &e; expr::WriteFormat fmt;}; std::ostream& operator<<(std::ostream &os, fmt_expr e) { e.e->write(...); ... } ... std::cout << fmt_expr{my_expr, expr::WriteFormat::Infix};
Sekce | Body |
---|---|
Parse & print | 6 |
Evaluate | 1,5 |
Derive | 2,5 |
Simplify | 2,5 |
Error handling | 2,5 |
Bonus: different print formats | 1 |
Celkem | 16 |
Připomínáme, že z úlohy musíte získat alespoň 40% možných bodů (bez bonusu), tj. alespoň 8.
K úkolu dodáváme 3 druhy testů7).
Pro ladění doporučujeme použít přímé unit testy (tests-direct
), případně
potom tests-runner-direct
.
Tyto testy pro vás budou nejužitečnější, pokud použijete dodanou kostru aplikace.
Jsou to klasické testy v Catchi, které přímo volají jednotlivé funkce vašeho kódu.
V CMakeLists jsou definované jako target tests-direct
.
./tests-direct “[evaluate],[simplify]”
spustí všechny testy s tagy “evaluate” nebo “simplify”,
./tests-direct “~[evaluate]~[simplify]”
pak spustí všechny testy kromě testů s tagy “evaluate” nebo “simplify”.
Více v dokumentaci Catche.
Tyto testy jsou použity pro hodnocení. Spouští vaši aplikaci jako samostatný
proces, kterému předají parametry a výrazy na standardním vstupu dle zadání.
V CMakeLists jsou definované jako target tests-runner-subprocess
.
Pokud si chcete tyto testy spustit i u sebe (což není nutné, viz další sekce),
musíte testeru nastavit proměnnou prostředí
TEST_CMD
, ve které bude příkaz ke spuštění vašeho programu. Pokud spouštíte
testy přes make test
(nebo má vaše IDE integraci s CTestem), je už vše nastaveno.
CLion tuto integraci zatím nemá, je tedy nutné editovat konfiguraci pro tests-runner-subprocess
a do Environment variables přidat TEST_CMD=./symcalc
8).
Poslední typ testů je velmi podobný předchozím v tom, že k volání vašeho kódu používá
vysokoúrovňovou funkci handle_expr_line
. Tyty testy jsou tak (téměř) identické
s temi, co běží v odevzdávacím systému, ale jsou jednodušší a flexibilnější k použití.
V CMakeLists jsou definované jako target tests-runner-direct
.
V šabloně úkolu jsou dvě třídy výrazů – expr
a expr_base
. Třída expr_base
slouží jako vlastní interface – definuje (čistě) virtuální metody, které
musí její potomci (jednotlivé typy výrazů) implementovat.
Naproti tomu třída expr
slouží jako tenký wrapper nad std::shared_ptr<expr_base>
,
který je její jedinou datovou položkou. Význam této třídy je dvojí:
expr
místo std::shared_ptr<expr_base>
.
Pro první účel by se alternativně dalo využít typových aliasů (typedef
),
nicméně expr
by pak byl identický s std::shared_ptr<expr_base>
– měl
by všechny jeho veřejné metody a přetížené operátory by pracovaly nad tímto
shared_ptr
(a potenciálně by nám překážely operátory definované už pro
obecný shared_ptr
). Toto zapouzdření pomocí kompozice vytváří nový typ a
máme plnou kontrolu nad tím, jaké operace bude podporovat. V C++ toto navíc
nemá žádný performance overhead. Třída expr
je tedy ta, kterou by měla
používat většina kódu.
valgrind ./symcalc