Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Arbori asociati expresiilor aritmetice

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
PROIECT ASDN - Dispozitiv de comanda pentru doua lifturi alaturate
Scheme logice si pseudocod - Reprezentarea algoritmilor prin scheme logice
Evaluarea corectitudinii algoritmilor
Clusterizare - Algoritmul K-means
SYSAMO-SISTEM EXPERT PENTRU AMORTIZAREA IMOBILIZARILOR CORPORALE
Inteligenta artificiala - Definitii ale inteligentei artificiale
AUTOMATE FINITE IMPLEMENTATE IN VERILOG
Introducere in ModelSIM
Arbori de decizie - Inteligenta artificiala
OPTIMIZAREA DECIZIILOR PRIN METODE MATEMATICE

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 = E1 op E2, unde op este un operator, iar E1 si E2 sunt expresii aritmetice, arborele binar corespunzator contine in radacina operatorul, subarborele stang fiind arborele binar asociat expresiei E1, 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:

1.     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)

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

3.     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).

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

5.     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.

6.     (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 E1 op E2 fiind egal cu timpul necesar pentru efectuarea operatiei op plus maximul dintre timpii necesari evaluarii subexpresiilor E1 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.





* Programul Expresie-Aritmetica de la sfarsitul capitolului construieste arborele binar asociat unei expresii corecte din punct de vedere sintactic, afiseaza forma poloneza a expresiei si genereaza codul optimal pentru expresia data.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1383
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site