Matteo Baldoni Architetture degli Elaboratori 1
Corso di Corso di
Architettura degli Elaboratori Architettura degli Elaboratori
Reverse Polish Notation:
Jan Lukasiewicz [1878-1956], Donald Knuth [1962]
Matteo Baldoni Dipartimento di Informatica Università degli Studi di Torino C.so Svizzera, 185 – I-10149 Torino [email protected] http://www.di.unito.it/ ~baldoni
Matteo Baldoni Architetture degli Elaboratori 2
Reverse Polish Notation Reverse Polish Notation
Problema: data una espressione (A + B) / (C – D) scrivere un algoritmo per calcolarne il valore
Questo problema è di fondamentale importanta per la realizzazione di un qualsiasi llinguaggio ad alto livello È più facile utilizzando per le espressioni la RPN:
A B + C D - /
La struttura dati pila (stack) gioca un ruolo fondamentale
Matteo Baldoni Architetture degli Elaboratori 3
La pila (stack) La pila (stack)
La pila è una sequenza di elementi di un certo tipo in cui è possibile aggiungere o togliere elementi
soltanto ad un estremo (la
“testa”) della sequenza LIFO: Last In First Out, ultimo arrivato, primo servito
Testa
Matteo Baldoni Architetture degli Elaboratori 4
La pila (stack) La pila (stack)
La pila puo` essere vista come un caso speciale di lista in cui
l’ultimo elemento inserito è anche il primo ad essere rimosso
non è possibile accedere ad alcun elemento che non sia quello in testa
Applicazione importante:
gestione dell’esecuzione di procedure ricorsive
Matteo Baldoni Architetture degli Elaboratori 5
Operazioni sulle pile Operazioni sulle pile
creaPila: crea una nuova pila vuota
pilaVuota: test, restituisce true se la pila è vuota, false altrimenti
leggiPila (top): restituisce l’elemento in testa alla pila fuoriPila (pop): elimina l’elemento in testa alla pila inPila (push): inserisce un elemento in testa alla pila
Matteo Baldoni Architetture degli Elaboratori 6
Operazioni sulle pile Operazioni sulle pile
creaPila(Pila)
creaLista(Pila)
codaVuota(Pila)
return vuoto(Pila)
leggiPila(Pila) p ← primo(Pila) elem ← leggi(p, Pila) return elem
fuoriPila(Pila) p ← primo(Pila) elem ← leggi(p, Pila) cancella(p, Pila) return elem
inPila(elem, Pila) p ← primo(Pila) inserisci(elem, p, Pila)
Matteo Baldoni Architetture degli Elaboratori 7
Espressioni aritmetiche Espressioni aritmetiche
Le parentesi sono fondamentali per una corretta interpretazioni delle regole di priorita` tra gli operatori additivi e moltiplicativi
3 * 3 + 2: quale è il risultato? 11 oppure 15?
Dipende se * ha maggiore priorita` di + oppure no
* ha maggiore priorita` di + uso le parentesi per far si che si sommi prima di moltiplicare
!
Matteo Baldoni Architetture degli Elaboratori 8
Albero sintattico Albero sintattico
Albero sintattico
i nodi interni rappresentano gli operatori
le foglie gli operandi la gerarchia permette di memorizzare le relazioni di priorita` tra I vari operatori
le parentesi sono inutili
" "
" # #
#
Matteo Baldoni Architetture degli Elaboratori 9
Albero: previsita Albero: previsita
$&% '
% (
% )
% *
% +
% ,
% -
% .
% $/% $$
PREVISITA(p, Tree) // Esamina p
if not foglia(p, Tree) then begin v ← primoFiglio(p, Tree)
while not fineFratelli(v, T) do begin PREVISITA(v, Tree)
v ← succFratello(v, Tree) end
end
$
' * $ / $$
, -
+
)
( .
Matteo Baldoni Architetture degli Elaboratori 10
Albero: invisita Albero: invisita
$
' * $/ $$
, -
+
)
( .
INVISITA(p, Tree) if foglia(p, Tree) then //Esamina p else begin
v ← primoFiglio(p, Tree) INVISITA(v, Tree) // Esamina p
v ← succFratello(v, Tree)
while not fineFratelli(v, T) do begin INVISITA(v, Tree)
v ← succFratello(v, Tree) end
end
012 3 4 $
(
% '
% )
% $% +
% *
% .
% -
% $ /% $$&% ,
Matteo Baldoni Architetture degli Elaboratori 11
Albero: postvisita Albero: postvisita
$
' * $ / $$
, -
+
)
( .
(
% )
% '
% +
% *
% .
% $/% $$&% -
% ,
% $
POSTVISITA(p, Tree)
if not foglia(p, Tree) then begin v ← primoFiglio(p, Tree)
while not fineFratelli(v, T) do begin PREVISITA(v, Tree)
v ← succFratello(v, Tree) end
// Esamina p end
Matteo Baldoni Architetture degli Elaboratori 12
Albero sintattico Albero sintattico
5 La notazione postfissa è data dalla visita dell’albero sintattico con una
postvisita
5 La visita postfissa può essere realizzata appogiandosi ad uno stack
5 Ma come utilizzare l’espressione cosi`
ottenuta?
5 Come calcolarne il valore espresso?
67 8 67 9 :; 97 8 6< 9 :;; 8 : = >?
8
9
8 8
9 9:
7 7
7 : < :
7 7 : 9 87 < : 9 8 9 : 8
Matteo Baldoni Architetture degli Elaboratori 13
Macchina a stack Macchina a stack
@ Per il calcolo di un’espressione in notazione polacca postfissa si fa uso di una macchina a pila
@ Si legge l’espressione polacca da sinistra verso destra
@ Per ogni valore numerico si effettua un’operazione di push in una pila di tale valore
@ Per ogni operatore si esegue l’operazione espressa sui due prima valori estratti con la pop e si fa la push del risultato
@ il top finale è il valore dell’espressione
A A B C D A E B C D C B D
Matteo Baldoni Architetture degli Elaboratori 14
Esecuzione Esecuzione
F F G H I F J G H I H G I
A AKA BLAKA MLA E M A
E M EA
E M
B
EA
E M ALA
E M N
E M BO BLBO O P
Matteo Baldoni Architetture degli Elaboratori 15
Uno stack per la conversione Uno stack per la conversione
Q Si inserisce un $ sullo stack
Q I numeri sono copiati in output
Q Le parentesi sinistre sono inserite nello stack
Q Se il simbolo analizzato è una parentesi destra si estraggono e inviano in output tutti i simboli sino ad una parentesi sinistra, parentesi destra e sinistra si eliminano
Q Se il simbolo analizzato ha priorità più alta di quello sul top il simbolo è inserito nello stack
Q Se ha priorità più bassa si estrae il simbolo sul top e lo si invia in output
Q Se il simbolo analizzato è $ si estraggono e inviano in output tutti i simboli sullo stack
A A B C D A E B C D C B D
RA D RA C BS C A D RE C BSS D B T
Matteo Baldoni Architetture degli Elaboratori 16
Esecuzione Esecuzione
UV W UV X YZ X V W U[ X YZZ W Y \
V V Y X WV [ Y X W X Y W
T RT D
RT RD
RT DT
C
RDRT D
RT RT
C
RT DC
RT RDC
RT C
RDC
RT T T
