V tomto úkolu 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.

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.

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.