Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2023-24 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 2023-24 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.

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

andrea.sterbini (207920 points)
750 1267 2373
in Homework 3 by (208k 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.6k views
closed with the note: test aggiunti

1 Answer

V
Valerio.Pescatori (1940 points)
11 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 (207920 points)
750 1267 2373
by (208k points)
Esatto, dato che non ci sono operatori unari i nodi interni hanno sempre entrambi i figli