Ultimo aggiornamento: 2023-03-25
Implementare uno stack di interi basato su array. In certe situazioni (descritte sotto), l’array può essere ridimensionato in modo da consentire allo stack di allargarsi o contrarsi in base al numero di elementi effettivamente presenti.
Lo stack è rappresentato dalla struttura Stack
seguente:
dove capacity
indica la lunghezza dell’array data[]
, e size
indica il numero di elementi effettivamente presenti nello stack. Durante tutta la vita di uno stack si deve sempre avere size
\(\leq\) capacity
.
Si realizzi una prima versione in cui il valore dell’attributo capacity
viene definito all’atto della creazione (ad esempio, capacity = 1000
) e rimanga sempre costante. In questo modo lo stack non potrà mai contenere più di capacity
elementi.
Una volta verificata la correttezza della versione di cui sopra, la si modifichi in modo da ridimensionare l’array data[]
usando la politica seguente:
All’atto della creazione, si pone size = 0
e capacity = 1
.
Se dopo una operazione di inserimento si ha size == capacity
, si alloca un nuovo array data
di capienza doppia, si copiano i valori dal vecchio al nuovo array e si pone capacity = 2*capacity
. Il vecchio array viene distrutto, e il nuovo prende il suo posto nella struttura stack.
Se dopo una operazione di cancellazione si ha size < capacity / 4
, si alloca un nuovo array data
di capienza dimezzata, si copiano i valori dal vecchio al nuovo array e si pone capacity = capacity / 2
. Il vecchio array viene distrutto, e il nuovo prende il suo posto nella struttura stack.
Nota: Non usare la funzione
realloc()
(per chi sa cos’è); è richiesto di allocare un nuovo array conmalloc()
, copiare i dati, effettuare lafree()
del vecchio array e settare il puntatoredata
della strutturaStack
al nuovo array.
Si può dimostrare che la strategia di cui sopra garantisce:
size / capacity
, e indica quale frazione dell’array è effettivamente utilizzata per contenere valori.Il programma stack-main.c legge da file una sequenza di comandi da eseguire su uno stack inizialmente vuoto. I comandi validi sono i seguenti:
Operazione | Significato |
---|---|
i val |
inserisci val in cima allo stack (push) |
p |
cancella il valore in cima allo stack (pop) |
c |
svuota lo stack (clear) |
t |
stampa il valore in cima allo stack senza cancellarlo (top) |
s |
stampa il contenuto dello stack senza modificarlo |
Per compilare:
gcc -std=c90 -Wall -Wpedantic stack.c stack-main.c -o stack-main
Per eseguire in ambiente Linux/MacOSX:
./stack-main stack.in
Per eseguire in ambiente Windows:
.\stack-main stack.in
Estendere il programma stack-main.c per gestire le seguenti ulteriori operazioni; indichiamo con \(s_1\) in valore in cima allo stack e con \(s_2\) il valore immediatamente sotto di esso:
Operazione | Significato |
---|---|
+ |
Estrai \(s_1, s_2\); al loro posto inserisci \(s_1 + s_2\) |
- |
Estrai \(s_1, s_2\); al loro posto inserisci \(s_1 - s_2\) |
* |
Estrai \(s_1, s_2\); al loro posto inserisci \(s_1 \times s_2\) |
/ |
Estrai \(s_1, s_2\); al loro posto inserisci \(s_1 / s_2\) (divisione intera) |
: |
Duplica il valore in cima allo stack; in altre parole, inserisci una nuova copia di \(s_1\) in cima allo stack. |
[ |
Scambia tra di loro i due valori in cima allo stack; in altre parole, rende \(s_2\) l’elemento in cima allo stack, e \(s_1\) quello subito sotto di esso. |
Si può assumere che l’input sia sempre corretto, quindi ad esempio in presenza del comando ‘+’ si può assumere che ci siano sempre almeno due elementi nello stack; è tuttavia opportuno rendere il programma robusto possibile inserendo opportuni controlli.
Le operazioni precedenti consentiranno di usare questo programma come una calcolatrice RPN (Reverse Polish Notation). La notazione RPN consente di rappresentare una espressione aritmetica senza fare uso di parentesi e indicando gli operatori dopo gli argomenti su cui devono operare. Ad esempio, l’espressione
(2 + 3) * 4
viene rappresentata come la sequenza di istruzioni:
i 2
i 3
+
i 4
*
I file di input seguenti contengono le operazioni aritmetiche illustrate nella sezione “Per approfondire”: