[Assembler]Esercizio

[mrborel]

Devo fare un'esercizio di assembler per un'esame...Mi servirebbe una mano!!Questo è quello che devo fare:

Uno dei problemi classici dell'informatica è la risoluzione di semplici espressioni come, ad esempio:
((10-5)+((8-2)-(3+4))).
Infatti, la presenza di parentesi complica la risoluzione costringendo al calcolo e alla relativa memorizzazione di risultati parziali.
La risoluzione di espressioni di questo tipo risulta più semplice se le si scrive in notazione polacca inversa che non richiede l'utilizzo di parentesi. Nel caso visto in precedenza:
10 5 - 8 2 - 3 4 + - + .

Esercizio:
scrivere un programma assembly che prende in ingresso espressioni e le traduca in notazione polacca inversa.
Si ipotizzi che le espressioni non contengano numeri negativi e che le sole operazioni siano la somma (+) e la sottrazione (-).
Successivamente implementare anche il calcolo del risultato ipotizzando che i numeri e i risultato (anche parziali) abbiano al più 2 cifre.

Suggerimento:
La trasformazione di un espressione in notazione polacca inversa si può facilmente implementare mediante l'utilizzo dello stack. Occorre scandire l'espressione da sinistra a destra e stampare (o memorizzare) i numeri che si incontrano. Quando si incontra una operazione questa va posta sullo stack. Viceversa, nel caso si arrivi ad una parentesi chiusa occorre prelevare l'operazione che si trova nello stack e stamparla.
Analogamente, anche il calcolo del risultato a partire dalla notazione polacca inversa si può implementare sfruttando lo stack. Anche in questo caso occorre scandire l'espressione da sinistra a destra e porre eventuali numeri che si incontrano sullo stack. Quando si arriva ad una operazione occorre prelevare i due numeri in cima allo stack, effetture il calcolo e riporre il risultato sullo stack.
Al termine il risultato si troverà in cima allo stack.

Esempio:

introdurre un espressione: ((10-5)+((8-2)-(3+4)))
notazione inversa: 10 5 - 8 2 - 3 4 + - +
risultato: 4

La CPU è 8086 ed il tipo di assemblatore è Intel x86(diciamo il classico assembler,quello più comune)
Cordiali saluti, spero riusciate ad aiutarmi!!!

[cionci]

Ma tu per adesso cosa hai scritto ? Dove trovi difficoltà ?

[StateCity]

e' semplice : http://en.wikipedia.org/wiki/Reverse_Polish_notation
(ci sono anche gli esempi...)
Poi siccome i numeri sono al piu' di 2 cifre, si rientra comodamente nel Byte singolo.
Forse forse l'unico vero problema sara' la tokenizzazione dei simboli,
cioe' nn si deve scabiare l'ascii del + con il valore numerico della cifra..

[StateCity]

in linea generale l'algoritmo e' tipo questo:
http://sourcecode99.blogspot.com/200...tation-to.html

Esempio : 3 − 4 + 5 -------- diventa nella pila (stack) LIFO in notazione postfissa --------> 3 4 − 5 +

si elabora in 3 4 - = -1 la pila diventa -1 5 +

si elabora in -1 5 + = 4 la pila diventa 4

Link molto utili :
http://www.spsu.edu/cs/faculty/bbrow...tures/postfix/
http://home.att.net/~srschmitt/reversepolish.html


POP PUSH ecc. ecc.

bye

[Vincenzo1968]

Originariamente inviato da mrborel

...
Esempio:

introdurre un espressione: ((10-5)+((8-2)-(3+4)))
notazione inversa: 10 5 - 8 2 - 3 4 + - +
risultato: 4

La CPU è 8086 ed il tipo di assemblatore è Intel x86(diciamo il classico assembler,quello più comune)
Cordiali saluti, spero riusciate ad aiutarmi!!!

Vediamo, applicando l'algoritmo passo passo, come si arriva al risultato dell'esempio.

Parte I: da notazione infissa a notazione RPN

Il primo token nella stringa di input è una parentesi di apertura. La inseriamo in cima allo stack:

STACK : (
OUTPUT:

Il secondo token è, nuovamante una parentesi di apertura. Va inserita in cima allo stack:

STACK : ( (
OUTPUT:

Il terzo token è il numero 10. Va inserito nella stringa di output:

STACK : ( (
OUTPUT: 10

Il token successivo è l'operatore '-'. Poiché l'operatore in cima allo stack(la parentesi di apertura) ha precedenza minore rispetto al segno meno, inseriamo quest'ultimo in cima allo stack:

STACK : ( ( -
OUTPUT: 10

Il token successivo è il numero 5. Va inserito alla fine della stringa di output:

STACK : ( ( -
OUTPUT: 10 5

Il token successivo è la parentesi di apertura. In questo caso bisogna estrarre tutti gli operatori dallo stack finché non si incontra una parentesi di apertura. Ogni operatore estratto va piazzato alla fine della stringa di output. Le due parentesi vanno scartate. La situazione, dopo l'applicazionme delle operazioni suddette, è la seguente:

STACK : (
OUTPUT: 10 5 -

Il token successivo è l'operatore '+'. Questo ha precedenza maggiore rispetto all'operatore che si trova in cima allo stack e, dunque, va inserito in cima allo stack:

STACK : ( +
OUTPUT: 10 5 -

I due token successivi sono parentesi di apertura. Vanno inserite in cima allo stack:

STACK : ( + ( (
OUTPUT: 10 5 -

Il token successivo, il numero 8, va alla fine della stringa di output:

STACK : ( + ( (
OUTPUT: 10 5 - 8

Il token successivo, l'operatore '-' ha precedenza maggiore rispetto a quello che si trova in cima allo stack e va, dunque, inserito in cima allo stack:

STACK : ( + ( ( -
OUTPUT: 10 5 - 8

Il token successivo, il numero 2, va alla fine della stringa di output:

STACK : ( + ( ( -
OUTPUT: 10 5 - 8 2

Il token successivo è la parentesi di apertura. Ogni operatore va estratto dallo stack e aggiunto alla fine della stringa di output finché la cima dello stack non contiene una parentesi di apertura(cha va estratta dallo stack e scartata insieme a quella di chiusura):

STACK : ( + (
OUTPUT: 10 5 - 8 2 -

Il token successivo, l'operatore '-', ha precedenza maggiore rispetto a quello in cima allo stack. Va aggiunto in cima:

STACK : ( + ( -
OUTPUT: 10 5 - 8 2 -

Il token successivo, la parentesi di apertura, va in cima allo stack:

STACK : ( + ( - (
OUTPUT: 10 5 - 8 2 -

Il token successivo, il numero 3, va aggiunto alla stringa di output:

STACK : ( + ( - (
OUTPUT: 10 5 - 8 2 - 3

Il token successivo, l'operatore '+', ha precedenza maggiore rispetto a quello in cima allo stack. Va aggiunto in cima:

STACK : ( + ( - ( +
OUTPUT: 10 5 - 8 2 - 3

Il token successivo, il numero 4, va alla fine della stringa di output:

STACK : ( + ( - ( +
OUTPUT: 10 5 - 8 2 - 3 4

Il token successivo + una parentesi di chiusura. Procediamo come nei casi precedenti:

STACK : ( + ( -
OUTPUT: 10 5 - 8 2 - 3 4 +

Di nuovo, il token successivo è una parentesi di apertura:

STACK : ( +
OUTPUT: 10 5 - 8 2 - 3 4 + -

L'ultimo token è anch'esso una parentesi di apertura:

STACK :
OUTPUT: 10 5 - 8 2 - 3 4 + - +

Abbiamo letto tutta la stringa di input e lo stack è vuoto. Il risultato è dunque il seguente:

10 5 - 8 2 - 3 4 + - +


Parte II: valutare un'espressione in formato RPN

L'algoritmo per la valutazione di un'espressione in formato RPN è semplice semplice:

1) Si legge l'espressione da sinistra a destra, un token alla volta.

2) Ogni operando incontrato va inserito in cima allo stack.

3) Incontrando un operatore, si prelevano due operandi (o uno, se l'operatore è unario) dallo stack, si applica l'operatore agli operandi prelevati, e il risultato si inserisce in cima allo stack. Se l'operatore è binario, il primo operando prelevato dallo stack è l'operando destro; il secondo è l'operando sinistro. Per l'addizione e la moltiplicazione, l'ordine non è importante: 2 * 3 = 3 * 2. Per la sottrazione e la divisione, invece si: 2 / 3 è diverso da 3 / 2.

4) Alla fine, l'operando in cima allo stack contiene il risultato dell'espressione.

Valutiamo la nostra espressione:

10 5 - 8 2 - 3 4 + - +

Il primo token è il numero 10. Va in cima allo stack:

STACK: 10

Anche il secondo token, il numero 5, va in cima allo stack:

STACK: 10 5

Il token successivo è l'operatore '-'. Si prelevano due operandi dallo stack, si applica l'operatore e il risultato(10 - 5 = 5) viene posto in cima allo stack:

STACK: 5

I due token successivi, due numeri, vanno in cima allo stack:

STACK: 5 8 2

Il token successivo è l'operatore '-'. Si procede come prima:

STACK: 5 6

I due token successivi, i numeri 3 e 4, vanno in cima allo stack:

STACK: 5 6 3 4

Il token successivo è l'operatore '+'. Si estraggono due operandi dallo stack, si sommano e il risultato si piazza in cima allo stack:

STACK: 5 6 7

Il token successivo, l'operatore '-', comporta l'estrazione di due operandi dallo stack; il risultato della sottrazione va in cima allo stack:

STACK: 5 -1

L'ultimo token è l'operatore '+'. Si estraggono due operandi dallo stack, si sommano e il risultato viene posto in cima allo stack:

STACK: 4

Siamo arrivati alla fine della stringa in input. Il numero in cima allo stack, 4, costituisce il risultato della nostra espressione.