L9a

7/18/2019 L9a

http://slidepdf.com/reader/full/l9a 1/4

Structuri de Date

L A B O R A T O R 9a

Arbori binari pentru expresii aritmetice

Orice expresie aritmetica se poate reprezenta printr-un arbore binar

in care nodurile interne contin operatori iar nodurile terminale (frunze)

contin operanzi !xemplu de expresie cu operanzi intre"i#

($% & (($'&')(*-')))

Arborele corespunzator#

&

+

$%

+

& -

+ +

$' ' * '

,iecare nod de arbore a contine ca date un numar intre"

O expresie complet parantezata (.full/ parent0esized.) contine

paranteze in 1urul fiecarei subexpresii cu doi operanzi !xemple#

(22&) 3 ((($*&2*)&*)&4*) 3 ((5**2)&(26**)) 3 (($*6*)&(%*(5*-4*)))

$ Sa se defineasca tipul .tnod. pentru un nod de arbore binar si o functie

pentru crearea unui nod de arbore binar cu date primite ca ar"umente#

tnod6 ma7e (int x3 tnod6 left3 tnod6 ri"0t)8

,unctia urmatoare construieste un arbore pentru expresia (22&($$))

tnod6 build ()

tnod 6 r3 6f$3 6f28

f$:ma7e(3*3*)8

f2:ma7e($$3*3*)8

r:ma7e(;;3f$3f2)8

f$:ma7e(223*3*)8

r:ma7e(;&;3f$3r)8

return r8

<

Sa se scrie o functie pentru afisarea unui arbore binar ca o expresie

cu paranteze in 1urul fiecarei (sub)expresii (ca arianta de afisareinfixata a unui arbore binar) !xemplu de afisare# (22&($$))

!xemplu de utilizare#

int main ()

tnod6 r:build()8

infix(r)8

s/stem(.pause.)8

<

7/18/2019 L9a


2 Sa se scrie o fuctie pentru afisarea prefixata3 cu indentare3 a unui

arbore

binar si sa se adau"e apelul acestei functii la pro"ramul anterior !xemplu de

afisare#

&

22

$$

Sa se scrie o functie recursia pentru ealuarea rezultatului unei

expresii lo"ice reprezentate printr-un arbore binar cu operanzi intre"i

de o sin"ura cifra in nodurile arborelui #

int ealtree (tnod6 r)8

!aluarea este un caz particular de izitare postfixata# se ealueaza

mai intai subarborii si apoi se aplica operatorul din radacina asupra

alorilor rezultate din ealuarea subarborilor Se a defini si folosi o functie pentru calculul unei expresii cu doi

operanziintre"i#

int calc (int op3 int x3 int /)8 op:operator binar

Se a adau"a functia pro"ramului anterior si se a afisa rezultatul

ealuarii expresiei din arborele creat !xemple de expresii ptr erificare#

($%&(($'&')(*-'))) 3 (($*6*)&(%*(5*-4*)))

4 ,unctia urmatoare calculeaza rezultatul unei expresii complet

parantezate

cu operanzi si rezultate intermediare numere intre"i #

int eal (c0ar6 = p) p : adresa sir cu expresie

int a3b3x8 c0ar op8

if (isdi"it(6p)) daca este o cifra

x: (int) strtod(p3=p)8 conersie in binar

return x8

<

if (6p::;(;) daca inceput subexpresie

a: eal (&&p)8 calcul operand $

op: 6p&&8 retine operator

b:eal (p)8 calcul operand 2

p&&8 peste ;); de la sfarsitul expresiei

return calc(op3a3b)8 rezultat subexpresie

<

<

Sa se scrie o functie care construieste un arbore binar dintr-o expresie

infixata cu paranteze la fiecare subexpresie3 modificand functia anterioara

tnod6 build (c0ar6 = p)8 p : adresa sir cu expresie

>entru erificare se a afisa arborele cu functiile .infix. si .prefix.

7/18/2019 L9a


' !aluarea unei expresii complet parantezate se poate face si cu

functiile

mutual recursie urmatoare#

termen (operand)

int term (c0ar6 = p)

int infx (c0ar6=)8

if (isdi"it(6p))

return (int) strtod(p3=p)8

else

return infx (p)8

<

ealuare expresie

int infx (c0ar6 = p)

int term (c0ar6 =)8

int a3b8 c0ar op8

if (6p::;(;)

a: term(&&p)8

op: 6p&&8 operator

b: term (p)8 p&&8 ;);

return calc(op3a3b)8

<

<

Sa se modifice cele doua functii pentru crearea unui arbore binar dintr-o

expresie complet parantezata#

tnod6 term (c0ar6 = p)8

tnod6 build (c0ar6 = p)8

Sa se erifice prin afisarea arborelui creat in ordine prefixata3 cu

indentare

5 ,unctiile urmatoare realizeaza ealuarea unei expresii aritmetice in

forma

uzuala (cu paranteze numai unde sunt necesare) si cu operanzi de o cifra#

expresie

int expr ( c0ar 6 =exp )

int term(c0ar6=)8

c0ar c08 int r$3r28

r$:term(exp)8 primul termen

?0ile ((c0:6exp) == (c0::;&; @@ c0::;-;) )

r2: term(&&exp)8 al doilea termen

if (c0::;&;) r$ &: r28

if (c0::;-;) r$ -: r28

< return r$8

<

termen

int term (c0ar 6= exp)

int fact(c0ar6=)8

c0ar c08 int r$3r28

r$:fact(exp)8 aloarea primului factor

?0ile ( (c0:6exp) == (c0::;6; @@ c0::;;) )

r2: fact (&&exp)8

7/18/2019 L9a


if (c0::;6;) r$ 6: r28

if (c0::;;) r$ : r28

<

return r$8

<

factor

int fact (c0ar6 = exp)

c0ar c08 int r8 c0ar 6 p8

c0:6exp8

if (c0::*) return *8

if (isdi"it(c0)) daca cifra

exp&&8 peste cifra c0

return c0-;*;8 rezultat:operand

<

else if ( c0::;(;)

r: expr ( &&exp)8 rezultat ealuare expresie

exp&&8

<

return r8

<

Sa se erifice pe expresiile urmatoare#

'&%2-26 (2&$)6(4-$)&'

Sa se construiasca un arbore binar ec0ialent expresiei prin modificarea

functiilor expr3 term si fact si sa se afiseze pentru erificare

L9a

Documents

Transcript of L9a