https://www.algopedia.ro/wiki/index.php?title=Note_de_curs,_probleme_algoritmic%C4%83,_clasa_IX/X,_28_noiembrie_2014&feed=atom&action=history
Note de curs, probleme algoritmică, clasa IX/X, 28 noiembrie 2014 - Revision history
2024-03-29T06:10:47Z
Revision history for this page on the wiki
MediaWiki 1.40.0
https://www.algopedia.ro/wiki/index.php?title=Note_de_curs,_probleme_algoritmic%C4%83,_clasa_IX/X,_28_noiembrie_2014&diff=12408&oldid=prev
Dan: Created page with "<pre> #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 *..."
2015-06-23T22:03:47Z
<p>Created page with "<pre> #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 *..."</p>
<p><b>New page</b></p><div><pre><br />
#include <stdlib.h><br />
/*<br />
<br />
3+(x-4*5)*5+9*y*y-z<br />
<br />
-<br />
+ z<br />
+ *<br />
3 * * y<br />
- 5 9 y<br />
x *<br />
4 5<br />
<br />
2+2*2<br />
<br />
+<br />
2 *<br />
2 2<br />
<br />
*/<br />
<br />
// MAX_INT = 0111 1111 1111 1111 1111 1111 1111 1111<br />
// MIN_INT = 1000 0000 0000 0000 0000 0000 0000 0000<br />
// -1 = 1111 1111 1111 1111 1111 1111 1111 1111+<br />
// 1<br />
// = 0000 0000 0000 0000 0000 0000 0000 0000<br />
<br />
// MAX_INT = 0111 1111 1111 1111 1111 1111 1111 1111<br />
// MAX_INT=0x7fffffff;<br />
// MIN_INT = 1000 0000 0000 0000 0000 0000 0000 0000<br />
// MIN_INT=0x80000000;<br />
<br />
//const int MIN_INT = 1 << 31;<br />
//const int MAX_INT = (1 << 31) - 1;<br />
const int MAX_INT = 0x7fffffff;<br />
const int MIN_INT = 0x80000000;<br />
<br />
#include <cstdio><br />
#include <string><br />
#include <iostream><br />
<br />
using namespace std;<br />
<br />
class Nod {<br />
public:<br />
virtual int evaluare() const = 0;<br />
<br />
virtual int evaluare(int val) const = 0;<br />
<br />
virtual ~Nod() {<br />
;<br />
}<br />
<br />
virtual void print(ostream &f) const = 0;<br />
<br />
virtual Nod* derivative(char var) const = 0;<br />
<br />
friend ostream& operator << (ostream &f, const Nod& x) {<br />
x.print(f);<br />
return f;<br />
}<br />
};<br />
<br />
class Operatie : public Nod {<br />
public:<br />
char op;<br />
Nod* fiuSt;<br />
Nod* fiuDr;<br />
<br />
int evaluare(int val) const {<br />
int answer;<br />
switch (op) {<br />
case '+':<br />
answer = fiuSt->evaluare(val) + fiuDr->evaluare(val);<br />
break;<br />
case '-':<br />
answer = fiuSt->evaluare(val) - fiuDr->evaluare(val);<br />
break;<br />
case '*':<br />
answer = fiuSt->evaluare(val) * fiuDr->evaluare(val);<br />
break;<br />
case '/':<br />
answer = fiuSt->evaluare(val) / fiuDr->evaluare(val);<br />
break;<br />
}<br />
return answer;<br />
}<br />
<br />
int evaluare() const {<br />
return this->evaluare(MIN_INT);<br />
}<br />
<br />
~Operatie() {<br />
;<br />
}<br />
<br />
void print(ostream &f) const {<br />
f << '(' << *fiuSt << op << *fiuDr << ')';<br />
}<br />
<br />
Nod* derivative(char var) const {<br />
switch(op){<br />
case '+':<br />
{<br />
Operatie* answer = new Operatie;<br />
answer->op= '+';<br />
answer->fiuSt= this->fiuSt->derivative(var);<br />
answer->fiuDr= this->fiuDr->derivative(var);<br />
return answer;<br />
}<br />
case '-':<br />
{<br />
Operatie* answer = new Operatie;<br />
answer->op= '-';<br />
answer->fiuSt= this->fiuSt->derivative(var);<br />
answer->fiuDr= this->fiuDr->derivative(var);<br />
return answer;<br />
}<br />
case '*':<br />
{<br />
Operatie* answer = new Operatie;<br />
answer->op= '+';<br />
Operatie* fiuSt = new Operatie;<br />
fiuSt->op='*';<br />
answer->fiuSt=fiuSt;<br />
Operatie* fiuDr = new Operatie;<br />
fiuDr->op='*';<br />
answer->fiuDr=fiuDr;<br />
fiuSt->fiuSt= this->fiuSt->derivative(var);<br />
fiuSt->fiuDr= this->fiuDr;<br />
fiuDr->fiuDr= this->fiuDr->derivative(var);<br />
fiuDr->fiuSt= this->fiuSt;<br />
return answer;<br />
}<br />
case '/':<br />
{<br />
Operatie* answer = new Operatie;<br />
answer->op='/';<br />
Operatie* numarator = new Operatie;<br />
answer->fiuSt= numarator;<br />
numarator->op= '-';<br />
Operatie* fiuSt = new Operatie;<br />
fiuSt->op='*';<br />
numarator->fiuSt=fiuSt;<br />
Operatie* fiuDr = new Operatie;<br />
fiuDr->op='*';<br />
numarator->fiuDr=fiuDr;<br />
fiuSt->fiuSt= this->fiuSt->derivative(var);<br />
fiuSt->fiuDr= this->fiuDr;<br />
fiuDr->fiuDr= this->fiuDr->derivative(var);<br />
fiuDr->fiuSt= this->fiuSt;<br />
Operatie* numitor = new Operatie;<br />
answer->fiuDr= numitor;<br />
numitor->op= '*';<br />
numitor->fiuSt= this-> fiuDr;<br />
numitor->fiuDr= this-> fiuDr;<br />
return answer;<br />
}<br />
}<br />
/*if (this->nume == var) {<br />
Valoare* answer = new Valoare;<br />
answer->valoare = 1;<br />
return answer;<br />
} else {<br />
Necunoscuta* answer = new Necunoscuta;<br />
answer->nume = this->nume;<br />
return answer;<br />
}*/<br />
}<br />
};<br />
<br />
class Valoare : public Nod {<br />
public:<br />
int valoare;<br />
<br />
int evaluare() const {<br />
return valoare;<br />
}<br />
<br />
int evaluare(int val) const {<br />
return valoare;<br />
}<br />
<br />
~Valoare() {<br />
;<br />
}<br />
<br />
void print(ostream &f) const {<br />
f << valoare;<br />
}<br />
<br />
Nod* derivative(char var) const {<br />
Valoare* answer = new Valoare;<br />
answer->valoare = 0;<br />
return answer;<br />
}<br />
};<br />
<br />
class Necunoscuta : public Nod {<br />
public:<br />
char nume;<br />
<br />
int evaluare() const {<br />
throw "Functia nu se poate evalua";<br />
return 0;<br />
}<br />
<br />
int evaluare(int val) const {<br />
if (val == MIN_INT) {<br />
throw "Functia nu se poate evalua";<br />
}<br />
return val;<br />
}<br />
<br />
~Necunoscuta () {<br />
;<br />
}<br />
<br />
void print (ostream &f) const {<br />
f << nume;<br />
}<br />
<br />
Nod* derivative(char var) const {<br />
if (this->nume == var) {<br />
Valoare* answer = new Valoare;<br />
answer->valoare = 1;<br />
return answer;<br />
} else {<br />
Necunoscuta* answer = new Necunoscuta;<br />
answer->nume = this->nume;<br />
return answer;<br />
}<br />
}<br />
};<br />
<br />
Nod* expresie(char* &adresa);<br />
<br />
// factor = necunoscuta<br />
// factor = constanta<br />
// factor = (expresie)<br />
Nod* factor(char* &adresa) {<br />
if ( adresa[0]>='0'&&adresa[0]<='9' ){<br />
Valoare* rezultat=new Valoare;<br />
rezultat->valoare=adresa[0]-'0';<br />
++adresa;<br />
return rezultat;<br />
} else if ( adresa[0]=='(' ){<br />
++adresa;<br />
Nod* rezultat=expresie(adresa);<br />
if (adresa[0] != ')') {<br />
throw "Lipseste ')'";<br />
}<br />
++adresa; // ')'<br />
return rezultat;<br />
} else if ( 'a' <= adresa[0] && adresa[0] <= 'z' ) {<br />
Necunoscuta* rezultat = new Necunoscuta();<br />
rezultat->nume = adresa[0];<br />
++adresa;<br />
return rezultat;<br />
} else {<br />
throw "Astept o valoare sau o paranteza";<br />
}<br />
}<br />
<br />
// termen = factor*factor<br />
// termen = factor/factor<br />
// termen = factor/factor...<br />
Nod* termen(char* &adresa) {<br />
Nod* rezultat = factor (adresa);<br />
while (adresa[0] == '*' || adresa[0] == '/') {<br />
++adresa;<br />
Operatie* rezultatAux = new Operatie();<br />
rezultatAux->op = adresa[-1];<br />
rezultatAux->fiuSt = rezultat;<br />
rezultatAux->fiuDr = factor (adresa);<br />
rezultat = rezultatAux;<br />
}<br />
<br />
return rezultat;<br />
}<br />
<br />
// expresie = termen+termen<br />
// expresie = termen+termen+termen<br />
// expresie = termen-termen<br />
// expresie = termen-termen-termen<br />
Nod* expresie(char* &adresa) {<br />
Nod* rezultat = termen (adresa);<br />
while (adresa[0] == '+' || adresa[0] == '-') {<br />
++adresa;<br />
Operatie* rezultatAux = new Operatie();<br />
rezultatAux->op = adresa[-1];<br />
rezultatAux->fiuSt = rezultat;<br />
rezultatAux->fiuDr = termen (adresa);<br />
rezultat = rezultatAux;<br />
}<br />
<br />
return rezultat;<br />
}<br />
<br />
Nod* construiesteArbore(char* V) {<br />
char* adresa = V;<br />
Nod* rezultat = expresie(adresa);<br />
if (adresa[0] != 0) {<br />
throw "Sirul nu s-a evaluat complet";<br />
}<br />
return rezultat;<br />
}<br />
<br />
const int MAX_N = 10000;<br />
<br />
char V[MAX_N + 1];<br />
<br />
int main(void) {<br />
//printf("%d\n", rand() % 2);<br />
printf("MIN_INT = %d\n", MIN_INT);<br />
printf("MAX_INT = %d\n", MAX_INT);<br />
// citirea datelor<br />
scanf("%s", V);<br />
<br />
// calcularea solutiei<br />
try {<br />
Nod* radacina = construiesteArbore(V);<br />
int answer = radacina->evaluare(10);<br />
cout << "f(x) = ";<br />
cout << *radacina << endl;<br />
cout << "f(10) = " << answer << endl;<br />
<br />
cout << "f'(x) = " <<<br />
*(radacina->derivative('x')) << endl;<br />
} catch (char const* &error) {<br />
cout << error;<br />
}<br />
<br />
return 0;<br />
}<br />
</pre></div>
Dan