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

From Algopedia
Jump to navigationJump to search
#include <stdlib.h>
/*

3+(x-4*5)*5+9*y*y-z

                 -
           +      z
 +             *
3        *   *  y
    -     5 9 y
   x  *
     4 5

2+2*2

 +
2  *
  2 2

*/

// MAX_INT = 0111 1111 1111 1111 1111 1111 1111 1111
// MIN_INT = 1000 0000 0000 0000 0000 0000 0000 0000
//      -1 = 1111 1111 1111 1111 1111 1111 1111 1111+
//                                                 1
//         = 0000 0000 0000 0000 0000 0000 0000 0000

// MAX_INT = 0111 1111 1111 1111 1111 1111 1111 1111
// MAX_INT=0x7fffffff;
// MIN_INT = 1000 0000 0000 0000 0000 0000 0000 0000
// MIN_INT=0x80000000;

//const int MIN_INT = 1 << 31;
//const int MAX_INT = (1 << 31) - 1;
const int MAX_INT = 0x7fffffff;
const int MIN_INT = 0x80000000;

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

class Nod {
public:
	virtual int evaluare() const = 0;

	virtual int evaluare(int val) const = 0;

	virtual ~Nod() {
		;
	}

	virtual void print(ostream &f) const = 0;

	virtual Nod* derivative(char var) 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(int val) const {
		int answer;
		switch (op) {
		case '+':
			answer = fiuSt->evaluare(val) + fiuDr->evaluare(val);
			break;
		case '-':
			answer = fiuSt->evaluare(val) - fiuDr->evaluare(val);
			break;
		case '*':
			answer = fiuSt->evaluare(val) * fiuDr->evaluare(val);
			break;
		case '/':
			answer = fiuSt->evaluare(val) / fiuDr->evaluare(val);
			break;
		}
		return answer;
	}

	int evaluare() const {
		return this->evaluare(MIN_INT);
	}

	~Operatie() {
		;
	}

	void print(ostream &f) const {
		f << '(' << *fiuSt << op << *fiuDr << ')';
	}

	Nod* derivative(char var) const {
		switch(op){
		case '+':
		{
			Operatie* answer = new Operatie;
			answer->op= '+';
			answer->fiuSt= this->fiuSt->derivative(var);
			answer->fiuDr= this->fiuDr->derivative(var);
			return answer;
		}
		case '-':
		{
			Operatie* answer = new Operatie;
			answer->op= '-';
			answer->fiuSt= this->fiuSt->derivative(var);
			answer->fiuDr= this->fiuDr->derivative(var);
			return answer;
		}
		case '*':
		{
			Operatie* answer = new Operatie;
			answer->op= '+';
			Operatie* fiuSt = new Operatie;
			fiuSt->op='*';
			answer->fiuSt=fiuSt;
			Operatie* fiuDr = new Operatie;
			fiuDr->op='*';
			answer->fiuDr=fiuDr;
			fiuSt->fiuSt= this->fiuSt->derivative(var);
			fiuSt->fiuDr= this->fiuDr;
			fiuDr->fiuDr= this->fiuDr->derivative(var);
			fiuDr->fiuSt= this->fiuSt;
			return answer;
		}
		case '/':
		{
			Operatie* answer = new Operatie;
			answer->op='/';
			Operatie* numarator = new Operatie;
			answer->fiuSt= numarator;
			numarator->op= '-';
			Operatie* fiuSt = new Operatie;
			fiuSt->op='*';
			numarator->fiuSt=fiuSt;
			Operatie* fiuDr = new Operatie;
			fiuDr->op='*';
			numarator->fiuDr=fiuDr;
			fiuSt->fiuSt= this->fiuSt->derivative(var);
			fiuSt->fiuDr= this->fiuDr;
			fiuDr->fiuDr= this->fiuDr->derivative(var);
			fiuDr->fiuSt= this->fiuSt;
			Operatie* numitor = new Operatie;
			answer->fiuDr= numitor;
			numitor->op= '*';
			numitor->fiuSt= this-> fiuDr;
			numitor->fiuDr= this-> fiuDr;
			return answer;
		}
		}
		/*if (this->nume == var) {
			Valoare* answer = new Valoare;
			answer->valoare = 1;
			return answer;
		} else {
			Necunoscuta* answer = new Necunoscuta;
			answer->nume = this->nume;
			return answer;
		}*/
	}
};

class Valoare : public Nod {
public:
	int valoare;

	int evaluare() const {
		return valoare;
	}

	int evaluare(int val) const {
		return valoare;
	}

	~Valoare() {
		;
	}

	void print(ostream &f) const {
		f << valoare;
	}

	Nod* derivative(char var) const {
		Valoare* answer = new Valoare;
		answer->valoare = 0;
		return answer;
	}
};

class Necunoscuta : public Nod {
public:
	char nume;

	int evaluare() const {
		throw "Functia nu se poate evalua";
		return 0;
	}

	int evaluare(int val) const {
		if (val == MIN_INT) {
			throw "Functia nu se poate evalua";
		}
		return val;
	}

	~Necunoscuta () {
		;
	}

	void print (ostream &f) const {
		f << nume;
	}

	Nod* derivative(char var) const {
		if (this->nume == var) {
			Valoare* answer = new Valoare;
			answer->valoare = 1;
			return answer;
		} else {
			Necunoscuta* answer = new Necunoscuta;
			answer->nume = this->nume;
			return answer;
		}
	}
};

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 if ( 'a' <= adresa[0] && adresa[0] <= 'z' ) {
		Necunoscuta* rezultat = new Necunoscuta();
		rezultat->nume = adresa[0];
		++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) {
	//printf("%d\n", rand() % 2);
	printf("MIN_INT = %d\n", MIN_INT);
	printf("MAX_INT = %d\n", MAX_INT);
	// citirea datelor
	scanf("%s", V);

	// calcularea solutiei
	try {
		Nod* radacina = construiesteArbore(V);
		int answer = radacina->evaluare(10);
		cout << "f(x) = ";
		cout << *radacina << endl;
		cout << "f(10) = " << answer << endl;

		cout << "f'(x) = " <<
				*(radacina->derivative('x')) << endl;
	} catch (char const* &error) {
		cout << error;
	}

	return 0;
}