Diapositiva 1

1.
2.
3.
4.
5.
6.
7.
Esercizi su pile
Scrivere una funzione che restituisca una nuova pila che contiene i
valori di una pila in ingresso in ordine inverso. La pila originale non
deve essere modificata.
Scrivere una funzione che crea una copia della pila passata in
ingresso
Scrivere una funzione per verificare che le parentesi tonde e
quadre all’interno di una stringa siano correttamente annidate.
Scrivere una funzione per calcolare il valore di un’espressione
aritmetica espressa come stringa in forma postfissa contenente i
simboli 0, 1, …, 9, +, * e le parentesi ( ).
Scrivere una funzione che inverta l’ordine dei valori di una pila. La
funzione deve modificare la pila in ingresso e non crearne una
nuova.
Una parola o una frase palindroma può essere letta
indifferentemente da sinistra a destra o da destra a sinistra.
Scrivere una funzione che controlli se una data stringa è
palindroma utilizzando una pila.
Scrivere una funzione che stampi il contenuto di una pila senza
distruggerla e usando solo operazioni pop e push.
NOTA: scrivere sempre pre e post condizione di ogni funzione
Definizione di pila
struct nodo_pila
{
tipo_elemento el;
struct nodo_pila *next;
};
struct pila
{
struct nodo_pila *top;
};
dove tipo_elemento codifica il tipo di ogni elemento
della pila.
Esercizio 3
Scrivere una funzione per verificare che le parentesi
tonde e quadre all’interno di una stringa siano
correttamente annidate.
Pre condizioni:
la funzione prende in ingresso una stringa s che contiene
eventuali parentesi tonde e quadre
Post condizioni:
restituisce 1 se le parentesi contenute in s sono bilanciate, 0
altrimenti
Nota: se le parentesi sono solo tonde, basta verificare
che il contatore non diventi mai negativo.
Variante: stampare anche il contenuto di ogni coppia di
parentesi riconosciuta.
Svolgimento
int bilanciamento(char *s)
{
struct pila *p = crea_pila();
char c, par;
while(c = *s++)
{
switch(c)
{
case ‘(‘; case ‘[‘:
push(p, c);
break;
}
}
}
case ‘)’: case ‘]’:
if (pila_vuota(p) || !match(pop(p), c)) return 0;
break;
/* verifica che non ci siano parentesi rimaste aperte */
return pila_vuota(p);
int match(char p1, char p2) { return (p1 == ‘(‘ && p2 == ‘)’) || (p1 == ‘[‘ && p2 == ‘]’); }
Esercizio 4
Scrivere una funzione per calcolare il
valore di un’espressione aritmetica
espressa come stringa in forma postfissa
contenente i simboli 0, 1, …, 9, +, *.
Pre condizioni:
la funzione prende in ingresso una stringa contenente
un’espressione aritmetica in forma postfissa
Post condizioni:
la funzione restituisce il valore dell’espressione o emette un
errore se l’espressione non è ben formata
Variante: prevedere anche gli operatori -, /, % (modulo)
Svolgimento (2)
int valuta_postfissa(char *e)
{
struct pila *p = crea_pila();
char c;
while(c = *e++)
{
/* operando */
if ((c != ‘+’)&&(c != ‘*’)) { push(p, c-’0’); }
/* operatore */
else
{
int op1, op2;
op2 = pop(p);
op1 = pop(p);
switch(c)
{
case ‘+’: push(p, op1+op2); break;
case ‘*’: push(p, op1*op2); break;
}
}
}
}
return pop(p);
Per esercizio: ampliare la precondizione, ammettendo in ingresso stringhe che non siano in forma postfissa ed
emettendo errore in tal caso.
Esercizio 6
Una parola o una frase palindroma può essere
letta indifferentemente da sinistra a destra o
da destra a sinistra. Scrivere una funzione che
controlli se una data stringa è palindroma
utilizzando una pila.
Pre condizioni:
la funzione prende in ingresso una stringa
Post condizioni:
restituisce 1 se la stringa è palindroma, 0 altrimenti
Nota: è possibile ottimizzare confrontando i
valori sulla pila con la seconda metà della stringa
Svolgimento (non ottimizzato)
int palindroma(char *s)
{
char *s2 = s;
struct pila *p = crea_pila();
char c;
while(c = *s++) push(p, c);
while(!is_empty(p)) if (pop(p) != *s2++) return
0;
}
return 1;
Svolgimento (ottimizzato)
int palindroma2(char *s)
{
struct pila *p = crea_pila();
char c;
int slen = strlen(s);
int len = slen/2;
while(len--) push(p, *s++);
/* se s è una stringa dispari, salta il carattere centrale */
if (slen % 2) s++;
while(!is_empty(p)) if (pop(p) != *s++) return 0;
}
return 1;
Esercizio 8 (bonus!!)
Realizzare una funzione che, dato un array bidimensionale
(labirinto), una cella di partenza p e una cella di arrivo a, restituisca
1 se è possibile raggiungere a da p passando solo per celle del
labirinto di valore 0 (le celle di valore == 1 rappresentano i muri del
labirinto). Utilizzare una pila.
Pre condizioni:
la funzione prende in ingresso un array bidimensionale a valori 0 e 1 e
due puntatori a una struttura cella che rappresenta una coordinata
all’interno del labirinto.
Post condizioni:
restituisce 0 se esiste un cammino di celle di valore 0 da p ad
a; restituisce 1 altrimenti.
Variante: scrivere una funzione che restituisca (se esiste) un
possibile cammino che porta da p ad a
typedef struct
{
int x;
int y;
} cella;
Ragioniamoci
Esempio di matrice labirinto:
int labirinto[MAX_Y][MAX_X] =
{
{ 0, 0, 0, 1, 0, },
{ 0, 1, 1, 1, 0, },
{ 0, 0, 0, 1, 1, },
{ 0, 1, 0, 0, 0, },
{ 0, 0, 1, 1, 0, },
};
Prototipo della funzione: int labirinto(int **lab, cella p, cella a);
In rosso un percorso che porta da (0, 0) a (4, 4) (su questi input la funzione
deve restituire 1)