La Notazione Polacca Inversa (in sigla: RPN, Reverse Polish
Notation) è una forma di rappresentazione di un’espressione
numerica in modo che l’ordine di esecuzione delle operazioni sia
univocamente determinato, ma senza utilizzare parentesi e senza
dover ricorrere alle regole di precedenza fra operatori. Si tratta
quindi di un modo diverso, ma equivalente a quello normalmente adottato, per
scrivere
le espressioni e data una espressione in notazione RPN è sempre
possibile ricavare la corrispondete espressione in forma “normale” e
viceversa. Quindi non ha “punti deboli”
o limitazioni rispetto alla forma usuale.
Per scrivere un’espressione in notazione RPN sono sufficienti i valori
numerici che indicano gli operandi
ed i segni di operazione (e di funzione) e non occorrono,
come già detto le parentesi. La valutazione di una espressione in
forma RPN avviene da sinistra verso destra con una regola molto semplice:
Ogni simbolo di
operazione (o di funzione) si applica all’operando immediatamente precedente,
se si tratta di operazione o funzione ad un solo valore, oppure ai due
operandi immediatamente precedenti, se si tratta di operazione o funzione
a due operandi; il risultato di ciascuna operazione sostituisce l’operando
(o i due operandi) a cui l’operazione è stata applicata.
Vediamo ad esempio la seguente espressione, in notazione “normale”:
7*4^(3*(2.1+6))+sen(5.5)
(dove si è usato il carattere “^” per indicare l’elevamento a potenza)
Se vogliamo valutarla correttamente dobbiamo usare sia le regole
di precedenza fra operatori, che quelle relative alle parentesi.
La stessa espressione in notazione RPN sarebbe:
4 2.1 6 + 3 * ^ 7 * 5.5 sen +
Applicando la regola enunciata sopra, partendo cioè da sinistra,
si vede che il primo operatore che si incontra è il +, e questo
significa che occorre sommare i due numeri alla sua sinistra. Si ottiene
(evidenziando fra parentesi quadre il risultato parziale):
4 [8.1] 3 * ^ 7 * 5.5 sen +
Proseguendo
si incontra l’operatore *: si moltiplica allora il risultato precedente
con il numero 3:
4 [24.3] ^ 7 * 5.5 sen +
Poi il numero 4 viene elevato al valore
ottenuto fino ad ora,
poi il numero 7 viene moltiplicato per il risultato,
poi viene calcolato il seno del numero 5.5 (si noti che la funzione sen
ha un solo operando) e infine viene eseguita l’ultima operazione di somma.
Esattamente lo stesso avremmo fatto se avessimo applicato
le regole che ben conosciamo all’espressione normale, ma
come si vede la notazione RPN indica l’ordine esatto delle operazioni
rendendo inutili tutte queste regole.
La notazione polacca inversa (detta anche “postfissa”, dato che l’operatore
segue gli operandi) ha avuto per lungo tempo interesse limitato, fino
all’avvento delle calcolatrici elettroniche. Dato che le regole per
il calcolo in forma RPN sono molto semplici
anche i programmi per il loro calcolo sono
assai più semplici di quelli necessari per interpretare la notazione
usuale; quindi le prime calcolatrici, che non erano in grado di eseguire
programmi “complessi”, utilizzavano questo tipo di notazione
per il calcolo delle espressioni.