Note de curs, probleme algoritmică, clasa IX/X, 14 noiembrie 2014
From Algopedia
/* 3+(x-4*5)*5+9*y*y-z - + z + * 3 * * y - 5 9 y x * 4 5 2+2*2 + 2 * 2 2 */ #include <cstdio> #include <string> #include <iostream> using namespace std; class Nod { public: virtual int evaluare() const = 0; virtual ~Nod() { ; } virtual void print(ostream &f) const = 0; friend ostream& operator << (ostream &f, const Nod& x) { x.print(f); return f; } }; class Operatie : public Nod { public: char op; Nod* fiuSt; Nod* fiuDr; int evaluare() const { int answer; switch (op) { case '+': answer = fiuSt->evaluare() + fiuDr->evaluare(); break; case '-': answer = fiuSt->evaluare() - fiuDr->evaluare(); break; case '*': answer = fiuSt->evaluare() * fiuDr->evaluare(); break; case '/': answer = fiuSt->evaluare() / fiuDr->evaluare(); break; } return answer; } ~Operatie() { ; } void print(ostream &f) const { f << '(' << *fiuSt << op << *fiuDr << ')'; } }; class Valoare : public Nod { public: int valoare; int evaluare() const { return valoare; } ~Valoare() { ; } void print(ostream &f) const { f << valoare; } }; Nod* expresie(char* &adresa); // factor = necunoscuta // factor = constanta // factor = (expresie) Nod* factor(char* &adresa) { if ( adresa[0]>='0'&&adresa[0]<='9' ){ Valoare* rezultat=new Valoare; rezultat->valoare=adresa[0]-'0'; ++adresa; return rezultat; } else if ( adresa[0]=='(' ){ ++adresa; Nod* rezultat=expresie(adresa); if (adresa[0] != ')') { throw "Lipseste ')'"; } ++adresa; // ')' return rezultat; } else { throw "Astept o valoare sau o paranteza"; } } // termen = factor*factor // termen = factor/factor // termen = factor/factor... Nod* termen(char* &adresa) { Nod* rezultat = factor (adresa); while (adresa[0] == '*' || adresa[0] == '/') { ++adresa; Operatie* rezultatAux = new Operatie(); rezultatAux->op = adresa[-1]; rezultatAux->fiuSt = rezultat; rezultatAux->fiuDr = factor (adresa); rezultat = rezultatAux; } return rezultat; } // expresie = termen+termen // expresie = termen+termen+termen // expresie = termen-termen // expresie = termen-termen-termen Nod* expresie(char* &adresa) { Nod* rezultat = termen (adresa); while (adresa[0] == '+' || adresa[0] == '-') { ++adresa; Operatie* rezultatAux = new Operatie(); rezultatAux->op = adresa[-1]; rezultatAux->fiuSt = rezultat; rezultatAux->fiuDr = termen (adresa); rezultat = rezultatAux; } return rezultat; } Nod* construiesteArbore(char* V) { char* adresa = V; Nod* rezultat = expresie(adresa); if (adresa[0] != 0) { throw "Sirul nu s-a evaluat complet"; } return rezultat; } const int MAX_N = 10000; char V[MAX_N + 1]; int main(void) { // citirea datelor scanf("%s", V); // calcularea solutiei try { Nod* radacina = construiesteArbore(V); int answer = radacina->evaluare(); cout << *radacina; printf(" = %d\n", answer); } catch (char const* &error) { printf("%s\n", error); } return 0; }