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): 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:

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.