FireTeam

Per fare
questo abbiamo bisogno del tipo di dato astratto rappresentato dall’albero
binario, in cui ogni nodo rappresenta un elemento dell’espressione inserita,
che utilizzeremo anche per dare le tre diverse letture di una espressione
aritmetica (polacca, post-fissa,pre-fissa).

Definiremo
dunque un albero binario in cui ciascun nodo ha una struttura in cui oltre ad
un campo contenente l’elemento del particolare nodo, ci sarà un nodo key che ci
permetterà di chiarire anzitempo la natura del nodo, cioè se è un numero
(key=0) o un operatore (1<=key<=5); inoltre ci dovrà essere un puntatore
al figlio sinistro e al figlio destro.

Con
la costruzione di questo albero
saremo in grado di stabilire le priorità tra gli operatori facenti parte
dell’espressione e gli operandi su cui essi agiscono, effettuando quindi nel
giusto ordine le operazioni inserite nell’espressione.

L’implementazione
della valutazione dell’albero scorre tutto l’albero iniziando la valutazione
dell’espressione a partire dalle foglie fino a risalire alla radice. Da notare
che tra quelli definiti l’operatore “-“ è l’unico che può essere interpretato
come operatore binario o unario a seconda che il figlio sinistro esista o meno.

Una volta riconosciute
le espressioni e quindi le operazioni da effettuare grazie alla lettura
dell’albero che le rappresenta, il nostro software visualizzerà a video i tre
tipi di lettura e infine il risultato. Da notare che tale programma consente
l’utilizzo delle parentesi che logicamente non sono rappresentate nell’albero
ma la cui presenza è importante per una buona comprensione dell’espressione sia
da parte dell’utente che dell’algoritmo stesso; inoltre per poter inserire in
una espressione dei numeri negativi essi dovranno essere inseriti tra
parentesi, praticamente si scriverà 3+(-6) e non 3+-6, aumentandone così anche
la leggibilità.

UTILIZZAZIONE ED ESEMPIO
D’USO

Compilando ed eseguendo valutatore.c vengono
quindi date innanzitutto delle note all’uso del software e dopo l’inserimento
dell’espressione da parte dell’utente si procede prima alla stampa
dell’espressione secondo la lettura simmetrica, anticipata e differita e infine
viene stampato a video il risultato ottenuto dalla valutazione
dell’espressione.

CODICE SORGENTE

ADTab.h

Innanzitutto ci
sarà una libreria di funzioni utili per la gestione della struttura dati
rappresentato dall’albero binario

/******************************************************************************

*
ALBERO BINARIO HEADER FILE
*

* funzioni per manipolare
l’Abstract Data Type albero binario *

******************************************************************************/

/*********************** DEFINIZIONE STRUTTURA DATI ***********************/

typedef int
tipoelemento; /*permette di
modificare il tipo dell’elemento*/

typedef int tipochiave; /*permette di modificare il
tipo della chiave*/

typedef struct tiponodo *TipoADTab;

typedef struct tiponodo{ /*definizione della struttura dei nodi
*/

tipoelemento *elemento; /* puntatore all’elemento del nodo
*/

tipochiave key; /*campo che ci
permette di chiarire se

un nodo contiene un operatore o un numero*/

TipoADTab sx; /*puntatore al figlio sinistro
*/

TipoADTab dx;
/*puntatore al figlio destro */

} tiponodo;

/******************* FUNZIONI DI GESTIONE
DELL’ALBERO
*********************/

void
ADTab_CreaAlbero(TipoADTab *);

/******************************************************************************

* Dato in input un albero
binario lo prepara all’uso. Se l’albero contiene dei*

* dati allora bisogna prima
cancellarli!!!
*

******************************************************************************/

void
ADTab_CancellaAlbero(TipoADTab *);

/******************************************************************************

* Dato in input un albero
binario lo cancella completamente
*

******************************************************************************/

void ADTab_CreaNodo(TipoADTab
*);

/******************************************************************************

* Dato in input nodo
dell’albero gli alloca memoria e imposta a NULL i due *

* puntatori ai nodi
figli
*

******************************************************************************/

void
ADTab_InserisciKey(TipoADTab,tipochiave);

/******************************************************************************

* Dato in input nodo
dell’albero e una chiave per esso, registra la chiave *

* nel nodo.
*

******************************************************************************/

void
ADTab_InserisciElemento(TipoADTab,tipoelemento);

/******************************************************************************

* Dato in input nodo
dell’albero e un elemento per esso, registra l’elemento *

* nel nodo. *

******************************************************************************/

tipochiave
ADTab_MostraKey(TipoADTab);

/******************************************************************************

* Dato in input un nodo
dell’albero, da in output la sua chiave.
*

******************************************************************************/

tipoelemento
ADTab_MostraElemento(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero, da in output il suo elemento
*

******************************************************************************/

int
ADTab_AlberoVuoto(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero controlla se l’albero è vuoto o meno. *

******************************************************************************/

TipoADTab
ADTab_AlberoSinistro(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero restituisce il sottoalbero sinitro. *

******************************************************************************/

TipoADTab
ADTab_AlberoDestro(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero restituisce il sottoalbero destro. *

******************************************************************************/

TipoADTab
*ADTab_IndirizzoAlberoSinistro(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero restituisce l’indizzo al sottoalbero sinitro.*

******************************************************************************/

TipoADTab
*ADTab_IndirizzoAlberoDestro(TipoADTab);

/******************************************************************************

* Dato in input nodo
dell’albero restituisce l’indizzo al sottoalbero destro. *

******************************************************************************/

/********************* IMPLEMENTAZIONE DELLE FUNZIONI **********************/

void
ADTab_CreaAlbero(TipoADTab *tree)

{

*tree = NULL;

}

void ADTab_CancellaAlbero(TipoADTab
*tree)

{

if (*tree != NULL)

{

ADTab_CancellaAlbero(&((*tree)->sx));

ADTab_CancellaAlbero(&((*tree)->dx));

if ((*tree)->elemento !=
NULL)

{

free((*tree)->elemento);

}

free(*tree);

*tree = NULL;

}

}

void ADTab_CreaNodo(TipoADTab *tree)

{

*tree = (TipoADTab)
malloc(sizeof(tiponodo));

(*tree)->sx = NULL;

(*tree)->dx = NULL;

(*tree)->elemento = NULL;

}

void ADTab_InserisciKey(TipoADTab tree,tipochiave key)

{

tree->key = key;

}

void ADTab_InserisciElemento(TipoADTab
tree,tipoelemento elemento)

{

tree->elemento = (tipoelemento *)
malloc(sizeof(tipoelemento));

*(tree->elemento) = elemento;

}

tipochiave
ADTab_MostraKey(TipoADTab tree)

{

return tree->key;

}

tipoelemento ADTab_MostraElemento(TipoADTab
tree)

{

return
*(tree->elemento);

}

int
ADTab_AlberoVuoto(TipoADTab tree)

{

return tree == NULL;

}

TipoADTab
ADTab_AlberoSinistro(TipoADTab tree)

{

return tree->sx;

}

TipoADTab
ADTab_AlberoDestro(TipoADTab tree)

{

return tree->dx;

}

TipoADTab
*ADTab_IndirizzoAlberoSinistro(TipoADTab tree)

{

return &(tree->sx);

}

TipoADTab
*ADTab_IndirizzoAlberoDestro(TipoADTab tree)

{

return &(tree->dx);

}

A
usufruire di questo insieme di funzione è il main di valutatore.c che insieme
ad altre functions ci hanno permesso di assolvere al compito di questo software

valutatore.c

/******************************************************************************

* Esercizio di Laboratorio di Algoritmi e
Strutture Dati mod. A gr.2 *

*
*

* Realizzato da:
*

* Divisato Antonio 50/358
*

* Ferrara Francesco Saverio 566/811
*

* Liguori Vincenzo 408/301
*

*
*

******************************************************************************/

#include <stdio.h>

#include “ADTab.h”

#define MAXSTRINGA 80
/*massima lunghezza della stringa*/

#define MAXINT 3726
/*indicatore di errore*/

void leggistringa(char *str,
int *n)

{

/* funzione che si occupa di
leggere la stringa rapppresentante l’espressione

da valutare. La particolarità
di questa funzione sta nel fatto che al termine

della lettura sostituisce il
carattere di new line con quello terminatore.

Restituisce quindi la stringa
modificata in tal modo e la lunghezza effettiva,

cioè senza considerare il
carattere di terminazione
*/

*n = -1; /*
inizializzazione della variabile n */

do
/*inizio del ciclo di letture */

{

scanf(”%c”,&str[++(*n)]); /*lettura del carattere*/

} /* fine del ciclo quando si incontra il carattere di new
line “\n” oppure

si è superato il valore massimo della stringa consentito */

while ((str[*n] != ‘\n’) && (*n <
MAXSTRINGA));

/*sostituzione del carattere “\n” con il carattere
terminatore “\0″, e

decremento del valore di “n” per dare in output la
lunghezza effettiva

della stringa */

str[(*n)--] = ‘\0′;

}

int operatore(char *str, int low, int high)

{

/*In input prende una parte
della stringa compresa tra low e high e

restituisce in output
l’indice dell’operatore che deve essere prelevato

durante la costruzione
dell’albero. In caso di insuccesso da in output MAXINT*/

int i;

int indice_primario = MAXINT;

int parentesi_primario = MAXINT;

int parentesi_aperte = 0; /*all’inizio non ci sono parentesi
aperte*/

int cerca_indice_primario = 1; /*variabile booleana*/

/*Questo ciclo viene eseguito per tutta la lunghezza della
stringa, ma

si arresta se la variabile booleana cerca_indice_primario
viene posta a zero*/

for (i=low ; (i <= high) &&
(cerca_indice_primario) ; i++)

{

switch (str[i]) /*case del carattere
str[i]*/

{

case ‘+’:

case ‘-’: /*se è un + o un
-*/

/*se le
parentesi attuali dell’indice provvisorio sono >= delle

parentesi
attualmente aperte*/

if
(parentesi_primario >= parentesi_aperte)

{

indice_primario = i; /*imposta l’indice primario provvisorio*/

parentesi_primario = parentesi_aperte; /*aggiorna la variabile*/

}

break;
/*ferma il ciclo*/

case
‘*’:

case ‘/’: /*se è un * oppure
un /*/

if
(parentesi_primario >= parentesi_aperte)

{

if (parentesi_aperte < parentesi_primario)

{

indice_primario = i;

parentesi_primario = parentesi_aperte;

}

else

{

if ((str[indice_primario] != ‘+’) && (str[indice_primario] != ‘-’))

{

indice_primario = i;

parentesi_primario = parentesi_aperte;

}

}

}

break;

case ‘^’: /*se è
un’elevazione a potenza*/

if
(parentesi_primario >= parentesi_aperte)

{

if (parentesi_aperte < parentesi_primario)

{

indice_primario = i;

parentesi_primario = parentesi_aperte;

}

else

{

if ((str[indice_primario] != ‘+’) && (str[indice_primario] != ‘-’)

&& (str[indice_primario] != ‘*’) &&
(str[indice_primario] != ‘/’))

{

indice_primario = i;

parentesi_primario = parentesi_aperte;

}

}

}

break;

case ‘(’: /*se trova una
parentesi aperta*/

parentesi_aperte++; /*incrementa il numero di parentesi aperte*/

break;

case ‘)’: /*se trova una
parentesi chiusa*/

parentesi_aperte–;
/*decrementa il numero di parentesi aperte*/

break;

}

}

return indice_primario; /*ritorna l’indice dell’operatore
scelto*/

}

int cifra(char *str, int low, int high)

{

/* Questa function riceve in
input una parte della stringa(espressione inserita)

compresa tra gli indici
definiti da low e high e restituisce in output l’intero

in essa contenuto se è
presente altrimenti l’indicatore d’errore MAXINT */

int i;

int flag=0; /*variabile d’appoggio*/

int numero=0; /*inizializzo a 0 il valore di
ritorno della function*/

for (i=low ; i <= high ; i++)

{

if ((str[i] >= ‘0′) && (str[i] <=
‘9′)) /*se è un numero*/

{

flag = 1; /*indica che nella stringa in esame è
contenuto un numero*/

numero = (numero*10) + (str[i]-’0′);
/*registra il numero*/

}

}

if (flag)
/*se il numero è stato memorizzato*/

return numero;
/*ritorna il numero*/

else

return MAXINT; /*altrimenti
ritorna un indicatore di errore*/

}

int tiposegno(char *str,int
i)

{

/* Dato in input l’operatore
memorizzato in str[i] viene restituito
in output

l’intero ad esso relativo */

int primario; /*variabile di return */

switch (str[i]) /* utilizzando lo switch

se l’operatore in questione è:
*/

{

case ‘+’: /* il + allora primario
assumerà valore 1*/

primario = 1;

break;

case ‘-’: /* il – allora primario
assumerà valore 2*/

primario = 2;

break;

case ‘*’: /* il * allora primario
assumerà valore 3*/

primario = 3;

break;

case ‘/’: /* il / allora primario
assumerà valore 4*/

primario = 4;

break;

case ‘^’: /* il ^ allora primario
assumerà valore 5*/

primario = 5;

break;

}

return primario;
/* valore di return */

}

int esamina(char *str,int low,int high, int *i, int *primario, int
*numero)

{

/* la function
“esamina” riceve in input una parte della stringa compresa

tra i parametri-indice low e
high, e serve a stabilire se si deve o meno

inserire un elemento
nell’albero. Infatti questa funzione restituirà in

output 1 se è stato trovato
un elemento da inserire nell’albero, in caso

contrario restituirà 0. Da
notare che in caso di successo (return 1) si hanno

dua casi: se primario=0
allora nella variabile “numero” ci sarà il numero da

registrare nell’albero; se
invece primario ha un valore compreso tra 1 e 5

allora tale valore indicherà
quale operatore specifico dovrà essere

registrato nel nostro
albero.*/

if (low <= high) /*costrutto di controllo sui parametri-indice*/

{

*i = operatore(str,low,high); /*riconosco
l’operatore con l’omonima

function */

if (*i == MAXINT) /*se la funzione operatore()
ha restituito MAXINT*/

{
/*vorrà dire che non è stato individuato un operatore*/

*numero = cifra(str, low, high);
/*controlla la presenza di un numero*/

if (*numero == MAXINT) /*se la
funzione “cifra” restituisce MAXINT*/

{

return 0; /*ritorno un
indicatore di errore*/

}

else /*altrimenti vorrà dire che si è trovato un numero e
ciò viene */

{ /*indicato ponendo primario = 0 */

*primario = 0;

}

}

else /*se invece è stato trovato un operatore in
str[i]*/

{

*primario = tiposegno(str,*i);
/*registro nella variabile primario

il valore indicante tale operatore*/

}

return 1; /*ritorno un indicatore di successo*/

}

else

{

return 0; /*ritorno un indicatore di errore*/

}

}

void maketree(TipoADTab *tree,char *str,int low,int high)

{

/*Questa funzione ricorsiva
costruisce l’albero da valutare. A tale scopo

riceve in input i
parametri-indice della stringa e la stringa stessa e fa uso

di alcune function della
libreria “ADTab.h” a cui passerà il puntatore tree

all’albero anch’esso ricevuto
in input */

int j;

int primario = -1; /*inizializzazione di primario */

int numero = MAXINT; /*inizializzazione numero
all’indicatore d’errore*/

if (low <= high) /*se ci sono ancora caratteri nella
stringa*/

{

/*esamino la stringa con la funzione
“esamina” */

if (esamina(str,low,high,&j,&primario,&numero))

{

/*se è stato trovato qualcosa da
registrare*/

ADTab_CreaNodo(tree);
/*alloco la memoria*/

ADTab_InserisciKey(*tree,primario); /*registro la key*/

ADTab_InserisciElemento(*tree,numero); /*registro l’elemento*/

if (j != MAXINT) /*e se è stato
trovato un operatore*/

{

/*esamino ricorsivamente
l’albero sinistro e l’albero destro*/

maketree(ADTab_IndirizzoAlberoSinistro(*tree),str,low,j-1);

maketree(ADTab_IndirizzoAlberoDestro(*tree),str,j+1,high);

}

}

}

}

void leggitree1(TipoADTab tree)

{

/*questa void effetta la
lettura dell’albero SIMMETRICA*/

int key;

if (!ADTab_AlberoVuoto(tree)) /*controllo che l’albero non
sia vuoto*/

{

/* ricorsione sul sottoalbero sinistro */

leggitree1(ADTab_AlberoSinistro(tree));

key = ADTab_MostraKey(tree); /* se il campo key
da stampare è diverso

da zero vuol dire che c’è un operatore

che individueremo conoscendo il
valore di

key*/

if (key!=0)

{

switch (key) {

case 1:

printf(” + “);

break;

case 2:

printf(” – “);

break;

case 3:

printf(” * “);

break;

case 4:

printf(” / “);

break;

case 5:

printf(” ^ “);

break;

}

}

else

{

/* stampa del numero relativo
a ciascun nodo */

printf(” %d
“,ADTab_MostraElemento(tree));

}

/* ricorsione sul sottoalbero destro */

leggitree1(ADTab_AlberoDestro(tree));

}

}

void leggitree2(TipoADTab tree)

{

/*questa void effetta la
lettura dell’albero ANTICIPATA*/

int key;

if (!ADTab_AlberoVuoto(tree)) /*controllo che l’albero non
sia vuoto*/

{

/* ricorsione sul sottoalbero sinistro */

leggitree2(ADTab_AlberoSinistro(tree));

/* ricorsione sul sottoalbero destro */

leggitree2(ADTab_AlberoDestro(tree));

key = ADTab_MostraKey(tree);

/* se il campo key da
stampare è diverso da zero vuol dire che c’è un

operatore che individueremo conoscendo il valore
di key*/

if (key!=0)

{

switch (key) {

case 1:

printf(” + “);

break;

case 2:

printf(” – “);

break;

case 3:

printf(” * “);

break;

case 4:

printf(” / “);

break;

case 5:

printf(” ^ “);

break;

}

}

else

{

/* stampa del numero relativo
a ciascun nodo */

printf(” %d
“,ADTab_MostraElemento(tree));

}

}

}

void leggitree3(TipoADTab tree)

{

/*questa void effetta la
lettura dell’albero ANTICIPATA*/

int key;

if (!ADTab_AlberoVuoto(tree)) /*controllo che l’albero non
sia vuoto*/

{

key =
ADTab_MostraKey(tree);

/* se il campo key da
stampare è diverso da zero vuol dire che c’è un

operatore che individueremo conoscendo il valore
di key*/

if (key!=0)

{

switch
(key) {

case 1:

printf(” + “);

break;

case 2:

printf(” – “);

break;

case 3:

printf(” * “);

break;

case 4:

printf(” / “);

break;

case 5:

printf(” ^ “);

break;

}

}

else

{

/* stampa del numero relativo a
ciascun nodo */

printf(” %d
“,ADTab_MostraElemento(tree));

}

/* ricorsione sul sottoalbero sinistro */

leggitree3(ADTab_AlberoSinistro(tree));

/* ricorsione sul sottoalbero destro */

leggitree3(ADTab_AlberoDestro(tree));

}

}

int valutatree(TipoADTab
tree)

{

/*Come si comprende
facilmente dal nome. questa funzione valuta l’albero e

ritorna in output il valore
dell’espressione in esso memorizzata. E’ in

pratica il gestore di tutte
le function indispensabili alla implementazione

di questo valutatore di
espressioni*/

int i;

int valore_sx=MAXINT;
/* inizializzo all’idicatore di errore*/

int valore_dx=MAXINT;
/* sia valore_sx che valore_dx */

int valore_di_ritorno = 1;

if (!ADTab_AlberoVuoto(tree)) /*se l’albero non è vuoto*/

{

if(ADTab_MostraKey(tree) == 0) /*se nel nodo è
registrato un numero*/

{

return
ADTab_MostraElemento(tree);/*ritorno il numero in esso registrato*/

}

else

{

/*nel nodo è registrato un
operatore*/

switch
(ADTab_MostraKey(tree)) {

case 1: /* se è l’operatore di
addizione */

return
valutatree(ADTab_AlberoSinistro(tree)) + valutatree(ADTab_AlberoDestro(tree));

case 2: /* se è l’operatore di
sottrazione */

valore_sx =
valutatree(ADTab_AlberoSinistro(tree));

if (valore_sx != MAXINT)/*se
il – non è inteso come operatore unario*/

{

return valore_sx – valutatree(ADTab_AlberoDestro(tree));

}

else

{ /*se
invece il – è inteso come operatore unario*/

return 0 – valutatree(ADTab_AlberoDestro(tree));

}

case 3: /* se è l’operatore di moltiplicazione */

return
valutatree(ADTab_AlberoSinistro(tree)) * valutatree(ADTab_AlberoDestro(tree));

case 4: /* se è l’operatore di
divisione */

return
valutatree(ADTab_AlberoSinistro(tree)) / valutatree(ADTab_AlberoDestro(tree));

case 5: /* se è un’elevazione a
potenza*/

valore_sx =
valutatree(ADTab_AlberoSinistro(tree));

valore_dx =
valutatree(ADTab_AlberoDestro(tree));

/*questo
ciclo calcola il valore dell’elevazione a potenza*/

for (i=0 ;
i<valore_dx ; i++)

{

valore_di_ritorno = valore_di_ritorno * valore_sx;

}

return valore_di_ritorno; /* valore
dell’elevazione a potenza*/

}

}

}

else

{

return MAXINT; /*ritorna un indicatore di
errore*/

}

}

main()

{

char str[MAXSTRINGA]; /*dichiara la stringa di lunghezza
MAXSTRINGA*/

int n; /*dichiara l’intero contenente la dimensione
effettiva della stringa*/

TipoADTab tree; /*dichiarazione dell’albero*/

printf(”*****************************************************\n”);

printf(”*ESERCIZIO di Lab. ALGORITMI E STRUTTURE DATI
mod. A*\n”);

printf(”*
Divisato Antonio 50/358
*\n”);

printf(”* Ferrara Francesco
Saverio 566/811 *\n”);

printf(”*
Liguori Vincenzo 408/301
*\n”);

printf(”*****************************************************\n”);

printf(”\n”);

printf(”N.B.:\n”);

printf(”-e’ permesso l’uso di parentesi
tonde;\n”);

printf(”-i numeri negativi devono essere inseriti tra
parentesi:\n”);

printf(” esempio: scorretto 5+ -3; corretto
5+(-3).\n”);

printf(”\n\nOperazioni permesse:\n”);

printf(” +
–> addizzione\n”);

printf(” -
–>
sottrazione\n”);

printf(” *
–>
moltiplicazione\n”);

printf(” /
–> divisione\n”);

printf(” ^
–> elevazione a
potenza\n”);

printf(”\n”);

ADTab_CreaAlbero(&tree); /*crea l’albero*/

printf(”Inserire l’espressione da valutare:”);

leggistringa(str,&n); /*legge la stringa*/

maketree(&tree,str,0,n);

printf(”\nLETTURA
SIMMETRICA (sx-c-dx) -> “);

leggitree1(tree); /*legge l’albero*/

printf(”\nLETTURA ANTICIPATA (sx-dx-c) -> “);

leggitree2(tree); /*legge l’albero */

printf(”\nLETTURA DIFFERITA (c-sx-dx) -> “);

leggitree3(tree); /*legge l’albero*/

printf(”\n\n”);

n = valutatree(tree); /*valuta l’albero e registra il
risultato in n*/

printf(”Il risultato e’ %d\n\n”,n);

ADTab_CancellaAlbero(&tree); /*cancella l’albero per
liberare memoria*/

getchar();

}