Reverse Polish notation

rdf:langString Notazione polacca inversa

rdf:langString La notazione polacca inversa (in inglese reverse polish notation o semplicemente RPN) è una sintassi utilizzata per le formule matematiche. Fu inventata dall'australiano , filosofo ed esperto di computer, e fu così chiamata per analogia con la notazione polacca, inventata da Łukasiewicz. Con la RPN è possibile effettuare qualsiasi tipo di operazione, con il vantaggio di eliminare i problemi dovuti alle parentesi e alla precedenza degli operatori (prima la divisione, poi l'addizione ecc.). La sintassi di diverse calcolatrici contabili è tuttora la RPN (l'operatore deve digitare le formule in questo formato). Inizialmente utilizzata per semplificare l'hardware della macchina è diventata una sintassi standard utilizzata anche dall'utente. Nella notazione polacca inversa, detta anche notazione postfissa in contrasto con la normale notazione infissa, prima si inseriscono gli operandi e poi gli operatori: un esempio di RPN è 3 2 + che equivale al classico 3+2, oppure 10 2 / che fornisce 5. Quando si utilizza la RPN si fa conto di possedere una pila (stack) su cui pian piano si accumulano gli operandi: prima si impila il 3, poi il 2. Un operatore invece preleva dalla cima della pila tutti gli operandi di cui ha bisogno, esegue l'operazione, e vi rideposita il risultato. L'elemento più in basso è da considerarsi sempre l'operando sinistro. Se l'espressione completa è corretta, alla fine di tutte le operazioni sulla pila si avrà un solo elemento, il risultato finale. Questa pila permette, come già detto, di evitare l'utilizzo di parentesi per indicare la priorità delle operazioni, basta inserire nella parte sinistra della formula tutti gli operandi delle operazioni a parentesizzazione più esterna, al centro le operazioni più elementari, alla destra tutti gli operatori di combinazioni dei risultati delle operazioni centrali con gli operandi già presenti.Esistono infatti algoritmi di conversione sia dalla notazione infissa a quella postfissa che viceversa. Come si può notare da gli esempi successivi, il calcolo di un'espressione in RPN è facilmente implementabile sui computer. Un esempio: 5 + (10 * 2) → 5 10 2 * + Prima della moltiplicazione sono presenti sulla pila 5, 10, 2. Il "*" recupera i primi due elementi (10, 2) li moltiplica e modifica la pila in modo che contenga 5, 20. L'operazione "+" addiziona 5 e 20, ora presenti nella pila, sostituendoli con il risultato: 25. Altri esempi più complessi: ((10 * 2) + (4 - 5)) / 2 → 10 2 * 4 5 - + 2 /(7 / 3) / ((1 - 4) * 2) + 1 → 1 7 3 / 1 4 - 2 * / + oppure 7 3 / 1 4 - 2 * / 1 + La notazione polacca inversa prende spunto dalla notazione polacca, in cui gli operatori vengono posti prima degli operandi (quindi: + 1 2 invece di 1 2 +), ma la prima è più facilmente implementabile in modo elettronico o via software. La maggior parte dei calcolatori tascabili, commercializzati in modo massiccio soprattutto negli anni '80 e '90, che utilizza RPN invece della classica notazione algebrica (con parentesi e notazione infissa) è stata prodotta da Hewlett-Packard.