Programmazione 1    (P-Z) a.a. 2007-08

Data la struttura:

 
struct typedef { 
      int seq; 
      double value; 
} Element; 

Considerare una struttura dati a coda (Queue) di dimensioni limitate (es. 10) che contiene elementi di tipo Element. Il campo seq di Element contiene un valore sequenziale che viene incrementato ogni volta che viene creato un nuovo elemento; il campo value contiene un valore reale casuale.
La struttura Queue è caratterizzata dal permettere l'inserimento in fondo e l'eliminazione in testa. Implementare le due funzioni di enqueue(), che permette di inserire un nuovo elemento solo se Queue non è piena, e dequeue(), che permette l'estrazione di un elemento da Queue solo se questa non è vuota.
Integrare le funzioni in un programma in cui si eseguono sequenze casuali di enqueue e dequeue.
Consiglio: definire le funzioni enqueue() e dequeue() nel modo seguente:
void enqueue(Queue **, double);
double dequeue(Queue **);

Date due liste concatenate A e B, contenenti elementi di tipo Element (vedi esercizio precedente), implementare la funzione merge che prende in input le due liste e restituisce la lista concatenata ordinata sul campo seq, risultante dall'unione delle due stringhe.
La funzione deve essere implementata in modo che ad ogni sua esecuzione, soltanto un nuovo elemento (non già presente) viene aggiunto nella lista ordinata, mentre i parametri di merge sono sempre i puntatori al primo elemento di A e B.

Data l'espressione numerica in notazione infissa Infix = (6 + 2) * 5 - 8 / 4 (con gli operatori al centro degli operandi) la corrispondente espressione numerica in notazione postfissa è Postfix = 6 2 + 5 * 8 4 / - (con gli operatori che seguono gli operandi). Scrivere un programma che legge in input da prompt dei comandi un'espressione numerica in notazione infissa con numeri interi ad una cifra, e restituisce la stessa espressione numerica in notazione postfissa. Il programma deve utilizzare due liste concatenate di caratteri (char), una per l'espressione in forma infissa ed una per l'espressione in notazione postfissa, ed inoltre si richiede di utilizzare uno stack degli operandi (Stack) in cui è possibile operare attraverso le funzioni push() e pop() viste nella scorsa esercitazione.
L'algoritmo per la costruzione della notazione postfissa è di seguito descritto:

1)    Inserire un simbolo '(' in cima allo Stack.
2)    Inserire un simbolo ')' alla fine di Infix.
3)    Finchè Stack non è vuoto, leggere Infix da sinistra verso destra, e:
3.1)    Se il carattere corrente di Infix è un numero, copiarlo nell'elemento successivo di Postifx.
3.2)    Se il carattere corrente di Infix è '(', eseguire un push() in Stack.
3.3)    Se il carattere corrente di Infix è un operatore:
3.3.1)    Eseguire un pop() degli operatori in Stack finchè questi hanno precedenza maggiore o uguale 
          all'operatore corrente, e copiarli in Postfix.
3.3.2)    Eseguire un push() dell'operatore corrente in Stack.
3.4)    Se il carattere corrente di Infix è ')':
3.4.1)    Eseguire un pop() degli operatori in Stack ed inserirli in Postfix, finchè un '(' 
          resta in cima allo Stack.
	  Eseguire un pop() e scartare il simbolo '(' dallo Stack.

La lista concatenata Postfix cresce mano mano che vengono letti gli operandi in Infix e gli operatori vengono rimossi dallo stack.
Supponiamo inoltre che gli operatori possibili siano: +, -, * e /, e che le precedenze siano rispettivamente 1, 1, 2 e 2.

Nota: riassumendo quanto visto precedentemente, lo Stack può essere implementato attraverso la lista concatenata seguente:

typedef struct stackNode {
  char data;
  struct stackNode* next;
} Stack;

Mentre le operazioni di push() e di pop(), permettono rispettivamente di inserire un elemento in cima, e di eliminare l'elemento dalla cima di una lista concatenata.

Consiglio: utilizzare le funzioni così definite:

void push(Stack **head, char s);
char pop(Stack **head);