Tag html

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", ... ).

Quando un documento è ben formato

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.

Esempio

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

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso i numeri:

<a> <b> </a> </b>

il programma emette sul flusso di uscita:

NO

Programma da completare

#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;
}