Discussione esercizio 39:

#include <stdio.h>
#include <string.h>

/* Conta il numero di occorrenze della stringa str nel file di testo f.
 * Implementazione: è una semplice modifica della funzione filefind(). */
int filenumocc(FILE *f, const char *str) {
    int n = strlen(str) + 1, count = 0;
    long pos = 0;
    char buffer[n];
    rewind(f)
    while (fgets(buffer, n, f) != NULL) {
        if (strcmp(buffer, str) == 0)
            count++;
        fseek(f, pos, SEEK_SET);
        fgetc(f);
        pos = ftell(f);
    }
    return count;
}

Discussione esercizio 40:

#include <stdio.h>

int prime(long long n) {   //Ritorna vero se e solo se n è un numero primo
    long long k = 2;
    while (k * k < n && (n % k) != 0) k++;
    return (k >= n || (n % k) != 0);
}

void writeprimetable(char *fname, int np) {
    FILE *f = fopen(fname, "wb");
    if (f == NULL) return;
    long n = 2, count = 0;
    while (count < np) {
        if (prime(n)) {
            fwrite(&n, sizeof(long), 1, f);
            count++;
        }
        n++;
    }
    fclose(f);
}

#define NUM_PRIMES     1000000L

int main(int argc, char *argv[]) {
    if (argc != 2) return 0;
    FILE *f = fopen(argv[1], "rb");   //Apre il file con la tabella
    if (f == NULL) {                  //Se il file non esiste lo crea
        printf("Elaborazione tabella...\n");
        writeprimetable(argv[1], NUM_PRIMES);
        printf("OK\n");
        f = fopen(argv[1], "rb");
    }
    if (f == NULL) return 0;
    while (1) {
        long k, p;
        printf("Numero d'ordine del numero primo (1 - %ld), 0 per terminare: ",
                NUM_PRIMES);
        scanf("%ld", &k);
        if (k < 1 || k > NUM_PRIMES) break;
        fseek(f, (k - 1)*sizeof(long), SEEK_SET);
        fread(&p, sizeof(long), 1, f);
        printf("Il %ld-esimo numero primo e' %ld\n", k, p);
    }
    return 0;
}

La struttura dati  Pila  (Stack): struttura LIFO (Last In First Out), l'ultimo entrato è il primo ad uscire.

• Usi tipici: nei compilatori (stack delle chiamate), parsing di espressioni/codice, visite di alberi/grafi.
• Operazioni:

  push

  inserisce un nuovo elemento in cima alla pila

  pop

  preleva (e ritorna) l'elemento in cima

  top

  ritorna l'elemento in cima (senza rimuoverlo)

• Implementazioni: array, liste, array circolari.

La struttura dati  Coda  (Queue): struttura FIFO (First In First Out), il primo entrato è il primo ad uscire.

• Usi tipici: nei sistemi operativi per distribuire le risorse, coda di stampa, nei sistemi di simulazione (ad es. traffico aereo), visite di grafi.
• Operazioni:

  enqueue

  inserisce un nuovo elemento in coda

  dequeue

  preleva l'elemento in testa

  first

  ritorna l'elemento in testa (senza rimuoverlo)

• Implementazioni: array, liste, array circolari.

Esempio di uso di pile. Valutazione di semplici formule booleane: valori vero e falso rappresentati dai caratteri 'T' e 'F', operatori AND e OR rappresentati da '&' e '|' e le parentesi '(' e ')'. Un esempio di formula è il seguente T & (F | T & T) | F & (T & (F | F)) il cui valore è F.

Assumiamo che la formula da valutare sia sintatticamente corretta. Per calcolare il valore di verità di una formula usiamo una pila per mantenere i simboli della formula che non possono essere ancora elaborati. I simboli della formula sono letti uno a uno, se il simbolo non può essere elaborato è inserito in cima alla pila, se invece può essere elaborato in congiunzione con il simbolo in cima alla pila, il risultato dell'elaborazione è inserito in cima alla pila al posto dei simboli elaborati. Ci sono solamente due casi in cui il prossimo simbolo X della formula può essere elaborato (sia C il simbolo in cima alla pila):

1. X è un valore e C è un operatore:   il simbolo che precede quello in cima alla pila deve essere necessariamente un valore Y e così il risultato dell'operazione X C Y è posto in cima alla pila al posto di C e Y.
2. X = ')':   C deve essere necessariamente un valore e il simbolo che lo precede deve essere '('. I simboli C e '(' sono prelevati dalla pila. Se il simbolo in cima alla pila è un operatore si procede come nel caso (1), altrimenti C è inserito in cima alla pila.

Quindi, tutte le volte che il prossimo simbolo è '(' o un operatore è inserito in cima alla pila e anche quando è un valore e o la pila è vuota o il simbolo in cima alla pila è '('.

Ecco un esempio di valutazione per la formula F | ( T & ( F | T ) ).

Formula: F | ( T & ( F |        //I primi 7 simboli sono inseriti nella pila
                                //perché non possono essere elaborati
Pila:    F | ( T & ( F |


Formula: F | ( T & ( F | T      //Il prossimo simbolo 'T' può essere elaborato
                                //perché in cima alla pila c'è un operatore
Pila:    F | ( T & ( F |


Formula: F | ( T & ( F | T      //I simboli in cima alla pila '|' e 'F' sono
                                //prelevati e il risultato dell'operazione
                                //'F | T' è inserito in cima alla pila
Pila:    F | ( T & ( T


Formula: F | ( T & ( F | T )    //Il prossimo simbolo ')' può essere elaborato
                                //perché è una parentesi chiusa
Pila:    F | ( T & ( T


Formula: F | ( T & ( F | T )    //I simboli in cima 'T' e '(' sono prelevati ed
                                //essendo il simbolo in cima un operatore,
                                //l'operazione 'T & T' può essere effettuata e
                                //il risultato posto in cima alla pila
Pila:    F | ( T


Formula: F | ( T & ( F | T ) )  //Il prossimo simbolo ')' può essere elaborato
                                //perché è una parentesi chiusa
Pila:    F | ( T


Formula: F | ( T & ( F | T ) )  //I simboli in cima 'T' e '(' sono prelevati ed
                                //essendo il simbolo in cima un operatore,
                                //l'operazione 'F | T' può essere effettuata e
                                //il risultato posto in cima alla pila
Pila:   T

Per realizzare questo semplice valutatore di espressioni boolane ci occorre una pila di caratteri. Ecco una interfaccia per una tale piccola libreria:

/***************************** FILE charstack.h *******************************/
#ifndef _CHARSTACK_H
#define _CHARSTACK_H

typedef struct CharStack *CSPtr;  //Puntatore a uno stack di caratteri
// Crea un nuovo stack vuoto
CSPtr CS_new();
//Inserisce il carattere c in cima allo stack
void CS_push(CSPtr stack, char c);
//Preleva il carattere in cima e lo ritorna. Se lo stack è vuoto ritorna
char CS_pop(CSPtr stack);       //il carattere '\0'.
//Ritorna il carattere in cima. Se lo stack è vuoto ritorna '\0'
char CS_top(CSPtr stack);
//Ritorna vero se lo stack è vuoto, altrimenti ritorna falso
int CS_isempty(CSPtr stack);
//Distrugge lo stack rilasciando tutta la memoria
void CS_dispose(CSPtr stack);

#endif  /* _CHARSTACK_H */

L'implementazione (nel file charstack.c) è lasciata per esercizio. Ecco l'implementazione di una funzione int boolformula(char *formula), che valuta la formula booleana contenuta nella stringa formula, usando una pila di caratteri e un programma per provare la funzione.

#include "charstack.h"
#include "util.h"
#include <stdio.h>

/* Valuta il valore di verità della formula booleana f. Ritorna 0 se il valore
 * è falso e un intero diverso da 0 se il valore è vero. I caratteri
 * significativi sono i seguenti:
 * '(', ')'   per delimitare le sotto-espressioni
 * '&', '|'   operatori AND e OR
 * 'T', 'F'   valori vero e falso
 * Tutti gli altri caratteri sono ignorati. Per le espressioni con più di due
 * operandi l'associatività è a sinistra:
 *     V0 OP1 V1 OP2 V2 OP3 V3 ... OPk Vk è valutato come se fosse
 *     (...(((V0 OP1 V1) OP2 V2) OP3 V3) ... OPk Vk).
 * Non effettua controlli sulla correttezza sintattica della formula. Esempi:
 * T & T & F & F | T          valore vero
 * T & ((T & T) | F) | F      valore vero
 * (T & (T & (F & (F | T))))  valore falso    */
int boolformula(char *f);

#define FORMULA_MAXLEN     1000

int main() {
    char formula[FORMULA_MAXLEN + 1];
    while (1) {
        printf("Inserire una formula booleana (ad es. ((T & (F | T)) | F):\n");
        if (input_line(NULL, formula, FORMULA_MAXLEN) == 0) break;
        int val = boolformula(formula);
        printf("Il valore della formula e': %s\n", (val ? "VERO" : "FALSO"));
    }
    return 0;
}

//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 è 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);
}

int boolformula(char *f) {
    CSPtr stack = CS_new();
    for (int i = 0 ; f[i] != '\0' ; i++) {  //Legge uno ad uno i caratteri della formula
        char v;
        switch (f[i]) {
            case '(': case '&': case '|':   //Caratteri da inserire nella pila (sempre)
                CS_push(stack, f[i]);
                break;
            case 'T': case 'F':             //Valori di verità
                value(stack, f[i]);
                break;
            case ')':                       //Parentesi chiusa
                v = CS_pop(stack);  //Il valore dell'espressione tra parentesi
                CS_pop(stack);      //La relativa parentesi aperta
                value(stack, v);
                break;
            default: ;                      //Tutti gli altri caratteri sono ignorati
        }
    }
    int val = (CS_top(stack) == 'T');
    CS_dispose(stack);
    return val;
}

Esercizio 41    Estendere le capacità della funzione int boolformula(char *formula) così che possa valutare anche formule con l'operatore NOT, rappresentato dal carattere '!'. Quindi, dovrebbe valutare formule come F | ! ( T & ( ! F | F ) ) (che ha valore falso).
Esercizio 42    Modificare la funzione int boolformula(char *formula) per implementare una funzione int mod10formula(char *formula) che valuta semplici formule nell'aritmetica modulo 10. Tali formule sono formate dai caratteri '(', ')', '+', '*', '0', '1', ..., '9', dove gli operatori '+' e '*' sono la somma e la moltiplicazione modulo 10. Ad esempio, la formula 3 + (4*(2 + 6 + 9)*(1 + 9) + 6) ha valore 9.