Warning
This page is located in archive.

Parser 1

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.

Operátory a jejich vlastnosti

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á

Formát vstupu

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.

Příklady

Vstup Výsledek
1 + 2 3
1 + 2 * 3 7
1 1
2^3^3 134217728
(2^3)^3 512

Co odevzdat?

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.

Rady

Operátor výstupu

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.

Konstruktory se dají dědit

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

Postfix zápis

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.

Užitečné hlavičky

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.

1)
Exponenciace
courses/b6b36pjc/ukoly/parser-1.txt · Last modified: 2017/10/29 15:34 by horenmar