Homework 4 - calcolo di una espressione aritmetica con parentesi

Si vuole realizzare una calcolatrice che possa ricevere come input una espressione aritmetica in notazione infissa (con parentesi). Ad esempio deve poter calcolare una espressione come ( < 32 - [ 17 * ( [ 12 / 4 ] + < 1 / 11 > ) ] > / { [ 42 * 3 ] - 1 } ) e stamparne il risultato (circa −0.164363636) con la normale precisione della syscall print float

ATTENZIONE: sono previsti due livelli di difficoltà dell'esercizio

• esercizio completo: 1 punto
• esercizio semplificato: 0.5 punti
  • senza caratteri spuri dopo l'espressione
  • con le sole parentesi quadre
  • senza caratteri da ignorare (solo cifre, parentesi quadre e operatori)
  • con espressioni SEMPRE corrette (nessuna gestione degli errori)

Per riuscirci bisogna realizzare un programma ricorsivo oppure manipolare una stack.

• l'espressione è su una sola riga ed è lunga al massimo 1000 caratteri
• eventuali spazi o caratteri diversi dalle parentesi, cifre e operatori possono essere ignorati
• le operazioni ammesse sono solo le 4 operazioni aritmetiche, indicate dai caratteri +*/-
• per evitare ambiguità tra i numeri negativi e l'operazione -, tutti i numeri in input saranno interi e non negativi
• è comunque necessario manipolare internamente numeri in virgola mobile a 32 bit (non usate i double)
  • per convertire una word (intero) in un numero in virgola mobile si usano le due istruzioni:

    mtc1 $s0, $f0	move to coprocessor 1 (il valore intero codificato in complemento a 2)
    cvt.s.w $f0, $f0	convert from word to simple precision (da CA2 a virgola mobile)

  • una volta convertito il numero in virgola mobile potete riportarlo avanti e indietro dal coprocessore matematico senza doverlo ri-convertire
• per semplicità non bisogna gestire la precedenza degli operatori prodotto e divisione rispetto a somma e sottrazione (quindi una espressione corretta conterrà sempre tutte le parentesi necessarie a disambiguare le precedenze, come si vede nell'esempio sopra, oppure dovete dare errore)
• le parentesi utilizzabili sono i caratteri: <>[]{}() che vanno accoppiati correttamente

La sintassi dell'espressione (versione completa) si basa sulle seguenti regole grammaticali:

• espressione := carattere_da_ignorare espressione
• espressione := numero intero non negativo
• espressione := espressione carattere_da_ignorare
• espressione := (espressione operatore espressione)
• espressione := [espressione operatore espressione]
• espressione := {espressione operatore espressione}
• espressione := <espressione operatore espressione>
• operatore := +|-|*|/
• carattere_da_ignorare := tutti i caratteri diversi dagli operatori, parentesi e cifre

La sintassi dell'espressione nella versione semplificata è:

• espressione := numero intero non negativo
• espressione := [espressione operatore espressione]
• operatore := +|-|*|/

Come vedete la maggior parte delle regole della grammatica si distinguono per il primo o per l'ultimo carattere, quindi non è difficile definire le regole ricorsive che gli corrispondono.

Consigli

Realizzate prima il programma in un linguaggio di alto livello

Mentre riconoscete una espressione potete trovarvi nelle seguenti situazioni:

• avete letto una cifra -> state riconoscendo un numero
• state riconoscendo un numero e avete letto un carattere diverso da una cifra -> l'espressione è completa
• avete letto una parentesi aperta -> state riconoscendo una espressione, vi aspettate la prima espressione
• avete letto la prima espressione -> vi aspettate l'operatore
• avete letto l'operatore -> vi aspettate la seconda espressione
• avete letto la seconda espressione -> vi aspettate la parentesi chiusa e potete calcolare l'operazione indicata dall'operatore
• avete finito di leggere l'espressione più esterna -> non vi aspettate altri caratteri

Per controllare se la parentesi chusa corrisponde alla parentesi aperta dovete ricordare su stack quale parentesi era stata aperta

Per calcolare l'operazione, cosa che potete fare DOPO che avete letto la seconda espressione, dovete ricordare su stack qual'era l'operatore

Non è necessario ricordare la struttura completa di una espressione per calcolare una espressione che la contiene, basta calcolarne il valore quando si chiude la parentesi e usarlo successivamente per il calcolo della espressione che la contiene. Quindi su stack per ogni chiamata basta mettere:

• tutti i registri che modificate
• la parentesi aperta (per controllarla con quella chiusa)
• il valore della prima sub-espressione (per svolgere l'operazione)
• l'operatore (per sapere che operazione svolgere tra i due valori delle due sub-espressioni)

Gestione degli errori (solo per la versione completa dell'esercizio)

Ignorate tutti i caratteri diversi da cifre, parentesi e operatori

Gli unici errori che dovrebbero presentarsi sono:

• errore di sintassi della espressione: dovete stampare SOLO uno dei seguenti messaggi (seguito da accapo):
  • quando ci si aspetta una parentesi chiusa e invece viene qualcos'altro: (numero o operatore o parentesi aperta)
    • "MANCA LA PARENTESI CHIUSA " seguito dal carattere mancante
  • quando ci si aspetta una espressione e invece viene qualcos'altro: (parentesi chiusa o operatore)
    • "MANCA UNA PARENTESI APERTA O UN NUMERO"
  • quando ci si aspetta un operatore e invece viene qualcos'altro: (parentesi chiusa o numero o parentesi aperta)
    • "MANCA UN OPERATORE"
  • quando l'espressione è finita ma è seguita, (a parte eventuali caratteri da ignorare) da operatori o cifre o parentesi: (NEW)
    • "CARATTERI SPURI DOPO L'ESPRESSIONE"
  • (spero di aver elencato tutti gli errori possibili, casomai suggerite altri casi)
    • per il momento genererò dei file che contengono solo espressioni corrette
    • poi dopo qualche giorno aggiungerò file di test con espressioni NON corrette

• La divisione per zero in virgola mobile non produce eccezioni ma può dare i risultati speciali:
  • 0/0=NaN (not a number)
  • N/0=Infinity
  • -N/0=-Infinity
• che saranno propagati dal calcolo correttamente (e che stamperete con print float)

Consegna entro le ore 24 di lunedì 25 maggio

La pagina di consegna è pronta.

Tests e risultati

Cominciano ad arrivare i primi compiti ...

Ho definito qualche test iniziale, appena posso ne aggiungo altri:

• divisioni per zero
• espressioni errate semplici
• espressioni corrette generate a caso
• espressioni errate generate a caso

-- AndreaSterbini - 07 May 2015