Clasele 9-10 lecția 3 - 2 oct 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:
