metoda postfixata

transcript

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

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

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

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

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

5 3 2 * + 4 – 5 +

Rezultatulevaluăriiexpresiei

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

3 * X + (Y – 12) - Z

Tiparit:

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

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

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)

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)

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

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)

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

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'

1 < 10 ? DAscriem cifra '1'

Desfăşurarea apelurilor (II)

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

1 < 10 ? DAscriem cifra '1'

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

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);}

Teste - B

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

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

Teste - C

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

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

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.

Setul Mandelbrot

detaliu:

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ă

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

O coamă muntoasă

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

(rezoluţie 512 x 512)

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); } }

Un fractal cu pătrate

● Care este regularecursivăde formare?

● Care este condiţiade oprire ?

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); } }

Triunghiul Sierpinski

Fractal descrisîn 1915 de cătrematematicianulpolonezWaclaw Sierpinski

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); } }

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); }

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); }

Mult mai mult

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

metoda postfixata

Documents