Scrii programul care verifică dacă parantezele dintr-o expresie se închid corect: fiecare ), ] sau } trebuie să închidă ultima paranteză rămasă deschisă.
paranteze.cpp, în consolă
{[()()]}DA([)]
NU
Partea a doua din trei despre structuri de date. „Ultima deschisă se închide prima” e exact regula unei stive, ca un teanc de farfurii.
să implementezi o stivă cu un vector și vârful vf
să implementezi o coadă cu doi indici, prim și ultim
să verifici paranteze echilibrate
să folosești stack și queue din biblioteca standard
Pasul 2 din 5
Rulează-l linie cu linie
Trei elemente intră în stivă, unul iese. Panoul arată și conținutul stivei, de la bază la vârf.
Linia 5. Vectorul ține elementele, vf ține poziția vârfului. 0 înseamnă stivă goală; elementele stau pe pozițiile 1, 2, 3…
Linia 6.++vf crește întâi vârful la 1, apoi pune 4 pe poziția 1. Operația se numește push.
Linia 7. 7 se pune deasupra, pe poziția 2.
Linia 8. 1 ajunge în vârf, pe poziția 3.
Linia 9.Pop: scoți vârful doar scăzând vf. Valoarea 1 rămâne în memorie, dar nu mai face parte din stivă.
Linia 10. Vârful e acum 7, pe poziția 2.
Linia 11.main se încheie.
Gata. Ultimul intrat, 1, a fost primul ieșit. Asta înseamnă LIFO: last in, first out.
Prezice ieșirea
Repeți vf--; încă o dată înainte de afișare. Ce apare?
Răspuns: „4 1”.
Două scoateri lasă în stivă doar elementul de la bază, 4, pe poziția 1.
Pasul 3 din 5
Stiva, coada și biblioteca standard
Fragmentele 1–3 stau în main. Cardul 4 e un program complet.
1
Stiva golită: ordinea inversă
lifo.cpp
int st[100], vf = 0;for (int x = 1; x <= 4; x++) st[++vf] = x * 10;while (vf > 0) { cout << st[vf] << ' '; vf--;}
Ce apare pe ecran
40 30 20 10
Intră 10, 20, 30, 40 și ies invers. De aceea stiva servește la „anulează” într-un editor, la apelurile de funcții și la orice problemă în care ultimul lucru început se termină primul.
2
Coada: primul venit, primul servit
coada.cpp
int c[100], prim = 1, ultim = 0;for (int x = 1; x <= 4; x++) c[++ultim] = x * 10;prim++;c[++ultim] = 50;while (prim <= ultim) { cout << c[prim] << ' '; prim++;}
Ce apare pe ecran
20 30 40 50
Elementele intră la ultim și ies de la prim. prim++ a scos 10, primul intrat. Coada e goală când prim > ultim. E regula FIFO: first in, first out.
Cu un singur fel de paranteză, stiva poate fi doar un contor: vf numără parantezele deschise. Expresia e corectă dacă nicio închidere nu vine pe stivă goală și dacă la final nu rămâne nimic deschis.
Biblioteca standard le are gata: push adaugă, pop scoate, top și front arată elementul următor. La bac se cere de obicei implementarea cu vector; în proiecte, folosește STL.
Capcană: uiți verificarea de la final
Algoritmul verifică doar închiderile. În „(()” nicio închidere nu e greșită, dar o paranteză rămâne deschisă:
Locurile de la început, eliberate de prim++, nu se mai folosesc. Repară cu o coadă circulară, în care indicii trec de la capăt înapoi la 1, sau cu queue din STL.
Pasul 4 din 5
Verifică-te
Cinci întrebări noi. După fiecare răspuns vezi imediat de ce e așa.
Stiva e 1, 2, 3. Scoaterea lasă 1, 2, apoi intră 4: 1, 2, 4. Vârful e 4, iar sub el e 2.
2 din 5 · Alege varianta
Documentele trimise la o imprimantă se tipăresc în ordinea în care au sosit. Ce structură folosești?
Răspuns: coadă.
Primul document trimis trebuie tipărit primul: FIFO. O stivă l-ar tipări întâi pe ultimul sosit.
3 din 5 · Prezice ieșirea
Ce afișează programul?
coada.cpp
#include<iostream>usingnamespace std;intmain() {int c[10], prim = 1, ultim = 0;for (int x = 1; x <= 3; x++) c[++ultim] = x; prim++; c[++ultim] = 4; cout << c[prim] << c[ultim];return0;}
Răspuns: „24”.
Coada e 1, 2, 3. prim++ îl scoate pe 1, primul intrat. Apoi 4 intră la coadă. Primul e acum 2, ultimul 4.
4 din 5 · Alege varianta
Ce răspunde programul complet pentru „{(})”?
Răspuns: NU.
După „{(” vârful stivei e „(”. Vine „}”, care ar trebui să închidă „{”, nu „(”. Contează și ordinea închiderilor, nu doar numărul lor.
5 din 5 · Alege varianta
Într-o stivă cu vector, cum arată operația push a lui x, dacă elementele stau de la poziția 1?
Răspuns: st[++vf] = x;
++vf crește vârful înainte de scriere, așa că primul element ajunge pe poziția 1. vf++ ar scrie pe poziția 0 și ar lăsa vf cu unu după vârf.
Pasul 5 din 5
Ce ai învățat
Stiva e LIFO: st[++vf] = x pune, vf-- scoate, st[vf] e vârful.
Coada e FIFO: intri la ultim, ieși de la prim; e goală când prim > ultim.
Parantezele sunt echilibrate dacă fiecare închidere se potrivește cu vârful și stiva rămâne goală.
stack și queue din STL fac aceleași operații, fără indici.
Programul complet
Trei feluri de paranteze, deci stiva ține caracterele deschise. strchr verifică dacă un caracter e unul dintre „([{”, iar pereche spune ce trebuie să fie în vârf.
paranteze.cpp
#include<iostream>#include<cstring>usingnamespace std;charpereche(char c) {if (c == ')') return'(';if (c == ']') return'[';return'{';}intmain() {char s[101], st[101];int vf = 0;bool ok = true; cin >> s;int k = 0;while (s[k] != 0 && ok) {char c = s[k++];if (strchr("([{", c)) st[++vf] = c;elseif (vf == 0) ok = false;else {char t = st[vf--]; ok = t == pereche(c); } }if (ok && vf == 0) cout << "DA";else cout << "NU";return0;}