Stampa per blocchi di una sequenza con parentesi
L'obiettivo dell'esercizio è scrivere un programma che legge da input una sequenza di numeri interi positivi racchiusi tra coppie di parentesi ben bilanciate, e stampa la sequenza per blocchi in base all'annidamento delle parentesi. Ad esempio, alla sequenza
12 24 31 ( 1 ( 2 3 ) 4 ( 5 6 ) ) 7 ( 2 ( 1 4 ) 7 8 ) 21
corrisponde l'output
2: 2 3
2: 5 6
1: 1 4.
2: 1 4
1: 2 7 8
0: 12 24 31 7 21
Più precisamente, abiamo che:
- un blocco è formato da tutti i numeri racchiusi tra una coppia di parentesi aperta/chiusa non contenuti all'interno di parentesi più interne, con l'eccezione del blocco più esterno o di livello 0 che è formato da tutti i numeri non contenuti all'interno di parentesi;
- i numeri che compongono i blocchi andranno stampati rispettando l'ordine in cui appaiono nella sequenza;
- i blocchi andranno stampati uno per riga e preceduti dal livello di annidamento del blocco (il numero di coppie di parentesi aperta/chiusa che lo racchiudono) e dal carattere ':';
- i blocchi andranno stampati tenendo conto che ogni blocco deve precedere i blocchi che lo contengono e i blocchi esterni che lo seguono (a destra nella sequenza).
Per semplificare la lettura della sequenza di input, le parentesi saranno rappresentate dai numeri negativi -1, per la parenetsi aperta, e -2, per la parentesi chiusa, e la fine della sequenza sarà indicata dal numero 0. Ad esempio, a
12 24 31 ( 1 ( 2 3 ) 4 ( 5 6 ) ) 7 ( 2 ( 1 4 ) 7 8 ) 21
corrisponde l'input
12 24 31 -1 1 -1 2 3 -2 4 -1 5 6 -2 -2 7 -1 2 -1 1 4 -2 7 8 -2 21 0
Per la realizzazione delle strutture dati necessarie alla soluzione dell'esercizio è possibile utilizzare o adattare le implementazioni (di pile e code) fornite sul sito del corso.
Suggerimento
Si osservi che all'interno di ogni blocco i numeri vano stampati rispettando l'ordine di arrivo, mentre i blocchi vanno stampati non appena completati, tenendo conto che ogni parentesi aperta inizia un nuovo blocco e che ogni parentesi chiusa termina un blocco.
--
StefanoGuerrini - 09 May 2007