LabASD - Stack LIFO

Moreno Marzolla

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:

typedef int StackInfo;

typedef struct {
    int size;
    int capacity;
    StackInfo *data;
} Stack;

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:

Nota: Non usare la funzione realloc() (per chi sa cos’è); è richiesto di allocare un nuovo array con malloc(), copiare i dati, effettuare la free() del vecchio array e settare il puntatore data della struttura Stack al nuovo array.

Si può dimostrare che la strategia di cui sopra garantisce:

  1. che il costo ammortizzato di una qualunque sequenza di operazioni sia \(O(1)\)
  2. che il fattore di utilizzo dell’array non scenda mai sotto il \(25\%\); il fattore di utilizzo è il rapporto 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

Per approfondire

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
*

File

I file di input seguenti contengono le operazioni aritmetiche illustrate nella sezione “Per approfondire”: