Breviar Laborator 5: Stive

Stive

Alexandra Maria VieruFacultatea de Automatica s, i Calculatoare

24 martie 2014

1 Not, iuni generale

Stiva este un tip de date abstract care ment, ine o ordine a elementelor s, i funct, ioneazadupa principiul LIFO (Last In First Out). Accesul la elementele de pe stiva sepoate face doar prin intermediul operat, iilor init, push, pop, top s, i isEmpty,ceea ce ınseamna ca stiva este un tip de date restictionat.

Figura 1: Stiva

Stiva ofera urmatoarele operat, ii:

init() - init, ializeaza stiva

push(e) - introduce elementul e pe stiva

pop() - returneaza valoarea varfului stivei s, i o scoate de pe stiva

top() - returneaza valoarea varfului stivei

isEmpty() - verifica daca stiva este goala

1

2 Implementari

O stiva poate fi implementata folosind vectori sau liste ınlantuite.

2.1 Vectori

Stiva implementata cu ajutorul vectorilor ar trebui sa fie redimensionata ın moddinamic, atunci cand nu mai este spatiu vectorul trebuie sa fie realocat.

Algoritmul 1 init()

cap← 5dim← 0array ← aloca(cap)

Algoritmul 2 push(e)

if dim = cap thencap← 2 ∗ caparray ← realoca(cap)

end ifarray[dim]← edim← dim + 1

Algoritmul 3 pop()

if dim = 0 theneroare : stivaegoala

end ifdim← dim− 1return array[dim]

Figura 2: Push 20

2

Algoritmul 4 top()

if dim = 0 theneroare : stivaegoala

end ifreturn array[dim− 1]

Algoritmul 5 isEmpty()

if dim = 0 thenreturn true

elsereturn false

end if

2.2 Liste ınlantuite

Este recomandat sa se foloseasca o lista ınlantuita cu santinela, astfel adaugareasi stergerea de la ınceputul listei se vor face mai usor (nu va mai trebui trimisareferinta la lista ın C++ sau ** ın C).

Algoritmul 6 init()

init(lst)

Algoritmul 7 push(e)

addFirst(lst)

Algoritmul 8 pop()

e = getF irst(lst)delF irst(lst)return e

Algoritmul 9 top()

e = getF irst(lst)return e

Algoritmul 10 isEmpty()

return isEmpty(lst)

3

3 Aplicat, ii ale stivelor

• Parcurgerea ın adancime (dfs)

• Verificarea corectitudinii imbricarii parantezelor

• Evaluarea expresiilor postfixate

• Implementarea iterativa folosind o stiva a oricarei functii recursive.

4 Algoritmi

O expresie ın forma postfixata este o expresie ın care operatorii se gasesc dupaoperanzii asupra carora trebuie aplicat, i s, i care nu cont, ine paranteze.

4.1 Conversia unei expresii din forma infixata ın formapostfixata

4.2 Evaluarea unei expresii postfixate

Algoritmul 12 evalPostfix(s postfix)

while nu s-a ajuns la sfarsitul lui s postfix doch← urmatorul caracter din s postfixif ch e operand then

pune ch pe stivaend ifif ch e operator then

extrage 2 operanzi de pe stiva o1 si o2if nu exista 2 operanzi pe stiva then

eroare: expresia s postfix e incorectaend ifcalculeaza rezultatul aplicarii operatorului asupra lui o1 si o2pune rezultatul pe stiva

end ifend whileif stiva contine o singura valoare thenreturn valoarea varfului

elseeroare: expresia s postfix e incorecta

end if

4

Algoritmul 11 infix2postfix(s infix)

while nu s-a ajuns la sfarsitul lui s infix doch← urmatorul caracter din sinfixif ch e operand then

adauga ch la sirul s postfixend ifif ch = ( then

pune ch pe stivaend ifif ch =) thenrepeatc← scoate din stivaif c 6= ( then

adauga c la s postfixend if

until c 6= (if c 6= (and stiva e goala then

eroare: sirul s infix e incorectend if

end ifif ch e operator thenwhile stiva nu e goala and varful stivei e operator and prioritate(ch) ≤prioritate(operator din varful stivei) do

scoate opearatorul din stiva si adauga-l la s postfixend whilepune ch pe stiva

end ifend whilewhile stiva nu e goala doch← scoate un element de pe stivaadauga ch la sirup postfixatif ch = ( then

eroare: sirul s infix e incorectend if

end while

5