Note de curs, probleme algoritmică, clasa IX/X, 14 noiembrie 2014

/*

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;
}