|
Testo della prova di esame del 28 / 10 / 2005:
Dispense del corso
e informazioni.
http://www.elettronica.ingegneria.unige.it/index.aspx?page=1199&lang=ITA
Srivere un sistema
software che esegue le seguenti elaborazioni
- Chieda all'utente e legga in input da tastiera il nome di un file di testo di
input.
Il file di input contiene zero o più righe di testo di lunghezza qualsiasi, separate
da caratteri "a capo". Ciascuna riga è una stringa di caratteri S composta interamente
da caratteri di tipo parentesi (,),[,],{,}.
Una stringa S di questo tipo si dice bilanciata se soddisfa una delle seguenti forme:
- S = ""
- S = "(T)"
- S = "[T]"
- S = "{T}"
- TU
dove T ed U sono entrambe stringhe bilanciate. In altre parole una stringa è bilanciata
se ogni parentesi aperta è chiusa da una parentesi dello stesso tipo ad esempio
"{()[()]}" è una stringa bilanciata, mentre "([)]" non è una stringa bilanciata.
- Chieda all'utente il nome del file di output.
- Scriva sul file di output le righe del
file di input che rappresentano stringhe bilanciate uniche eliminando le stringhe
non bilanciate, le stringhe duplicate e non considerando le righe nulla e quelle
mal formate (contente caratteri diversi dalle parentesi).
- Errori dovuti a file di input non esistente
o a file di output non scrivibile devono essere gestiti.
Svolgimento
Il sistema è composto da 4 classi:
|
Nome classe
|
Descrizione
|
|
CStack
|
Implementa il funzionamento di uno stack lifo di lunghezza arbitraria per caratteri
(char)
|
|
CItem
|
Eredita da CStack ed aggiunge alcune funzionalità come il controllo del bilanciamento
|
|
CContainer
|
Implementa il funzionamento di un contenitore di oggetti (puntatori) stack su cui
effettuare operazioni
|
|
CFile_interface
|
Consente di interfacciarsi con file di testo per la lettura e la scrittura di dati
|
Il diagramma uml del sistema è il seguente:

Per visualizzare in dettaglio l’immagine ciccare qui Il diagramma è stato realizzato
con Microsoft Visio 2003.
Descrizione dei metodi delle classi (privati a sfondo grigio;
pubblici a sfondo bianco)
Classe CStack
|
Nome metodo
|
Descrizione
|
|
void push(const char&)
|
Inserisce un carattere nello stack
|
|
const char pop()
|
Legge l’ultimo carattere inserito
|
|
void reset()
|
Cancella tutti gli elementi presenti nello stack
|
|
int getelements();
|
Ritorna il numero dei caratteri totali presenti all’interno dello stack
|
Classe CItem: public
CStack
|
Nome metodo
|
Descrizione
|
|
void dump() const
|
Stampa a video l’oggetto in una forma convenientemente leggibile
|
|
bool check()
|
Controlla la validità dell’elemento (bilanciamento, grammatica)
|
|
int getelements() const
|
Ritorna il numero dei caratteri totali presenti all’interno dell’elemento
|
|
void setinvalid()
|
Invalida l’elemento, ovvero memorizza che non è conforme
|
|
bool getvalid()
|
Ritorna la validità dell’elemento
|
|
void setseq(int)
|
Imposta il valore di identificativo all’ oggetto
|
|
int getseq()
|
Ritorna il valore dell’identificativo dell’oggetto
|
|
bool eq(const CItem&, const CItem&) const
|
Confronta due oggetti di tipo CItem
|
|
string tostring()
|
Ritorna una stringa formata dai caratteri contenuti nell’elemento
|
|
void CItem::checkchr(bool *, const char*)
|
Controlla la grammatica dei caratteri presenti
|
|
bool CItem::checkopn(const char *)
|
Controlla se la parentesi è aperta
|
|
bool CItem::checksim(const char *, const char *)
|
Controlla la grammatica dei caratteri presenti
|
Classe CContainer
|
Nome metodo
|
Descrizione
|
|
void add(CItem*)
|
Aggiunge un elemento al contenitore
|
|
CItem pick(int)
|
Legge, senza estrarlo, un elemento dal contenitore
|
|
void dump()
|
Stampa a video il contenuto del contenitore in una forma convenientemente leggibile
|
|
void checkall()
|
Controlla la validità di tutti gli elementi presenti nel contenitore. Valuta il
bilanciamento degli elementi, la correttezza grammaticale e la presenza di duplicati.
|
|
int getelements() const
|
Ritorna il numero degli elementi totali presenti all’interno del contenitore
|
|
void readfromfile(string)
|
Legge i dati dal file di ingresso e popola il contenitore
|
|
void writetofile(string)
|
Scrive in un file gli elementi validi presenti nel contenitore
|
|
void releasemem()
|
Libera la memoria e pulisce il contenitore (gli oggetti puntati vengono distrutti)
|
|
void checkdupl()
|
Controlla la presenza di duplicati presenti nel contenitore
|
Classe CFile_interface
|
Nome metodo
|
Descrizione
|
|
void readfile (string,CContainer*)
|
Legge i dati dal file di ingresso e popola il contenitore passato
|
|
void writefile (string,CContainer*)
|
Scrive in un file gli elementi validi presenti nel contenitore passato
|
Si utilizza una suite di test automatici per verificare la correttezza
di funzionamento delle classi principali e dei rispettivi metodi rilevanti.
Test della classe CItem
|
Nome test
|
Descrizione
|
|
testConstructor
|
Controlla la correttezza di un oggetto creato (deve essere vuoto e valido)
1-
nessun elemento
2-
valido
|
|
testEqual
|
Controlla la correttezza dell’operatore ==. Crea due oggetti CItem riempiendoli
con gli stessi caratteri e ne testa l’uguaglianza
|
|
testDifferent
|
Controlla la correttezza dell’operatore ==. Crea due oggetti CItem riempiendoli
con caratteri non uguali e ne testa la disuguaglianza
|
|
testMinorThan
|
Controlla la correttezza dell’operatore <. Crea due oggetti CItem , li riempie
e li confronta
1-
test su lunghezza diversa
2-
test su stessa lunghezza, ma diversi
3-
test su stessa lunghezza, ed uguali
|
|
testPush
|
Controlla che un carattere venga inserito correttamente (verifica che il numero
totale dei caratteri presenti venga incrementato di una unità)
|
|
testPop
|
Inserisce un carattere e successivamente lo estrae controllando il ripristino del
numero totale dei caratteri presenti
|
|
testPushPop
|
Esegue un push ed un pop controllando che il carattere inserito e quello estratto
siano identici
|
|
testTostring
|
Riempie l’oggetto CItem con una serie di caratteri e controlla che la stringa ottenuta
dalla conversione sia corretta (vedi descrizione del metodo)
|
|
testCheck
|
Controlla la validità del metodo di controllo (bilanciamento e grammatica) verificando
i seguenti casi
1-
controllo affermativo di “()” (tonda)
2-
controllo affermativo di “[]” (quadra)
3-
controllo affermativo di “{}”(graffa)
4-
controllo affermativo di “[()]” (inclusione)
5-
controllo affermativo di “[]()” (sequenza)
6-
controllo affermativo di “{[]()(())}” (varie)
7-
controllo negativo di “a” (carattere non ammesso)
8-
controllo negativo di “(” (parentesi non chiusa)
9-
controllo negativo di “)” (parentesi non aperta)
10-
controllo negativo di “[(])” (errata chiusura)
|
|
testValidity
|
Controlla il metodo getvalidity
1-
controlla un elemento valido “()”. Deve essere affermativo
2-
controlla un elemento non valido “(]”. Deve essere negativo
3- utilizza
il metodo setinvalid(); di invalidazione e controlla che l’elemento venga effettivamente
invalidato
|
|
testReset
|
Controlla l’avvenuto reset (svuotamento) dell’elemento CItem
|
Test della classe CContainer
|
Nome test
|
Descrizione
|
|
testConstructor
|
Controlla la correttezza di un contenitore creato (deve essere vuoto)
|
|
testAdd
|
Crea un oggetto CItem ed inserisce un puntatore a questo nel contenitore controllando
l’incremento del numero totale di oggetti contenuti
|
|
testPick
|
Crea un oggetto CItem ed inserisce un puntatore a questo nel contenitore, legge
l’elemento e lo confronta con quello inserito.
|
|
testCheckall
|
Controlla che il
contenitore verifichi la validità tutti gli elementi presenti (grammatica,
bilanciamento, duplicati)
1-
Inserisce due oggetti CItem non validi e controlla che il check sia corretto
2-
Inserisce due oggetti CItem contenente gli stessi caratteri e controlla che il check
sia corretto
|
|
testReleasemem
|
Controlla che il contenitore venga svuotato (gli oggetti puntati vengono distrutti)
|
Sono stati effettuati 16 test con esito positivo.
Brevi considerazioni sulle metodologie utilizzate per le parti “critiche”:
1 - bool CItem::check()
Per controllare la grammatica ed il bilanciamento della stringa
formata dalla sequenza di caratteri contenuti in un vector si utilizza un oggetto
locale di tipo CItem utilizzato come stack.
Viene considerato in sequenza ogni carattere presente nel CItem
principale e si opera come segue:
1- carattere non valido à invalida l’oggetto e termina il controllo. Si utilizza il metodo
privato checkchr
2- carattere “(“,”[“,”{“ parentesi aperta à inserisce (push) il carattere nello
stack. Si utilizza il metodo privato checkopn
3- carattere “)“,”]“,”} “ parentesi chiusa à estrae (pop) il carattere dallo stack
e ne controlla la “simmetria” rispetto al carattere letto. Se non è simmetrico invalida
l’oggetto e termina il controllo.Si utilizza il metodo checksim
Si procede sino al termine dei caratteri presenti nell’oggetto
principale. Se lo stack non risulta vuoto invalida l’oggetto ed esce. Ciò deriva
dalla possibilità di avere un caso di sbilanciamento come il seguente: ()(. Se non
eseguissi il controllo sullo stack non individuerei l’errore. In questo caso lo
stack contiene “(“ poiché non è mai stata estratta.
2 - Controllo degli elementi duplicati
Per controllare la presenza di elementi duplicati nel contenitore
si eseguono i seguenti passi:
1 – ordinamento degli elementi contenuti nel container (es: “a”,”b”,”b”,”c”)
in ordine crescente.
2 – ciclo di controllo che confronta l’elemento corrente col
successivo e se sono uguali li invalida.
Richiede la definizione di struct per l’ordinamento e l’overload
degli operatori == e < (o >)
Questo metodo risulta molto efficiente: è stato lasciato commentato un primo metodo,
funzionante, ma decisamente più lento.
Download dei file di progetto e documentazione

|