Semplificando un po’ le cose, chiamiamo documento html una sequenza di tag del tipo <a>
(detti tag
di apertura) oppure </a>
(detti tag di chiusura), dove a
è una qualsiasi stringa di caratteri alfabetici.
Diciamo che un documento html è ben formato se i tag sono correttamente annidati (segue una definizione più precisa con alcuni esempi).
Scrivete un programma che legga una sequenza di tag e stabilisca se costituisce un documento html ben formato oppure no. Per farlo, usate una pila di cui trovate un’implementazione parziale nel programma in calce.
Suggerimento: esaminate i tag in ordine inserendo nella pila solo i tag di apertura; quando incontrate un tag di chiusura verificate che sia quello giusto controllando la pila... Se arrivate alla fine ma la pila non è vuota, allora...
Potete assumere che i nomi dei tag siano lunghi al massimo 10 caratteri e non contengano spazi, quindi per leggere un tag potete usare (con qualche cautela!) scanf( "%s", ... )
.
Un documento html è ben formato se l’ordine dei tag soddisfa questi due criteri:
Ad esempio, la sequenza
<a> <b> </b> <c> <d> </d> </c> </a>
costituisce un documento html ben formato. Al contrario, la sequenza
<a> <b>
non lo è perché i tag non sono mai chiusi. Analogamente, la sequenza
<a> <b> </a> </b>
non è un documento html perché il tag </a>
viene chiuso prima del tag <b>
, e la sequenza
<a> </a> </c>
non è un documento html perché il tag </c>
viene chiuso senza essere mai stato aperto.
Eseguendo
./soluzione
avendo nel flusso di ingresso la sequenza di tag:
<a> <b> </b> <c> <d> </d> </c> </a>
il programma emette sul flusso di uscita:
OK
Eseguendo
./soluzione
avendo nel flusso di ingresso i numeri:
<a> <b> </a> </b>
il programma emette sul flusso di uscita:
NO
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
typedef char *Item;
// Pila implementata come lista di interi (inserimento e cancellazione avvengono solo in testa)
struct element {
Item value;
struct element *next;
};
typedef struct element Element;
struct stack {
Element *head;
};
typedef struct stack *Stack;
Stack init( void ); /* alloca lo spazio per una pila vuota e ne restituisce un puntatore */
void destroy( Stack ); /* svuota la pila liberando la memoria */
int is_empty( Stack ); /* restituisce 1 se la pila e' vuota, 0 altrimenti */
Item top( Stack ); /* se la pila non e' vuota, restituisce il top de1la pila; altrimenti esce con messaggio di errore. */
Item pop( Stack ); /* se la pila non e' vuota, estrae il top da1la pila e lo restituisce; altrimenti esce con messaggio di errore. */
void push( Stack, Item ); /* se c'e' spazio, aggiunge l'item alla pila; altrimenti esce con messaggio d'errore. */
void print_stack( Stack ); /* stampa il contenuto della pila, partendo dal top. */
/********************************************************************
INSERIRE QUI LA FUNZIONE MAIN E EVENTUALI ALTRE FUNZIONI AGGIUNTIVE
********************************************************************/
...
int main() {
...
}
Stack init( void ) {
Stack s = malloc( sizeof (struct stack) );
if ( s == NULL ) {
printf( "err malloc\n" );
exit( EXIT_FAILURE );
}
s -> head = NULL;
return s;
}
void print_stack( Stack s ) {
Element *p;
if ( s == NULL )
return;
printf( "Contenuto della pila: " );
for ( p = s -> head; p != NULL; p = p -> next ) {
printf( "%s", p -> value );
printf( " " );
}
printf( ".\n" );
}
void destroy( Stack s ) {
Element *p, *old;
for ( p = s -> head; p != NULL; ) {
old = p;
p = p -> next;
free( old );
}
free( s );
}
int is_empty( Stack s ){
return ( s -> head == NULL );
}
Item top( Stack s ){
if ( is_empty( s ) ) {
printf( "err pop: pila vuota\n" );
exit( EXIT_FAILURE );
}
return s -> head -> value;
}
void push( Stack s, Item item ){
Element *new = malloc( sizeof( Element ) );
if ( new == NULL ) {
printf( "err push: pila piena!\n" );
exit( EXIT_FAILURE );
}
new -> value = item;
new -> next = s -> head;
s -> head = new;
}
/******* COMPLETATE LA FUNZIONE POP: *************/
Item pop( Stack s ){
Item item;
Element *old;
if ( is_empty( s ) ) {
printf( "err pop: pila vuota\n" );
exit( EXIT_FAILURE );
}
...
return item;
}