[10/06/2011]
Esecizio: Data una stringa s che contiene una espressione aritmentica, scrivere una funzione
char *toPol(char *s)
che converte tale espressione in un espressione in notazione polacca inversa. Utilizzare come struttura dati per la conversione una pila (stack).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#define MAX 100
int top = 0;
char stack[MAX];
char pop(void) { if (top!=0) return stack[--top]; }
void push(char a) { if (top==MAX) exit(1); else stack[top++] = a; }
char readtop(void) { if (top==0) return ' '; return stack[top-1]; }
bool empty(void) { return (top==0); }
int priority(char s)
{
int p = 0;
if (s == ' ') return s;
switch(s) {
case '*': case '/': p=2; break;
case '+': case '-': p=1; break;
case '(': case ')': p=0; break;
default: exit(1);
}
return p;
}
char *toPol(char *s)
{
char c;
int len = strlen(s);
char *result = (char *) malloc(sizeof(char)*(len+1));
int j = 0;
for (int i=0; i<len; i++)
{
switch(s[i]) {
case '(': push(s[i]); break;
case ')':
while ((c = pop()) != '(')
{
result[j++] = c;
} break;
case '-': case '*': case '/': case '+':
while (priority( (c=readtop()) ) >= priority(s[i]))
result[j++] = pop();
push(s[i]);
break;
default:
if (isdigit(s[i])) result[j++] = s[i];
}
}
while (!empty()) result[j++] = pop();
result[j] = ' ';
return result;
}
int main(int argc, char *argv[])
{
char s[] = "3+4*(5-2)+7*(4+2)/3";
char *v = toPol(s);
printf("%sn",v); free(v);
return 0;
}
Modificare il codice sopra, prima di tutto estendere la funzione che riconosce i numeri in modo da farla funzionare anche con numeri e non con singole cifre, poi 1) Invece di costruire la stringa in notazione polacca inversa, è possibile usare gli stack in modo da “valutare” direttamente l’espressione data nella stringa. 2) oppure: invece di costruire una stringa, costruire un albero che rappresenta l’espressione, in questo albero i nodi foglia sono le costanti e i nodi interni sono gli operandi, la struttura dell’albero riflette l’ordine con cui si valuta l’espressione. Scrivere 1) una funzione che dato l’albero stampa l’espressione contenuta, 2) la valuta, 3) stampa una sequenza di operazioni in Assembly 68000 che calcolano l’espressione, per poter svolgere il punto 3, gestire in modo opportuno l’uso dei registri del processore.