Risoluzione esame TAPS (Tecniche Avanzate di Progettazione Software)

 
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:

 diagramma uml

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


Commenti degli utenti:


Scrivi un commento
 

Per inserire un commento è necessario essere loggati