|
|
|
|
|
|
|
Tutti i tipi di dati che hai visto finora sono concreti, nel senso che abbiamo completamente specificato quale sia la loro implementazione. La classe Carta rappresenta una carta da gioco usando due numeri interi: come abbiamo detto durante lo sviluppo della classe questa non è l'unica implementazione possibile ma ne esistono infinite altre.
Un tipo di dato astratto (TDA) specifica un insieme di operazioni (o metodi) e la loro semantica (cosa fa ciascuna operazione) ma senza specificare la loro implementazione: questa caratteristica è ciò che lo rende astratto.
Per che cosa è utile questa "astrazione"?
Quando parliamo di TDA spesso distinguiamo il codice che usa il TDA (cliente) dal codice che lo implementa (fornitore).
In questo capitolo esamineremo la pila, un tipo di dato astratto molto comune. Una pila è una collezione e cioè una struttura di dati che contiene elementi multipli. Altre collezioni che abbiamo già visto sono i dizionari e le liste.
Un TDA è definito dalle operazioni che possono essere effettuate su di esso e che sono chiamate interfaccia. L'interfaccia per una pila consiste di queste operazioni:
Una pila è spesso chiamata struttura di dati LIFO ("last in/first out", ultimo inserito, primo fuori) perché l'ultimo elemento inserito in ordine di tempo è il primo ad essere rimosso: un esempio è una serie di piatti da cucina sovrapposti, ai quali aggiungiamo ogni ulteriore piatto appoggiandolo sopra agli altri, ed è proprio dall'alto che ne preleviamo uno quando ci serve.
Le operazioni che Python fornisce per le liste sono simili a quelle definite per la nostra pila. L'interfaccia non è proprio quella che ci si aspetta ma scriveremo del codice per tradurla nel formato utile al nostro TDA Pila.
Questo codice è chiamato implementazione del TDA Pila. Più in generale un'implementazione è un insieme di metodi che soddisfano la sintassi e la semantica dell'interfaccia richiesta.
Ecco un'implementazione della Pila con le liste predefinite in Python:
class Pila:
def __init__(self):
self.Elementi = []
def Push(self, Elemento) :
self.Elementi.append(Elemento)
def Pop(self):
return self.Elementi.pop()
def EVuota(self):
return (self.Elementi == [])
L'oggetto Pila contiene un attributo chiamato Elementi che è la lista di oggetti contenuta nella pila. Il metodo __init__ inizializza Elementi come lista vuota.
Push inserisce un nuovo elemento nella pila aggiungendolo a Elementi. Pop esegue l'operazione inversa, rimuovendo e ritornando l'ultimo elemento inserito nella pila.
Per controllare se la pila è vuota EVuota confronta Elementi con una lista vuota e ritorna vero/falso.
Un'implementazione di questo tipo in cui i metodi sono solo una semplice invocazione di metodi già esistenti viene detta maschera. Nella vita reale la maschera (o impiallacciatura) è tra le altre cose quello strato di legno di buona qualità che copre un legno di bassa qualità sottostante. In informatica è un pezzo di codice che nasconde i dettagli di un'implementazione per fornire un'interfaccia più semplice e standard.
Una pila è una struttura di dati generica dato che possiamo aggiungere qualsiasi tipo di dato al suo interno. Gli esempi seguenti aggiungono due interi ed una stringa alla pila:
>>> P = Pila()
>>> P.Push(54)
>>> P.Push(45)
>>> P.Push("+")
Possiamo usare EVuota e Pop per rimuovere e stampare tutti gli elementi della pila:
while not P.EVuota() :
print P.Pop(),
Il risultato è + 45 54. In altre parole abbiamo usato la pila per stampare gli elementi in ordine inverso! Anche se questo non è il formato standard per la stampa di una lista usando una pila è stato comunque facile ottenerla.
Confronta questo codice con l'implementazione di StampaInversa nella sezione 17.4. Le due versioni sono molto più simili di ciò che sembra a prima vista, dato che entrambe fanno uso dello stesso meccanismo: mentre nell'implementazione della classe Pila appena scritta l'uso della pila è evidente, nella versione ricorsiva vista in precedenza il carico della gestione della pila era delegato all'interprete stesso. Ad ogni chiamata di funzione infatti viene usata una pila interna all'interprete che tiene conto della successione delle chiamate alle funzioni.
Nella maggior parte dei linguaggi di programmazione le espressioni matematiche sono scritte con l'operatore tra i due operandi, come nella consueta 1+2. Questo formato è chiamato notazione infissa. Un modo alternativo che ha avuto qualche successo in passato in particolari modelli di calcolatrici tascabili ma ora è usato meno frequentemente, è chiamato notazione postfissa: nella notazione postfissa l'operatore segue gli operandi, tanto che l'espressione appena vista sarebbe scritta in questo modo: 1 2 +.
Il motivo per cui la notazione postfissa può rivelarsi utile è che c'è un modo del tutto naturale per valutare espressioni postfisse con l'uso della pila:
Esercizio: applica questo algoritmo all'espressione 1 2 + 3 *.
Questo esempio mostra uno dei vantaggi della notazione postfissa: non sono necessarie parentesi per controllare l'ordine delle operazioni. Per ottenere lo stesso risultato con la notazione infissa avremmo dovuto scrivere (1 + 2) * 3.
Esercizio: scrivi l'espressione postfissa equivalente a 1+2*3.
Per implementare l'algoritmo di valutazione dell'espressione dobbiamo essere in grado di attraversare una stringa e di dividerla in una serie di operandi e operatori. Questo processo è un esempio di parsing e il risultato è una serie di elementi chiamati token. Abbiamo già visto questi termini all'inizio del libro.
Python fornisce un metodo split in due moduli, sia in string (per la gestione delle stringhe) che in re (per le espressioni regolari). La funzione string.split divide una stringa scomponendola in una lista di token e usando un singolo carattere come delimitatore. Per esempio:
>>> import string
>>> string.split("Nel mezzo del cammin"," ")
['Nel', 'mezzo', 'del', 'cammin']
In questo caso il delimitatore è il carattere spazio così che la stringa viene spezzata ad ogni spazio.
La funzione re.split è molto più potente, permettendo l'uso di una espressione regolare invece di un delimitatore singolo. Un'espressione regolare è un modo per specificare un insieme di stringhe e non soltanto un'unica stringa: [A-Z] è l'insieme di tutte le lettere maiuscole dell'alfabeto, mentre [0-9] è l'insieme di tutti i numeri. L'operatore ^ effettua la negazione dell'insieme così che [^0-9] rappresenta l'insieme di tutto ciò che non è un numero. Questi sono soltanto gli esempi più semplici di ciò che possono fare le espressioni regolari e per le nostre necessità ci fermeremo qui: infatti abbiamo già ricavato l'espressione regolare che ci serve per dividere un'espressione postfissa:
>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']
Nota come l'ordine degli operandi sia diverso da quello di string.split in quanto i delimitatori sono indicati prima della stringa da dividere.
La lista risultante include gli operandi 123 e 456, e gli operatori * e /. Include inoltre due stringhe vuote inserite dopo gli operandi.
Per valutare un'espressione postfissa useremo il parser e l'algoritmo che abbiamo visto nelle sezioni precedenti. Per cominciare dalle cose più semplici inizialmente implementeremo solo gli operatori + e *:
def ValutaPostfissa(Espressione):
import re
ListaToken = re.split("([^0-9])", Espressione)
Pila = Pila()
for Token in ListaToken:
if Token == '' or Token == ' ':
continue
if Token == '+':
Somma = Pila.Pop() + Pila.Pop()
Pila.Push(Somma)
elif Token == '*':
Prodotto = Pila.Pop() * Pila.Pop()
Pila.Push(Prodotto)
else:
Pila.Push(int(Token))
return Pila.Pop()
La prima condizione tiene a bada gli spazi e le stringhe vuote. Le due condizioni successive gestiscono gli operatori, partendo dal presupposto che qualsiasi altra cosa sia un operatore valido. Logicamente dovremo controllare la validità dell'espressione da valutare ed eventualmente mostrare un messaggio di errore se ci fossero dei problemi, ma questo lo faremo più avanti.
Testiamola per valutare l'espressione postfissa di (56+47)*2:
>>> print ValutaPostfissa("56 47 + 2 *")
206
Uno degli obiettivi fondamentali di un TDA è quello di separare gli interessi del fornitore, che scrive il codice del TDA, da quelli del cliente, che usa il TDA. Il fornitore deve solo preoccuparsi di verificare che l'implementazione sia corretta, secondo le specifiche del TDA, e non ha idea di come sarà usato il suo codice.
D'altra parte il cliente parte dal presupposto che l'implementazione del TDA sia corretta e non si preoccupa dei dettagli già considerati dal fornitore. Quando stai usando dei tipi predefiniti in Python hai il vantaggio di dover pensare solo da cliente, senza doverti preoccupare di verificare la corretta implementazione del codice.
Logicamente nel momento in cui implementi un TDA (e quindi sei il fornitore) devi scrivere del codice cliente per testarlo, e questo fatto può mettere un po' in confusione dato che si devono giocare entrambi i ruoli.
|
|
|
|
|
|
|