LabASD - Stack LIFO

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:

• 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 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:

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:

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

• stack.c
• stack.h
• stack-main.c
• stack.in (output atteso)

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

• stack-rpn.in (output atteso)
• stack-rpn1.in
• stack-rpn2.in
• stack-rpn3.in
• stack-rpn4.in
• stack-rpn5.in