Homework 3 - calcolo di una espressione aritmetica contenuta in un albero binario
Si supponga di avere un albero binario che rappresenta una espressione aritmetica in cui:
- le foglie sono numeri interi
- i nodi intermedi sono i 4 operatori aritmetici (* + - ^) rappresentati rispettivamente dai valori -1 -2, -3, -4
NOTA: "^" è la potenza intera in cui il secondo argomento (esponente) va preso in valore assoluto, quindi sempre positivo
L'albero che rappresenta l'espressione è codificato sotto forma di vettore di interi, con le convenzioni che:
- nella posizione 0 è contenuto il numero N di elementi dell'albero (quindi il vettore ha N+1 elementi)
- la radice si trova all'indice 1
- i due nodi figli del nodo che sta in posizione X sono
- sinistro in posizione 2X
- destro in posizione 2X+1
- tutti i nodi che non contengono alcun valore sono marcati dal valore speciale -666
NOTA: quindi un nodo in posizione X è foglia se entrambi i figli sono vuoti o non esistono, ovvero valgono -666 oppure si trovano in posizione 2X>N oppure 2X+1>N
NOTA: le foglie possono contenere qualsiasi valore tranne -666, quindi assumete che il valore -666 non appaia mai come valore di un nodo interno (-1,-2,-3,-4) o di una foglia. Farò in modo che i test non producano mai il valore -666 come valore intermedio
NOTA: una foglia può contenere i valori -1,-2,-3,-4 (bisogna vedere che non abbia figli)
Funzione ricorsiva 1: stampare l'espressione aritmetica
Dato l'indirizzo del vettore stampare l'espressione aritmetica corrispondente usando le parentesi tonde per ogni nodo, seguita da accapo ('\n')
NOTA: circondate di parentesi tonde anche i valori per evitare ambiguità con i segni
Esempio: se l'albero è
* / \ + - / \ / \ 3 * 7 - / \ / \ 5 8 6 9
Che è codificato col vettore 15, -1, -2, -3, 3, -1, 7, -3, -666, -666, 5, 8, -666, -666, 6, 9
ovvero 15, *, +, -, 3, *, 7, -, VUOTO, VUOTO, 5, 8, VUOTO, VUOTO, 6, 9
L'espressione da stampare è
(((3)+((5)*(8)))*((7)-((6)-(9))))
Funzione ricorsiva 2: svolgere un passo dei calcoli modificando il vettore/albero
Dato l'indirizzo del vettore che codifica l'albero di una espressione, semplificare l'espressione sostituendo tutti gli operatori che hanno solo figli numerici (foglie) con il corrispondente risultato (e mettere -666 nei figli per annullarli)
Esempio: se l'albero è quello dell'esempio precedente, il risultato dev'essere l'albero
* / \ + - / \ / \ 3 40 7 -3
Che è codificato col vettore 15, -1, -2, -3, 3, 40, 7, -3, -666, -666, -666, -666, -666, -666, -666, -666
ovvero 15, *, +, -, 3, 40, 7, -3, VUOTO, VUOTO, VUOTO, VUOTO, VUOTO, VUOTO, VUOTO, VUOTO
(o con il vettore più piccolo 7, -1, -2, -3, 3, 40, 7, -3 se preferite)
Se si usa la funzione 1 per stampare questa espressione si ottiene
(((3)+(40))*((7)-(-3)))
Programma da realizzare:
Scrivete il programma ASM che:
1) definisce le funzioni ricorsive 1 e 2 e tutte le altre funzioni che ritenete necessarie
2) definisce la procedura main che:
- legge il valore N < 1000 e lo memorizza nella posizione 0 di un vettore
- legge i successivi N elementi e li memorizza nelle posizioni 1..N del vettore
- stampa l'espressione seguita da accapo usando la Funzione ricorsiva 1 e passandole l'indirizzo del vettore
- ripete finchè l'albero non si è ridotto ad un solo nodo (numerico)
- esegue un passo di semplificazione usando la Funzione ricorsiva 2 e passandole l'indirizzo del vettore
- stampa l'espressione seguita da accapo usando la Funzione ricorsiva 1 e passandole l'indirizzo del vettore
- termina
Esempio di input/output
Se l'input è quello dell'esempio precedente ovvero i valori (commentati, nei test non ci saranno commenti)
15 # N, numero di elementi dell'albero da leggere -1 # operatore *, radice dell'albero -2 # operatore + -3 # operatore - 3 # valore foglia 3 -1 # operatore * 7 # valore foglia 7 -3 # operatore - -666 # nodo vuoto -666 # nodo vuoto 5 # valore foglia 5 8 # valore foglia 8 -666 # nodo vuoto -666 # nodo vuoto 6 # valore foglia 6 9 # valore foglia 9
L'output sarà
(((3)+((5)*(8)))*((7)-((6)-(9)))) (((3)+(40))*((7)-(-3))) ((43)*(10)) (430)
Consegna entro le ore 24 di domenica 13 maggio
La consegna dello Homework 3 è attiva.
Trovate i risultati dei test ed i file di test su http://twiki.di.uniroma1.it/twiki/view/Architetture2/MZ/AA17_18/HomeWork3