Lezione 22
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>

//Implementazione dello stack di caratteri tramite liste
typedef struct Elem {  //Elemento della lista
    char              c;
    struct Elem *next;
} Elem;

struct CharStack {
    Elem *top;      //Puntatore all'elemento in cima allo stack
};

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).
//Funzione ausiliaria che elabora il valore v
void value(CSPtr stack, char v) {
    char op = CS_top(stack);
    if (op == '!') {
        CS_pop(stack);                //estrai l'operatore dalla pila e
        v = (v == 'T' ? 'F' : 'T');   //calcola il valore di NOT v
        op = CS_top(stack);
    }
    if (op == '&' || op == '|') {  //Se il simbolo in cima alla pila e' un operatore
        CS_pop(stack);             //estrai l'operatore dalla pila e
        char v0 = CS_pop(stack);   //estrai anche il valore precedente
        if (op == '&')             //Calcola il valore di v op v0
            v = (v == 'T' && v0 == 'T' ? 'T' : 'F');
        else
            v = (v == 'F' && v0 == 'F' ? 'F' : 'T');
    }
    CS_push(stack, v);
}
Discussione esercizio 42:
//Funzione ausiliaria che elabora il valore v
void value(CSPtr stack, char v) {
    char op = CS_top(stack);
    if (op == '+' || op == '*') {  //Se il simbolo in cima alla pila e' un operatore
        CS_pop(stack);             //estrai l'operatore dalla pila e
        char v0 = CS_pop(stack);   //estrai anche il valore precedente
        if (op == '+')             //Calcola il valore di v op v0
            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);  // il valore dell'espressione tra parentesi
                CS_pop(stack);      // la relativa parentesi aperta
                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;       //Per mantenere il puntatore alla locazione in cui
                         //mettere il puntatore al primo dei nuovi elementi
    while (k > 0 && *p != NULL) {    //Scorri la lista fino al k-esimo elemento
        p = &((*p)->next);
        k--;
    }
    Elem *next = *p;     //Salva il puntatore al k-esimo elemento
    int i;
    for (i = 0 ; i < n ; i++) {      //Inserisci i nuovi elementi
        *p = malloc(sizeof(Elem));
        (*p)->val = A[i];
        p = &((*p)->next);
    }
    *p = next;           //Aggancia l'ultimo dei nuovi elementi al k-esimo elemento
    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) {     //È un elemento che precede p->next tale che tf(e, p->next) è vero
            e = p->next;
            p->next = e->next;     //Sgancia l'elemento dalla lista src
            Item **d = &dst;
            while (*d != NULL && (*d)->code < e->code)
                d = &((*d)->next);
            e->next = *d;          //Inserisci l'elemento nella lista dst
            *d = e;
        } else
            p = p->next;
    }
    return dst;
}