Discussione esercizio 41:
Prima di tutto l'implementazione (nel file
charstack.c
) dell'interfaccia
charstack.h
per
la realizzazione di una pila di caratteri.
#include "charstack.h"
#include <stdlib.h>
typedef struct Elem {
char c;
struct Elem *next;
} Elem;
struct CharStack {
Elem *top;
};
CSPtr CS_new() {
CSPtr stack = malloc(sizeof(struct CharStack));
stack->top = NULL;
return stack;
}
void CS_push(CSPtr stack, char c) {
Elem *e = malloc(sizeof(Elem));
e->c = c;
e->next = stack->top;
stack->top = e;
}
char CS_pop(CSPtr stack) {
if (stack->top != NULL) {
Elem *e = stack->top;
char c = e->c;
stack->top = e->next;
free(e);
return c;
} else
return '\0';
}
char CS_top(CSPtr stack) {
return (stack->top != NULL ? stack->top->c : '\0');
}
int CS_isempty(CSPtr stack) {
return (stack->top == NULL);
}
void CS_dispose(CSPtr stack) {
Elem *e = stack->top;
while (e != NULL) {
Elem *next = e->next;
free(e);
e = next;
}
free(stack);
}
Per la soluzione dell'esercizio basta seguire lo stesso schema della funzione
boolformula
.
L'operatore NOT va trattato nello
switch - case
alla stessa stregua degli altri
operatori (cioè, va aggiunto un
case
per
'!'
dove sono trattati anche
gli altri due operatori). Però bisogna anche tener presente che l'operatore NOT è unario
(a differenza degli oparatori AND e OR che sono binari). Questo significa che il NOT può essere valutato
non appena è disponibile il valore alla sua destra. La funzione
value
si occupa di valutare
gli operatori e quindi anche il NOT (anche questa è una modifica della versione precedente).
void value(CSPtr stack, char v) {
char op = CS_top(stack);
if (op == '!') {
CS_pop(stack);
v = (v == 'T' ? 'F' : 'T');
op = CS_top(stack);
}
if (op == '&' || op == '|') {
CS_pop(stack);
char v0 = CS_pop(stack);
if (op == '&')
v = (v == 'T' && v0 == 'T' ? 'T' : 'F');
else
v = (v == 'F' && v0 == 'F' ? 'F' : 'T');
}
CS_push(stack, v);
}
Discussione esercizio 42:
void value(CSPtr stack, char v) {
char op = CS_top(stack);
if (op == '+' || op == '*') {
CS_pop(stack);
char v0 = CS_pop(stack);
if (op == '+')
v = '0' + ((v0 - '0' + v - '0') % 10);
else
v = '0' + (((v0 - '0')*(v - '0')) % 10);
}
CS_push(stack, v);
}
int mod10formula(char *f) {
int i;
CSPtr stack = CS_new();
for (i = 0 ; f[i] != '\0' ; i++) {
char c, v;
switch (f[i]) {
case '(': case '+': case '*':
CS_push(stack, f[i]);
break;
case ')':
v = CS_pop(stack);
CS_pop(stack);
value(stack, v);
break;
default:
if ('0' <= f[i] && f[i] <= '9')
value(stack, f[i]);
}
}
int val = CS_top(stack) - '0';
CS_dispose(stack);
return val;
}
Discussione dell'esercizio 4 dell'
Esempio 1.
#include <stdlib.h>
List insarray(List L, int k, int A[], int n) {
Elem **p = &L;
while (k > 0 && *p != NULL) {
p = &((*p)->next);
k--;
}
Elem *next = *p;
int i;
for (i = 0 ; i < n ; i++) {
*p = malloc(sizeof(Elem));
(*p)->val = A[i];
p = &((*p)->next);
}
*p = next;
return L;
}
Discussione dell'esercizio 6 dell'
Esempio 2.
List transfer(List src, int (*tf)(Item *, Item *), List dst) {
if (src == NULL) return dst;
Item *p = src;
while (p->next != NULL) {
Item *e = src;
while (e != p->next && !tf(e, p->next))
e = e->next;
if (e != p->next) {
e = p->next;
p->next = e->next;
Item **d = &dst;
while (*d != NULL && (*d)->code < e->code)
d = &((*d)->next);
e->next = *d;
*d = e;
} else
p = p->next;
}
return dst;
}