V tomto úkolu si konečně odpočineme od listu a místo toho naimplementujeme parser a vyhodnocovač matematických výrazů. Aby to bylo trochu jednodušší, nebudete muset pracovat s funkcemi (sin
, cos
, etc) ani s proměnnými.
Váš evaluátor musí podporovat alespoň 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 |
---|---|---|
^ 1) | 3 | Pravá |
* , / | 2 | Levá |
+ , - | 1 | Levá |
Vstup se skládá z čísel, 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))
. Můžete ale předpokládat, že vstup je vždy správný, to jest, neobsahuje špatně ozávorkované výrazy, například )2 + 1(
, přebytečné operátory, například 1 + 1 +
, ani nic podobného.
Potřebné hlavičkové soubory a testy jsou ke stažení zde.
Vstup | Výsledek |
---|---|
1 + 2 | 3 |
1 + 2 * 3 | 7 |
1 | 1 |
2^3^3 | 134217728 |
(2^3)^3 | 512 |
Všechny soubory, které implementují vaše řešení úlohy, specificky, pokud jste vytvořili nové .hpp
soubory, tak je nezapomeňte odevzdat. Nemusíte odevzdávat expr.hpp
, ani žádné testovací soubory.
Operátor pro výpis do proudu (<<
) netestujeme, je pouze pro vaše potřeby – v případě chyby v testu se přes něj vypíše interní stav vaší implementace. Co přesně bude vypisovat je pouze na vás.
Nezapomeňte, že konstruktory se dají dědit a pokud dědící třída nepřidala žádné další datové prvky, pouze chování, může být nejlepší si nechat konstruktor předka. Aby třída zdědila konstruktor předka, musí to explicitně deklarovat:
class base { public: base(int x): a(2*x) {} private: int a; }; class derived : public base { public: using base::base; // derived přebírá konstruktor předka -- base }; derived d(123); // Zde se zavolá přebraný konstruktor
Jeden z nejsnažších způsobů, jak parsovat infix matematické výrazy je převést je do postfix notace, která se snadno převede na tzv. výrazový strom.
Pro práci se vstupem doporučujeme použít std::stringstream, specificky formátovaný výstup ke čtení čísel a metod .peek()
a .get()
, které vám umožňují se podívat na první znak a přečíst (vyjmout z proudu) první znak respektive. Pro parsování vstupů pak doporučujeme funkce z hlavičky cctype, kde najdete například isdigit
, vracející true
pokud daný znak je číslo.
Pro vyhodnocení výrazu se vám budou hodit funkce z hlavičky cmath, kde najdete například pow
sloužící k exponenciaci reálných čísel.