Arbori asociati expresiilor aritmetice

Arbori asociati expresiilor aritmetice

Rolul oricarui compilator este de a transforma programele scrise intr-un limbaj de programare oarecare intr-un cod echivalent, scris in limbaj de asamblare sau in limbaj masina. In acest capitol ne punem problema translatarii expresiilor aritmetice dintr-un limbaj de programare cum ar fi de exemplu limbajul Pascal in limbaj de asamblare. Pentru aceasta ne vom propune un model simplu de masina, care lucreaza cu registri notati R1, R2, si executa urmatoarele doua operatii:

PUNE Rx variabila/constanta: incarca variabila sau constanta in registrul Rx;

OPz Rx Ry: efectueaza operatia OPz asupra continuturilor registrilor de memorie Rx respectiv Ry, rezultatul fiind depus in registrul Rx.

De exemplu, pentru expresia aritmetica (a+b)*(c+2) se poate asocia codul:

PUNE R1 a

PUNE R2 b

OP+ R1 R2

PUNE R2 c

PUNE R3 2

OP+ R2 R3

OP* R1 R2

Primul pas in rezolvarea acestei probleme este de asocia expresiei aritmetice un arbore binar.

Definitie

Numim expresie aritmetica o constructie definita prin urmatoarele diagrame de sintaxa:

Fig. 1.

Observatie

Am ales pentru simplitate expresii aritmetice pentru care operanzii sunt formati dintr-un singur caracter, iar operatorii pot fi doar + si *. Aceste restrictii nu sunt semnificative.

Oricarei expresii aritmetice i se poate asocia un arbore binar strict, construit dupa urmatoarele reguli:

-daca expresia este formata dintr-un singur operand, arborele binar asociat este constituit dintr-un singur nod, radacina, care contine drept informatie operandul respectiv;

-daca expresia este de forma E = E₁ op E₂, unde op este un operator, iar E₁ si E₂ sunt expresii aritmetice, arborele binar corespunzator contine in radacina operatorul, subarborele stang fiind arborele binar asociat expresiei E , iar subarborele drept arborele binar asociat expresiei E

De exemplu, arborele binar asociat expresiei E = (a+b)*(a*c+b*d) este:

Fig.

Observatii

1. Intr-un arbore binar asociat unei expresii aritmetice nodurile terminale contin operanzi, iar nodurile interioare contin operatori.

Operatorii utilizati in cadrul expresiei fiind binari, arborele binar asociat expresiei aritmetice este strict.

Parcurgand in preordine arborele binar asociat expresiei aritmetice, obtinem notatia poloneza a expresiei (forma prefixata).

De exemplu, pentru expresia aritmetica E=(a+b)*(a*c+b*d), notatia poloneza este *+ab+*ac*bd.

Aceasta notatie a fost introdusa de matematicianul polonez J. Lucasiewicz si permite scrierea fara paranteze a unei expresii aritmetice.

Pentru a genera codul asociat unei expresii aritmetice vom presupune pentru inceput ca operatorii + si * nu sunt comutativi si nici asociativi. Vom descrie o procedura de generare a codului corespunzator unei expresii aritmetice reprezentate ca un arbore binar, utilizand un numar minim de registri de memorie.

Lema

Fie A arborele binar asociat unei expresii aritmetice si x un nod din A. Numarul minim de registri necesari pentru a evalua expresia corespunzatoare subarborelui cu radacina x este:

Observatii

1. Demonstratia se poate face prin inductie dupa inaltimea subarborelui cu radacina in x si o propunem ca exercitiu.

Pentru orice nod x din arbore, se poate calcula MR(x) parcurgand arborele in postordine.

procedure GenCod (rad: Arbore);

//genereaza codul asociat expresiei aritmetice reprezentate prin //arborele cu radacina rad, fara a tine cont de proprietatile de //comutativitate si asociativitate ale operatorilor

//UR este o variabila globala care indica numarul ultimului registru //ocupat

begin

if rad^.st = nil then //expresie formata dintr-un singur operand

begin

inc(UR);

writeln('PUNE R', UR, ' ', rad^.inf);

end

else

if MR(rad^.dr) > MR(rad^.st) then

begin

//genereaza mai intai codul asociat subarborelui drept

GenCod(rad^.dr);

GenCod(rad^.st);

writeln('OP', rad^.inf, ' R', UR-1, ' R', UR);

dec(UR);

end

else

begin

//genereaza mai intai codul asociat subarborelui stang

GenCod(rad^.st);

GenCod(rad^.dr);

writeln('OP', rad^.inf, ' R', UR-1, ' R', UR);

dec(UR);

end

end;

Daca sunt luate in considerare si proprietatile de comutativitate si asociativitate ale operatorilor, atunci aceeasi expresie poate fi reprezentata echivalent prin arbori binari diferiti. De exemplu,

Fig. 3.

In acest caz, numarul de registri de memorie utilizati, cat si timpul de evaluare a expresiei, difera in functie de forma arborelui asociat expresiei.

Exercitii:

Construiti un arbore binar pentru fiecare din expresiile urmatoare si determinati notatia poloneza.

a) a*b*c+2*d*(a+1+2*b*c)

b)     2*a*c*(a*b+c+3*d+a*b*c*d)

Evaluati complexitatea procedurii de generare a codului corespunzator unei expresii aritmetice.

Scrieti un program care sa citeasca un sir de caractere si sa verifice daca reprezinta o expresie aritmetica valida (in sensul definitiei de mai sus). In caz afirmativ, sa se aduca expresia in forma canonica, aplicand ori de cate ori este nevoie distributivitatea inmultirii fata de adunare (a*(b+c)=a*b+a*c; (b+c)*a=b*a+b*c) si, eventual, idempotenta (a+a=a; a*a=a).

Data o expresie aritmetica in notatie poloneza, scrieti un program care sa evalueze expresia, pentru valori date ale operanzilor.

Date doua expresii aritmetice sintactic valide, scrieti un program care sa verifice daca cele doua expresii sunt echivalente.

Indicatie: Se vor aduce cele doua expresii in forma canonica, tinand cont de proprietatile de comutativitate si asociativitate ale operatorilor si aplicand ori de cate ori este necesar regulile de distributivitate si idempotenta.

(Propusa de conf. dr. Florian Boian la Olimpiada Internationala de Informatica Cluj, 1994)

Data fiind o expresie aritmetica, notam p timpul necesar pentru efectuarea unei adunari si q timpul necesar pentru efectuarea unei inmultiri, timpul necesar pentru evaluarea expresiei E op E fiind egal cu timpul necesar pentru efectuarea operatiei op plus maximul dintre timpii necesari evaluarii subexpresiilor E si E Timpul de evaluare a unui operand este considerat nul. Scrieti un program care citeste date dintr-un fisier ce contine valorile lui p si q si expresii, fiecare expresie pe o linie separata. Pentru fiecare expresie se cere:

-Sa se determine timpul necesar evaluarii ei;

-Sa se determine o expresie echivalenta cu timp de evaluare minim si valoarea acestui timp. Transformarile permise sunt:

a*b=b*a; a+b=b+a

(a*b)*c=a*(b*c); (a+b)+c=a+(b+c).

Indicatie Transformati arborele binar asociat expresiei aritmetice intr-un arbore binar echilibrat dupa inaltime, aplicand rotatii simple sau duble, echivalente cu aplicarea proprietatilor de comutativitate si asociativitate.

Anexa

program Expresie_Aritmetica;

const LgMax = 30;

type Indice = 1..LgMax;

Arbore = ^NodArbore;

NodArbore = record

inf: char;

st, dr: Arbore;

end;

var e: string[LgMax];

rad: Arbore; UR: byte;

i, lg: Indice; fout: text;

procedure Citire;

begin

write('Introduceti expresia '); readln(e);

lg := length(e);

end;

procedure preordine(r: Arbore);

begin

if r <> nil then

begin

write(fout, r^.inf);

preordine(r^.st);

preordine(r^.dr);

end;

end;

function CreareArbore(var i: Indice): Arbore; forward;

function Factor(var i: Indice): Arbore;

var p: Arbore;

begin

if e[i] = '(' then

begin

inc(i);

Factor := CreareArbore(i);

inc(i);

end

else

begin

new(p); p^.inf := e[i]; p^.st := nil;

p^.dr := nil; inc(i);

Factor := p;

end;

end;

function Termen(var i: Indice): Arbore;

var p, r1: Arbore;

begin

r1 := Factor(i);

if (i > lg) or (e[i] <> '*') then

Termen := r1

else

begin

new(p); p^.inf := e[i]; inc(i);

p^.st := r1; p^.dr := Termen(i);

Termen := p;

end

end;

function CreareArbore(var i: Indice): Arbore;

var p, r1: Arbore;

begin

if i > lg then

CreareArbore := nil

else

begin

r1 := Termen(i);

if (i > lg) or (e[i] = ')') then

CreareArbore := r1

else

begin

new(p);

p^.inf := e[i];

p^.st := r1; inc(i);

p^.dr := CreareArbore(i);

CreareArbore := p;

end;

end;

end;

function MR(rad: Arbore): byte;

var m1, m2: byte;

begin

if rad^.st = nil then

MR := 1

else

begin

m1 := MR(rad^.st); m2 := MR(rad^.dr);

if m1 = m2 then MR := m1+1

else if m1 > m2 then MR := m1

else MR := m2;

end

end;

procedure GenCod(rad: Arbore);

begin

if rad^.st = nil then

begin

inc(UR);

writeln(fout, 'PUNE R', UR, ' ', rad^.inf);

end

else

if MR(rad^.dr) > MR(rad^.st) then

begin

GenCod(rad^.dr); GenCod(rad^.st);

writeln(fout,'OP',rad^.inf,' R',UR-1,' R',UR);

dec(UR);

end

else

begin

GenCod(rad^.st); GenCod(rad^.dr);

writeln(fout,'OP',rad^.inf,' R',UR-1,' R',UR);

dec(UR);

end

end;

begin

Citire; i := 1;

assign(fout,'expr.out'); rewrite(fout);

rad := CreareArbore(i);

preordine(rad); writeln(fout);

UR := 0;

GenCod(rad);

writeln(fout, 'Pentru evaluarea expresiei au fost necesari ', MR(rad),' registri');

close(fout);

end.

De exemplu, pentru expresia aritmetica E=(a+b)*(1+c)+2*a*b, continutul fisierului de iesire va fi:

+*+ab+1c*2*ab

PUNE R1 a

PUNE R2 b

OP+ R1 R2

PUNE R2 1

PUNE R3 c

OP+ R2 R3

OP* R1 R2

PUNE R2 a

PUNE R3 b

OP* R2 R3

PUNE R3 2

OP* R2 R3

OP+ R1 R2

Pentru evaluarea expresiei au fost necesari 3 registri.