Difference between revisions of "Clasele 9-10 lecția 3 - 2 oct 2015"

From Algopedia
Jump to navigationJump to search
(Created page with "= Prima oră = <syntaxhighlight> #include <cstdio> #include <cctype> // 2+2*2 // 6 // (+ (* 2 2) 2) // Expresie = Termen + Termen + Termen + ... // Termen = Factor * Facto...")
 
(No difference)

Latest revision as of 15:32, 4 December 2015

Prima oră

#include <cstdio>
#include <cctype>

// 2+2*2
// 6

// (+ (* 2 2) 2)

// Expresie = Termen + Termen + Termen + ...
// Termen = Factor * Factor * Factor * ...
// Factor = (Expresie) | Număr

// E = T | T + T | T + T + T + ...
// T = F | F * F | F * F * F * ...
// F = (E) | Nr

// E = T + T = F + F * F = Nr + Nr * Nr = 2 + 2 * 2
/*
     E
   / | \
  T  +  T
  |   / | \
  F   F * F
  |   |   |
  Nr  Nr  Nr
  |   |   |
  2   2   2

Ex2: (2+3)*2

E = T = F * F = (E) * Nr = (T+T) * 2 = (F+F)*2 =
  = (Nr+Nr)*2 = (2+3)*2


= 2/2/2 = (2/2)/2 st->dr
        = 2/(2/2) dr->st

*/

int E(char* &sir);
int T(char* &sir);
int F(char* &sir);
int Nr(char* &sir, int raspuns = 0);

//2+2*2
//2
//2+2
//2+2+2+2+2+2
//(2+2)*2+2
int E(char* &sir) { // variabia sir = adresa primului
	// caracter din sirul care se va evalua (si care
	// se poate deriva dintr-un E
	//printf("%c", sir[0]);
	int raspuns = T(sir);
	// avansam pana la sf. primului termen
	while (sir[0] == '+') {
		sir++;
		raspuns += T(sir);
	}
	return raspuns;
}

int T(char* &sir) {
	int raspuns = F(sir);
	// avansam pana la sf. primului termen
	while (sir[0] == '*') {
		sir++;
		raspuns *= F(sir);
	}
	return raspuns;
}
// E = T | T + T | T + T + T + ...
// T = F | F * F | F * F * F * ...
// F = (E) | Nr
//(

int F(char* &sir) {
	int raspuns;
	if (sir[0] == '(') {
		sir++; // '('
		raspuns = E(sir);
		sir++; // ')'
	} else if (isdigit(sir[0])) {
		raspuns = Nr(sir);
	} else {
		throw sir;
	}
	return raspuns;
}

//2345
//2
/*
int Nr(char* &sir) {
	int raspuns = 0;
	while (isdigit(sir[0])) {
		raspuns *= 10;
		raspuns += sir[0] - '0';
		sir++;
	}
	return raspuns;
}//*/

int Nr(char* &sir, int raspuns) {
	if (isdigit(sir[0])) {
		int cifra = sir[0] - '0';
		sir++;
		return Nr(sir, raspuns * 10 + cifra);
	} else {
		return raspuns;
	}
}

int main(void) {
	const int MAX_SIZE = 100;
	char sir[MAX_SIZE + 1];

	// citirea datelor
	fgets(sir, MAX_SIZE, stdin);

	// calcularea solutiei
	try {
		char* s = sir;
		int raspuns = E(s);
		if (*s != '\n') {
			throw s;
		}
		// afisarea solutiei
		printf("%d\n", raspuns);
	} catch (char* sir) {
		fprintf(stderr, "Am o eroare aici: %s\n", sir);
	}
	return 0;
}

A doua oră

În a doua oră am discutat pe scurt idei de rezolvare pentru problema 1220 - Stacks (Timus) dată ca temă data trecută.

Soluția propusă de mine a fost să simulăm o listă simplu înlănțuită de întregi cu ajutorul a doi vectori: unul de unsigned int (pentru stocarea valorilor) și unul de unsigned short int (pentru stocarea indicilor elementelor aterioare din stive).

unsigned int valoare[100001];
unsigned short int anterior[100001];

unsigned short int inceputStiva[1001];

Singura problemă cu această abordare este că indicii stocați în vectorul anterior au nevoie de 17 biți pentru a fi stocați (cu unul mai mult decât permite tipul de date unsigned short int). Soluția se bazează pe observația că valorile stocate în vectorul valoare nu folosesc decât 30 de biți din cei 32 disponibili, astfel că putem folosi unul dintre cei doi rămași pentru a stoca complet indicele elementului anterior din stivă.

Temă

Pentru data viitoare veți avea de rezolvat următoarele 4 probleme: