1
1. De ce stiva si paranteze?
O expresie cu paranteze este echilibrata daca fiecare paranteza deschisa are o pereche inchisa, in ordinea corecta de cuibare.
Stiva este structura naturala pentru aceasta problema: principiul LIFO (Last In First Out) reflecta exact regula „ultima deschisa = prima de inchis”.
Vizualizare pas cu pas pentru {[()]}:
Pas Car Actiune Stiva dupa
---------------------------------------------
1 '{' push('{') ['{']
2 '[' push('[') ['{', '[']
3 '(' push('(') ['{', '[', '(']
4 ')' pop()='(' ['{', '[']
5 ']' pop()='[' ['{']
6 '}' pop()='{' []
Stiva goala? True => ECHILIBRATE
Cazuri care esueaza:
((a+b)— stiva nu e goala la final (ramane un()([)]— varful stivei este(dar intalnim]→ nepotrivire)— stiva goala la inchidere → eroare imediata
2
2. Algoritm Python: verificare paranteze
# Verificare paranteze echilibrate cu stiva def verifica_paranteze(expresie): stiva = [] perechi = {')': '(', ']': '[', '}': '{'} for car in expresie: if car in '([{': stiva.append(car) # push elif car in ')]}': if not stiva or stiva[-1] != perechi[car]: return False # stiva goala sau nepotrivire stiva.pop() # pop return len(stiva) == 0 # echilibrat daca stiva goala print(verifica_paranteze("(a+b)*[c-d]")) # True print(verifica_paranteze("((a+b)")) # False print(verifica_paranteze("{[()]}")) # True print(verifica_paranteze("([)]")) # False
Output real (rulat cu python):
True False True False
Complexitate: O(n) timp — fiecare caracter este procesat exact o data. O(n) spatiu — stiva retine cel mult n/2 paranteze deschise (cazul nefavorabil:
(((().
3
3. Notatia postfixata (Reverse Polish Notation)
In notatia infixata (obisnuita), operatorul este intre operanzi:
In notatia postfixata (RPN — Reverse Polish Notation), operatorul vine dupa operanzii sai:
Avantaj major: nu necesita paranteze si nu necesita reguli de precedenta la evaluare — ordinea calculelor este codificata implicit in sirul de tokeni.
a + b.In notatia postfixata (RPN — Reverse Polish Notation), operatorul vine dupa operanzii sai:
a b +.Avantaj major: nu necesita paranteze si nu necesita reguli de precedenta la evaluare — ordinea calculelor este codificata implicit in sirul de tokeni.
Corespondenta infix ↔ postfix:
Infix Postfix Rezultat ------------------------------------------------------ 3 + 4 * 2 -> 3 4 2 * + 11 (5 + 3) * 2 -> 5 3 + 2 * 16 10 + 2 * 8 - 3 -> 10 2 8 * + 3 - 23
Evaluare manuala a "3 4 2 * +":
Token Actiune Stiva
-------------------------------
3 push(3) [3]
4 push(4) [3, 4]
2 push(2) [3, 4, 2]
* pop b=2, pop a=4 [3]
push(4*2=8) [3, 8]
+ pop b=8, pop a=3 []
push(3+8=11) [11]
Rezultat: 11
4
4. Algoritm Python: evaluare postfix
# Evaluare expresie postfixata (RPN) cu stiva def evalueaza_postfix(expresie): stiva = [] tokeni = expresie.split() for token in tokeni: if token.lstrip('-').isdigit(): stiva.append(int(token)) # e numar -> push else: b = stiva.pop() # al doilea operand (dreapta) a = stiva.pop() # primul operand (stanga) if token == '+': stiva.append(a + b) elif token == '-': stiva.append(a - b) elif token == '*': stiva.append(a * b) elif token == '/': stiva.append(int(a / b)) return stiva[0] print(evalueaza_postfix("3 4 2 * +")) # 11 print(evalueaza_postfix("5 3 + 2 *")) # 16 print(evalueaza_postfix("10 2 8 * + 3 -")) # 23
Output real (rulat cu python):
11 16 23
Complexitate: O(n) timp — fiecare token este procesat exact o data. O(n) spatiu — stiva contine cel mult n/2 operanzi.
5
5. Conversie infix → postfix (Shunting-Yard) EXCLUSIV INTENSIV
⚡ Sectiune doar pentru profil intensiv informatica
Algoritmul Shunting-Yard (Dijkstra, 1961) transforma o expresie infixata in postfixata folosind o stiva de operatori. Este fundamentul compilatoarelor si calculatoarelor stiintifice care accepta expresii cu paranteze si precedenta.
Reguli Shunting-Yard:
- Numar → adauga direct la output
- Operator → cat timp varful stivei e operator cu precedenta ≥ operator curent, muta in output; apoi push operator curent
- ( → push pe stiva
- ) → muta din stiva in output pana la
(, apoi scoate( - Final → muta toti operatorii ramasi din stiva in output
# Conversie infix -> postfix (Shunting-Yard, Dijkstra 1961) def infix_la_postfix(expresie): precedenta = {'+': 1, '-': 1, '*': 2, '/': 2} stiva = [] rezultat = [] tokeni = expresie.split() for token in tokeni: if token.lstrip('-').isdigit(): rezultat.append(token) # numar -> direct in output elif token == '(': stiva.append(token) elif token == ')': while stiva and stiva[-1] != '(': rezultat.append(stiva.pop()) stiva.pop() # scoate '(' else: # operator while (stiva and stiva[-1] != '(' and stiva[-1] in precedenta and precedenta[stiva[-1]] >= precedenta[token]): rezultat.append(stiva.pop()) stiva.append(token) while stiva: rezultat.append(stiva.pop()) return ' '.join(rezultat) print(infix_la_postfix("3 + 4 * 2")) # 3 4 2 * + print(infix_la_postfix("( 5 + 3 ) * 2")) # 5 3 + 2 * print(infix_la_postfix("10 + 2 * 8 - 3")) # 10 2 8 * + 3 -
Output real (rulat cu python):
3 4 2 * + 5 3 + 2 * 10 2 8 * + 3 -
Complexitate: O(n) timp — fiecare token intra si iese din stiva cel mult o data. O(n) spatiu — stiva contine cel mult n/2 operatori simultan.
6
6. Implementare C++: std::stack si cei doi algoritmi EXCLUSIV INTENSIV
⚡ Sectiune doar pentru profil intensiv informatica
In C++ folosim std::stack<T> din <stack>. Metode: push(x), pop(), top(), empty(). Atentie: pop() nu returneaza valoarea — citeste cu top() inainte.
#include <iostream> #include <stack> #include <string> using namespace std; bool verificaParanteze(const string& expr) { stack<char> stiva; for (char c : expr) { if (c == '(' || c == '[' || c == '{') { stiva.push(c); } else if (c == ')' || c == ']' || c == '}') { if (stiva.empty()) return false; char top = stiva.top(); stiva.pop(); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return stiva.empty(); } int main() { cout << verificaParanteze("(a+b)*[c-d]") << endl; // 1 (true) cout << verificaParanteze("((a+b)") << endl; // 0 (false) cout << verificaParanteze("{[()]}") << endl; // 1 (true) cout << verificaParanteze("([)]") << endl; // 0 (false) return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
1 0 1 0
Nota: In C++,
bool cu cout apare ca 1 (true) sau 0 (false). Adauga cout << boolalpha; pentru text true/false explicit.
#include <iostream> #include <stack> #include <sstream> #include <string> using namespace std; int evalueazaPostfix(const string& expresie) { stack<int> stiva; istringstream iss(expresie); string token; while (iss >> token) { if (isdigit(token[0])) { stiva.push(stoi(token)); } else { int b = stiva.top(); stiva.pop(); int a = stiva.top(); stiva.pop(); if (token == "+") stiva.push(a + b); else if (token == "-") stiva.push(a - b); else if (token == "*") stiva.push(a * b); else if (token == "/") stiva.push(a / b); } } return stiva.top(); } int main() { cout << evalueazaPostfix("3 4 2 * +") << endl; // 11 cout << evalueazaPostfix("5 3 + 2 *") << endl; // 16 cout << evalueazaPostfix("10 2 8 * + 3 -") << endl; // 23 return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
11 16 23