+ All Categories
Home > Documents > metoda postfixata

metoda postfixata

Date post: 01-Jul-2015
Category:
Upload: emy3999
View: 701 times
Download: 0 times
Share this document with a friend
31
1 Structuri de Date în Java (VII) Aplicaţie pentru stive şi cozi Evaluarea expresiei aritmetice postfixate Translatarea din formă infixată în postfixată Recursivitate Explicaţii şi teste Fractali. Proprietăţi Setul Mandelbrot O culme muntoasă Setul Sierpinski
Transcript
Page 1: metoda postfixata

1

Structuri de Date în Java (VII)

● Aplicaţie pentru stive şi cozi● Evaluarea expresiei aritmetice postfixate● Translatarea din formă infixată în postfixată● Recursivitate● Explicaţii şi teste● Fractali. Proprietăţi● Setul Mandelbrot● O culme muntoasă● Setul Sierpinski

Page 2: metoda postfixata

2

Aplicaţie pentru stive şi cozi

● Temă de laborator● Translatarea unei expresii aritmetice din forma

infixată cu paranteze în forma poloneză inversă (postfixată)

● Calcularea expresiei obţinute● Se citeşte întreaga expresie de la tastatură, într-

un string● Programul trebuie să evalueze expresia şi să

afişeze forma postfixată asociată● Eventualele erori trebuie semnalizate

Page 3: metoda postfixata

3

Expresie aritmetică postfixată

● notaţia infixată: 2 + 3● notaţia prefixată: + 2 3 (forma poloneză)● inventată de matematicianul polonez Jan Lukasiewicz● expresia (2 + 3) * 7 se scrie în formă poloneză * + 2 3 7

(scăpăm de paranteze)● notaţia poloneză inversă, sau notaţia postfixată pentru

expresia (2 + 3) * 7 este 2 3 + 7 *● notaţia postfixată nu necesită paranteze şi poate fi evaluată

uşor folosind o stivă● principiul: se citeşte expresia postfixată; dacă se întâlneşte un

număr, acesta se pune în stivă; un semn se foloseşte de îndată ce este întâlnit

Page 4: metoda postfixata

4

Evaluarea unei expresii postfixate

while mai există cuvinte în expresie dociteşte cuvântul următorif cuvântul este o valoare then

push (cuvânt)else cuvântul este un operator

pop () două valori de pe stivărezultat = aplicarea operator-ului valorilorpush (rezultat)

rezultatul final = pop ()// rezultatul evaluării expresiei se găseşte pe vârful stivei

Page 5: metoda postfixata

5

Exemplu de evaluare postfixată5 3 2 * + 4 – 5 +

5

5 3 2 * + 4 – 5 +

35

5 3 2 * + 4 – 5 +

2 35

5 3 2 * + 4 – 5 +

65

5 3 2 * + 4 – 5 +

11

5 3 2 * + 4 – 5 +

411

5 3 2 * + 4 – 5 +

7

5 3 2 * + 4 – 5 +

57

5 3 2 * + 4 – 5 +

12

Rezultatulevaluăriiexpresiei

Page 6: metoda postfixata

6

Translatarea unei expresii din forma infixată în forma postfixată (i)

3 * X + (Y – 12) - Z

Tiparit:

3

3 * X + (Y – 12) - Z

*Tiparit:3

3 * X + (Y – 12) - Z

*Tiparit:3 X

3 * X + (Y – 12) - Z

+

Tiparit:3 X *

3 * X + (Y – 12) - Z

(+

Tiparit:3 X *

3 * X + (Y – 12) - Z

(+

Tiparit:3 X * Y

numerele se tipăresc înmulţirea pe stivă operandul se tipăreşte

* are precedenţă maimare decât + şi setipăreşte

( se pune pe stivă operandul se tipăreşte

Page 7: metoda postfixata

7

Translatarea unei expresii din forma infixată în forma postfixată (ii)

3 * X + (Y – 12) - Z

- (+

Tiparit:3 X * Y

3 * X + (Y – 12) - Z

- (+

Tiparit:3 X * Y 12

3 * X + (Y – 12) - Z

+

Tiparit:3 X * Y 12 -

3 * X + (Y – 12) - Z

-

Tiparit:3 X * Y 12 - +

3 * X + (Y – 12) - Z

-

Tiparit:3 X * Y 12 - + Z

3 * X + (Y – 12) - Z

Tiparit:3 X * Y 12 - + Z -

- este pus pe stivă (era doar paranteza)

numerele se tipăresc se scoate tot până la paranteza (

tipăreşte, + are aceeaşi precedenţă cu -

operandul se tipăreşte goleşte stiva

Page 8: metoda postfixata

8

Algoritmul de translatare● iniţializează stiva● repetă paşii următori

● dacă urmează o paranteză deschisă “(“, atunci o pune în stivă● dacă însă urmează un număr sau operand, atunci îl tipăreşte● dacă însă e un operator, atunci:

● dacă în vârful stivei este un alt operator cu precedenţa mai mare sau egală cu a acestuia, atunci se scoate acel operator din stivă şi se tipăreşte

● se pune pe stivă operatorul● altfel, ceea ce urmează este o paranteză închisă “)”

● se scot simboluri din stivă şi se afişează până se întâlneşte paranteza deschisă corespondentă, care se scoate şi ea din stivă

● până când expresia se termină● se scot şi se afişează operatorii care au mai rămas în stivă (nu ar trebui să

mai avem paranteze deschise)

Page 9: metoda postfixata

9

Recursivitate

“În matematică sau computer science, recursivitatea specifică (sau construieşte) o clasă de obiecte sau metode prin definirea câtorva cazuri de bază (deseori doar unul) şi prin descrierea regulilor ce descompun cazurile complexe într-unele mai simple.”

(Wikipedia)

Page 10: metoda postfixata

10

Metode recursive

● recursivitatea înseamnă rezolvarea unei probleme cu ajutorul rezultatului obţinut prin rezolvarea unei aceleiaşi probleme dar de mărime mai redusă

● practic o metodă se poate autoapela dar cu un argument de mărime mai mică

● se poate formula o abordare recursivă pentru o problemă● la formularea unei metode recursive, trebuie acordată

atenţie la evoluţia argumentului metodei, pentru a nu ajunge la valori invalide

Page 11: metoda postfixata

11

:-P

RecursionIf you still don't get it, See: "Recursion".

Recursive acronyms● GNU: GNU's Not Unix● PHP: PHP Hypertext Preprocessor● GNU HURD: HIRD of Unix-Replacing Daemons● HIRD: HURD of Interfaces Representing Death

(hurd/hird/herd of gnus – i.e. the antelope)

Page 12: metoda postfixata

12

Metoda writeVertical● problema: să se scrie cifrele unui număr pe verticală,

folosind o metodă recursivă

public class RecWrite{ public static void writeVertical (int number) { if( number < 10 ) System.out.println (number); else { writeVertical (number / 10); System.out.println (number % 10); } } public static void main (String[] args) { writeVertical (1234); }}

problema opririi

apelul recursiv

Page 13: metoda postfixata

13

Desfăşurarea apelurilor (I)apel writeVertical( 1234 )

1234 < 10 ? NUapelăm writeVertical(123)scriem cifra '4'

apel writeVertical( 123 )

123 < 10 ? NUapelăm writeVertical( 12 )scriem cifra '3'

apel writeVertical( 12 )

12 < 10 ? NUapelăm writeVertical(1)scriem cifra '2'

apel writeVertical( 1 )

1 < 10 ? DAscriem cifra '1'

Page 14: metoda postfixata

14

Desfăşurarea apelurilor (II)

apel writeVertical( 1234 )

1234 < 10 ? NUapelăm writeVertical(123)scriem cifra '4'

apel writeVertical( 123 )

123 < 10 ? NUapelăm writeVertical( 12 )scriem cifra '3'

apel writeVertical( 12 )

12 < 10 ? NUapelăm writeVertical(1)scriem cifra '2'

apel writeVertical( 1 )

1 < 10 ? DAscriem cifra '1'

Page 15: metoda postfixata

15

Desfăşurarea apelurilor (III)

● Colecţia de parametri ai metodei curente precum şi variabilele sale locale sunt salvate pe stivă înainte de efectuarea apelului recursiv

● La întoarcerea din apel, se refac aceste valori tot folosind stiva

● Instrucţiunea de după apel se execută după ce s-a revenit din apel, valorile parametrilor rămîn aceleaşi cu cele de dinainte de apel

Page 16: metoda postfixata

16

Teste - A

// ce se afişează pentru apelul f(3) ?

public static void f(int n) {System.out.println (n);if (n > 1)

f (n-1);}

Page 17: metoda postfixata

17

Teste - B

// ce se afişează pentru apelul f(3) ?

public static void f(int n) {if (n > 1)

f (n-1);System.out.println (n);

}

Page 18: metoda postfixata

18

Teste - C

// ce se afişează pentru apelul f(3) ?

public static void f(int n) {System.out.println (n);if (n > 1)

f (n-1);System.out.println (n);

}

Page 19: metoda postfixata

19

Fractali

● Noţiunea de “fractal” inventată de Benoît Mandelbrot (1975) descrie obiecte a căror porţiune mărită (cu o lupă) prezintă similaritate cu întregul obiect

● Denumire derivată din latinescul fractus● Un fractal matematic este bazat pe o ecuaţie

iterativă, bazată pe recursie● Structuri geometrice folosite de programatori

pentru a realiza scene naturale reprezentînd arbori, munţi, nori etc.

Page 20: metoda postfixata

20

Setul Mandelbrot

detaliu:

Page 21: metoda postfixata

21

Proprietăţi

● Are o structură fină oricât de mult ar fi “mărit”

● Este mult prea neregulat pentru a fi descris cu ajutorul geometriei euclidiene

● Întregul are aceeaşi formă ca una sau mai multe părţi ale sale (self-similarity)

● Are o definiţie simplă şi recusivă

Page 22: metoda postfixata

22

Generarea fractalilor● Punctul situat la jumătatea segmentului este deplasat în sus sau în jos cu

o distanţă aleatoare● Se aplică regula din nou pe subsegmentele create● Se opreşte când mărimea unui subsegment devine relativ mică

a) segmentul iniţial b) mijlocul segmentului estemutat mai sus sau mai jos

c) două mijloacesunt mutate d) se mută patru mijloace

Page 23: metoda postfixata

23

O coamă muntoasă

Procedeul se aplicărecursiv până cânddistanţa dintre douăpuncte devine < 50

(rezoluţie 512 x 512)

Page 24: metoda postfixata

24

randomFractal (0, height/2, width, height/2)

public void randomFractal ( int leftX, int leftY, int rightX, int rightY) { final int STOP = 50; int midX, midY, deltam, deltap, delta; if ((rightX - leftX) <= STOP) drawArea.drawLine (leftX, leftY, rightX, rightY); else { midX = (leftX + rightX) / 2; midY = (leftY + rightY) / 2; deltam = - (int)(Math.random() * midY / 2); deltap = (int)(Math.random () * (width - midY) / 2); delta = -deltam < deltap ? deltam : deltap; midY += delta; randomFractal (leftX, leftY, midX, midY); randomFractal (midX, midY, rightX, rightY); } }

Page 25: metoda postfixata

25

Un fractal cu pătrate

● Care este regularecursivăde formare?

● Care este condiţiade oprire ?

Page 26: metoda postfixata

26

cubFractal (0, 0, width, height); public void cubFractal ( int leftX, int leftY, int rightX, int rightY) { final int STOP = 4; int midX, midY; if (rightX - leftX <= STOP) drawArea.drawRect (leftX, leftY,

rightX - leftX, rightY - leftY); else { midX = (leftX + rightX) / 2; midY = (leftY + rightY) / 2; drawArea.drawRect (leftX, leftY,

midX - leftX, midY - leftY); drawArea.drawRect (midX, midY,

rightX - midX, rightY - midY); cubFractal (midX, midY, rightX, rightY); cubFractal (midX, leftY, rightX, midY); cubFractal (leftX, midY, midX, rightY); } }

Page 27: metoda postfixata

27

Triunghiul Sierpinski

Fractal descrisîn 1915 de cătrematematicianulpolonezWaclaw Sierpinski

Page 28: metoda postfixata

28

Abstractizarea unui punct static class Pair { public int x; public int y; public Pair (int x, int y) { this.x = x; this.y = y; } public static Pair mid (Pair a, Pair b) { return new Pair ((a.x + b.x) / 2,

(a.y + b.y) / 2); } public static int len (Pair a, Pair b) { double x = a.x - b.x; double y = a.y - b.y; x *= x; y *= y; return (int)Math.sqrt (x + y); } }

Page 29: metoda postfixata

29

Triunghiul iniţial

public void sierpinski () { Pair a = new Pair (width / 2, 0); Pair b = new Pair (0, height); Pair c = new Pair (width, height); sierpinski (a, b, c); }

Page 30: metoda postfixata

30

Procedura de generare public void sierpinski (Pair a, Pair b, Pair c) { if (Pair.len (a, b) < 10) { drawArea.drawLine (a.x, a.y, b.x, b.y); drawArea.drawLine (b.x, b.y, c.x, c.y); drawArea.drawLine (a.x, a.y, c.x, c.y); return; } Pair ab = Pair.mid (a, b); Pair bc = Pair.mid (b, c); Pair ac = Pair.mid (a, c); sierpinski (a, ab, ac); sierpinski (ab, b, bc); sierpinski (ac, bc, c); }

Page 31: metoda postfixata

31

Mult mai mult

http://en.wikipedia.org/wiki/Fractal


Recommended