1

Stiva

Stiva este un caz particular de listă liniară, adică o înşiruire de valori. De cele mai multe

ori stiva se implementează static, folosind vectori.

Definiţia listei liniare: O listă liniară este o secvenţă de elemente având acelaşi tip de

dată, în care fiecare element, cu excepţia ultimului, are un succesor direct şi fiecare element,

în afară de primul, are un predecesor direct. Operaţiile cele mai importante cu listele sunt

adăugarea şi extragerea unor elemente în sau din listă.

Definiţia stivei: O stivă este o listă în care adăugările şi extragerile de elemente se

efectuează la un singur capăt al listei, numit vârful stivei. Principiul de funcţionare al stivei

este “ultimul intrat, primul ieşit” sau LIFO (Last In, First Out).

Pentru a ne imagina o stivă, să ne gândim la mai multe farfurii aşezate una peste alta.

Când dorim să adăugăm o farfurie, o aşezăm peste celelalte, iar când luăm o farfurie, o luăm

pe cea aflată deasupra. Procedând în acest mod, evităm să spargem farfuriile!

Operaţiile caracteristice stivei sunt:

a) Crearea unei stive vide

b) Inserarea unui element în vârful stivei (operaţia PUSH)

c) Extragerea unui element din vârful stivei (operaţia POP)

d) Accesarea elementului din vârf, fără a modifica valoarea acestuia (operaţia TOP)

Rolul stivelor în informatică este unul fundamental. Pentru realizarea apelului funcţiilor şi

a recursivităţii este necesară structura de stivă. O altă aplicaţie a stivelor este evaluarea

expresiilor matematice şi compilarea programelor scrise într-un limbaj de programare. Prin

modul de funcţionare stiva are proprietatea de a extrage elementele introduse în stivă în

ordine inversă faţă de adăugărea lor.

Implementarea Stivei

Stiva, ca structură abstractă de date, poate fi implementată în diferite moduri. De exemplu,

putem implementa stiva ca un vector în care să reţinem elementele stivei. Pentru ca acest

vector să funcţioneze ca o stivă, singurele operaţii permise sunt operaţiile caracteristice stivei.

În continuare presupunem că dorim ca în stivă să se afle cel mult 100 de elemente.

Definirea unei stive într-un program C++ se poate scrie după cum urmează:

const int DMax=100; //numărul maxim de elemente

int S[DMax+1]; //stiva (vectorul) S

int k,x; //vârful stivei (egal cu numărul elementelor din listă)

// x elementul din vârf

a) Crearea unei stive vide:

k=0; // stiva nu are elemente

k=0

2

b) Inserarea unui element x în vârful stivei, operaţia PUSH(x):

if (k==DMax) //stiva este plină

cout<<”Eroare: stiva plină!”;

else //inserăm x în vârful stivei S S[++k] = x;

Modificările stivei prin operaţiile PUSH(7), PUSH(2), PUSH(5) sunt reprezentate în

figura următoare:

c) Extragerea unui element x din vârful stivei, operaţia POP(x):

if (k==0) //stiva este vidă

cout<<”Eroare: stiva vidă!”;

else //inserăm x în stiva S x = S[k--];

Prin extragerea elementului din vârful stivei, de pe nivelul k=3, aceasta revine la nivelul

anterior, k=2. Se consideră că elementul de pe nivelul 3 (fostul vârf al stivei) nu mai aparţine

stivei.

d) Operaţia TOP este o operaţie de informare, care permite consultarea valorii

elementului din vârful stivei, fără a modifica valoarea acestuia.

x = S[k];

k=0

k=1

k=2 2

7

k=3

2

7

5

7 2

k=3

2

7

2

7

k=2

5

3

Aplicaţie: Verificarea parantezelor

1. O aplicaţie utilă a structurei de tip stivă este algoritmul prin care se verifică dacă o

expresie ce conţine paranteze este bine formată. O expresie cu paranteze este un şir de

paranteze deschise ‘(‘ şi închise ‘)‘. Expresia este bine formată dacă:

-începe cu o paranteză deschisă (

-fiecare paranteză deschisă ( are o paranteză închisă corespunzătoare )

De exemplu, expresia ( ( ) ( ) ) este bine formată, iar expresia ( ( ) ( ) este incorectă.

Algoritmul pentru verificarea corectitudinii unei expresii cu paranteze foloseşte o stivă de

caractere, în care se memorează doar parantezele deschise (. Paşii algoritmului sunt:

- la citirea unei paranteze deschise, aceasta se adaugă în stivă cu PUSH (

- la citirea unei paranteze închise, verificăm dacă stiva conţine o paranteză deschisă ) şi o

scoatem din stivă cu POP; dacă apare eroare la operaţia POP atunci expresia este

incorectă (avem o paranteză închisă fără corespondent)

- la sfârşitul şirului, stiva trebuie să fie vidă, k=0, dacă expresia este bine formată

În continuare o să urmărim aplicarea algoritmului pentru şirul bine format ( ( ) ( ) ):

La început, stiva este vidă:

Şirul citit este “( ( ) ( ) )”

Primul character din şir ( este adăugat în stivă

( ( ) ( ) )

Al doilea caracter este tot o paranteză deschisă (

( ( ) ( ) )

k=0

k=1 (

k=2

(

(

4

Al treilea caracter citit este paranteza închisă pereche a ultimei paranteze adăugate,

care va fi extrasă din stivă:

( ( ) ( ) )

Urmează al patrulea caracter o nouă paranteză deschisă:

( ( ) ( ) )

Al cincilea caracter este paranteza închisă pereche a ultimei paranteze deschise:

( ( ) ( ) )

Ultimul caracter este paranteza închisă corespunzătoare primului caracter citit:

( ( ) ( ) )

În final, stiva este vidă, ceea ce înseamnă că expresia este corect construită!

2. Algoritmul de mai sus poate fi adaptat pentru expresii formate cu toate tipurile de

paranteze folosite la matematică paranteze mici, paranteze drepte şi acolade. Condiţiile de

funcţionare a algoritmului sunt aceleaşi, în plus mai trebuie să testăm ca o paranteză închisă

să aibă ca pereche în stivă o paranteză de acelaşi tip. Parantezele nu au voie să se

intersecteze, de exemplu şirul ( [ ) ] este incorect format. Spre deosebire de regulile de la

matematică într-o expresie cu mai multe tipuri de paranteze este permis ca parantezele drepte

sau acoladele să fie incluse între paranteze mici, adică ([]{}) este o expresie corectă.

k=2

(

(

k=1 (

k=2

(

(

k=2

(

(

k=1 (

k=0

k=1 (

5

În acest caz, paşii algoritmului sunt:

- la citirea oricărui tip de paranteză deschisă, aceasta se adaugă în stivă cu PUSH

- orice alt caractere care nu este o paranteză deschisă sau închisă se ignoră

- la citirea unei paranteze închise, verificăm dacă stiva conţine o paranteză deschisă de

acelaşi tip şi o scoatem din stivă cu POP; dacă apare eroare la operaţia POP atunci

expresia este incorectă (avem o paranteză închisă fără corespondent)

- la sfârşitul şirului, stiva trebuie să fie vidă, k=0, dacă expresia este bine formată

De exemplu, expresia (x{x[]}x)este evaluată aşa cum apare în imaginea următoare:

6

Fişierul intrare/ieşire:

paranteze.in, paranteze.out

Sursă Tiberiu Popoviciu 2011,

Clasa a 9-a

Autor Cosmin-Mihai Tutunaru Adăugată de

Cosmin-Mihai Tutunaru

•stocarul

Timp execuţie pe test

0.1 sec Limită de memorie

32768 kbytes

Scorul tău în arhivă N/A Dificultate N/A

Paranteze

Ţirbi tocmai a învăţat la un curs de Silverlight despre paranteze rotunde "(, )", drepte "[, ]" şi

acolade "{, }". Un şir este parantezat corect dacă este construit conform regulilor:

<şir parantezat corect> = <şirul vid>

<şir parantezat corect> = "(" + <şir parantezat

corect> + ")"

<şir parantezat corect> = "[" + <şir parantezat

corect> + "]"

<şir parantezat corect> = "{" + <şir parantezat

corect> + "}"

<şir parantezat corect> = <şir parantezat corect>

+ <şir parantezat corect>

Cerinţă

Ca la orice curs, se dau teme de casă, iar Ţirbi a primit următoarea problemă: Având un şir cu N

paranteze, să se afle lungimea maximă a unei secvenţe parantezată corect.

Date de intrare

Fişierul de intrare paranteze.in conţine pe prima linie numărul natural N, iar pe următoarea linie

un şir cu N paranteze.

Date de ieşire

Fişierul de ieşire paranteze.out conţine lungimea maximă a unei secvenţe corect parantezată.

Restricţii

1 ≤ N ≤ 1 000 000

Pentru 50% din teste N ≤ 1 000

Exemplu

paranteze.in paranteze.out

13

{)([({})]([{}

6

Explicaţie

Secvenţa parantezată corect este îngroşată. {)( [({})] ([{}

7

Fişierul intrare/ieşire:

paranteze2.in, paranteze2.out

Sursă Infoarena Monthly 2012,

Runda 1

Autor Andrei Cristian Lambru Adăugată de Mr. Noname •cezar305

Timp execuţie pe test

0.05 sec Limită de memorie

16384 kbytes

Scorul tău în arhivă N/A Dificultate N/A

Paranteze2

Se da un sir de caractere S, de lungime N, ce poate contine caracterele '(' si ')' . Sa se calculeze

si sa se afiseze cate subsecvente ale lui S reprezinta parantezari corecte.

Se numeste o parantezare corecta un sir T de paranteze daca se poate forma astfel:

T = '()'

sau

T = '(' + t + ')' , unde t este o parantezare corecta

sau

T = t1+ t2 +...+tn , unde t1, t2, ..., tn sunt parantezari corecte.

Date de intrare

Fişierul de intrare paranteze2.in va contine pe prima si unica sa linie sirul S.

Date de ieşire

În fişierul de ieşire paranteze2.out se va scrie numarul subsecventelor ce constituie parantezari

corecte.

Restricţii

1 ≤ N ≤ 1.000.000

se intelege subsecventa a sirului S un interval compact de forma [i..j] cu 1 ≤ i ≤ j ≤ N

Exemplu

paranteze2.in paranteze2.out

()(()) 4

Explicaţie

Cele 4 subsecvente sunt 1-2, 3-6, 4-5 si 1-6