Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2021-22 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2021-22 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

VIDEOLEZIONI DEL CORSO DI FONDAMENTI DI PROGRAMMAZIONE AA20-21

PROGRAMMING COURSE VIDEOCONFERENCES AY20-21

[AVVISO] Homework 3 - calcolo di espressioni aritmetiche - entro domenica 13 maggio [DEFINITIVO]

andrea.sterbini (173640 points)
516 941 1795
in Homework 3 by (174k points)
closed by

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

1.4k views
closed with the note: test aggiunti

1 Answer

V
Valerio.Pescatori (1940 points)
6 25 38
by (1.9k points)
In generale un nodo può avere o 2 o 0 figli giusto? Non può esistere un caso in cui un nodo abbia 1 solo figlio o sbaglio?
andrea.sterbini (173640 points)
516 941 1795
by (174k points)
Esatto, dato che non ci sono operatori unari i nodi interni hanno sempre entrambi i figli