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

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
/*

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