Valutazione di espressioni aritmetiche tramite l'uso di pile
Mauro Brunato
Argomenti correlati: [ La pila ] [ Strutture dati astratte ]
I calcolatori utilizzano normalmente una pila per eseguire calcoli aritmetici.
Per farlo dispongono di primitive simili alle
seguenti (la sintassi, ovviamente, varia a seconda della macchina):
- PUSH n
Inserisci il numero n nella pila.
- ADD
Estrai due numeri dalla pila, sommali e inserisci nella pila il risultato.
- SUBTRACT, MULTIPLY, DIVIDE
Come sopra, per le altre operazioni aritmetiche.
In altri termini, il calcolatore esegue i calcoli inserendo gli operandi nella pila ed eseguendo le operazioni
sugli elementi in cima alla pila. Al termine del calcolo, la pila contiene come unico valore il risultato.
Ecco alcuni esempi. Nella prima colonna sono indicate le espressioni scritte nella notazione usuale;
nella seconda le operazioni che vengono effettivamente eseguite dal calcolatore; nella terza colonna,
è riportato il contenuto della pila alla fine di ciascuna operazione.
Espressione
| Operazioni sulla pila
| Contenuto della pila dopo ciascuna operazione
|
5+7
|
PUSH 5
PUSH 7
ADD
|
5
5 7
12
|
6-3*2
|
PUSH 6
PUSH 3
PUSH 2
MULTIPLY
SUBTRACT
|
6
6 3
6 3 2
6 6
0
|
2-3*5/(4+1)
|
PUSH 2
PUSH 3
PUSH 5
MULTIPLY
PUSH 4
PUSH 1
ADD
DIVIDE
SUBTRACT
|
2
2 3
2 3 5
2 15
2 15 4
2 15 4 1
2 15 5
2 3
-1
|
Notare che in tutti i casi gli operandi vengono inseriti nel'ordine in cui compaiono, ma alcune operazioni
vengono differite a seconda dell'ordine di precedenza (naturale o dettato dalle parentesi).
Traduzione delle espressioni
Il problema nel valutare le espressioni aritmetiche, scritte nella consueta notazione, è proprio
quello che non tutti gli operatori possono essere eseguiti subito: la valutazione di alcuni va differita
finché tutti gli operatori adiacenti con maggior precedenza sono stati eseguiti.
Ecco come possono essere tradotte semplici espressioni aritmetiche comprendenti le quattro operazioni e le parentesi.
Innanzitutto, bisogna definire una pila supplementare, oltre a quella aritmetica,
in grado di contenere i simboli degli operatori, come caratteri, codificati
numericamente o tramite un tipo definito per enumerazione. Chiameremo questa pila supplementare
pila degli operatori,
mentre quella prima introdotta per l'esecuzione dei calcoli verrà chiamata d'ora in poi pila aritmetica.
Ad ogni passo si legge dall'espressione un elemento, che può essere un numero oppure uno dei simboli
'+', '-', '*', '/', '(', ')'.
Ad ogni elemento letto, si seguono le seguenti regole:
- Se si tratta di un numero n, eseguiamo l'istruzione PUSH n che introduce il numero n
nella pila aritmetica.
- Se si tratta di una parentesi aperta, la inseriamo nella pila degli operatori.
- Se si tratta di un operatore, lo inseriamo nella pila degli operatori dopo aver estratto dalla sua cima
tutti gli operatori eventualmente presenti con priorità maggiore o uguale. Ogni volta che un operatore
viene estratto dalla pila, l'operazione corrispondente viene effettuata sulla pila aritmetica.
- Se si tratta di una parentesi chiusa, vengono estratti dalla pila degli operatori tutti gli operatori fino alla
prima parentesi aperta. Ad ogni estrazione, l'operazione corrispondente all'operatore
estratto viene eseguita sulla pila aritmetica.
Quando l'espressione da valutare è terminata, tutti gli operatori ancora
presenti sulla pila degli operatori vengono estratti ed eseguiti.
Consideriamo per esempio la valutazione dell'espressione 1-(4*3+2)/7. La seguente tabella
riassume tutti i passi dell'algoritmo appena delineato.
Simbolo letto
| Operazione sulla Pila operatori
| Pila operatori
| Operazione sulla Pila aritmetica
| Pila aritmetica
| Commenti
|
1
|
| vuota
| PUSH 1
| 1
| I numeri vengono spinti direttamente nella pila aritmetica
|
-
| PUSH '-'
| -
|
| 1
| Il primo operatore entra subito nella pila degli operatori
|
(
| PUSH '('
| - (
|
| 1
| La parentesi aperta va inserita senza controlli
|
4
|
| - (
| PUSH 4
| 1 4
|
|
*
| PUSH *
| - ( *
|
| 1 4
| Nulla viene estratto dalla pila degli operatori perché nella sua cima non ci sono
operatori di priorità maggiore di * o uguale.
|
3
|
| - ( *
| PUSH 3
| 1 4 3
|
|
+
| POP PUSH '+'
| - ( - ( +
| MULTIPLY
| 1 12
| Prima di inserire + è stato estratto ed eseguito * perché avente
priorità maggiore. Dopo l'estrazione di * non viene estratto altro, perché la parentesi
non è un operatore da eseguire, e il '-' non viene estratto perché non si trova in cima
alla pila.
|
2
|
| - ( +
| PUSH 2
| 1 12 2
|
|
)
| POP POP
| - ( -
| ADD
| 1 14
| Vengono estratti ed eseguiti tutti gli operatori presenti nella pila fino
alla prima parentesi aperta, in questo caso un'addizione.
|
/
| PUSH '/'
| - /
|
| 1 14
| La divisione viene inserita subito perché nella cima della pila
c'è un operatore con priorità strettamente minore.
|
7
|
| - /
| PUSH 7
| 1 14 7
|
|
Fine
| POP POP
| - vuota
| DIVIDE SUBTRACT
| 1 2 -1
| Alla fine dell'espressione, tutti gli operatori rimasti nella pila (la divisione e la sottrazione)
vengono estratti ed eseguiti.
|
Si noti che se l'espressione di partenza è sintatticamente corretta, alla fine la pila degli operatori
contiene soltanto segni di operazioni e non parentesi.