RPN (notazione polacca inversa)

La notazione polacca inversa è una sintassi utilizzata per le formule matematiche. Fu inventata dall'australiano Charles Hamblin, filosofo ed esperto di computer, e fu così chiamata per analogia con la notazione polacca, inventata dal matematico polacco Jan Ł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.). Alcune calcolatrici scientifiche utilizzano la RPN in quanto evita l'annotazione di risultati intermedi durante le operazioni.
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 prioritizzare le 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, la RPN è facilmente implementabile sui computer.

Algoritmo per la trasformazione da notazione infissa a RPN
Stringa di input = formula in Notazione Infissa.
Stringa di output = formula convertita in Notazione Polacca Inversa (postfissa).
Stack = Pila temporanea (da usarsi solo per gli operatori). Risulterà vuota a fine elaborazione.
Si effettua l'analisi lessicale dell'espressione in forma infissa allo scopo di individuare i singoli componenti (operandi, operatori e parentesi), procedendo sequenzialmente da sinistra a destra.
Ogni operando incontrato, si aggiuge alla fine della stringa di output.
Per ogni operatore, si intraprendono le seguenti azioni:
Se l'operatore in cima allo stack ha una precedenza minore rispetto a quello corrente (l'operatore, cioè, che abbiamo appena letto dalla stringa di input), inseriamo quest'ultimo in cima allo stack (così pure se in cima allo stack risiede una parentesi aperta).
A questo punto però occorre verificare se la nuova situazione dello stack richieda o meno una nuova estrazione (che deve avvenire nel caso l'operatore appena immesso abbia una precedenza minore di quello che adesso lo precede). Se l'estrazione viene effettuata, tale controllo della coppia di operandi va ripetuto a meno che non si incontri una parentesi aperta oppure si raggiunga l'inizio dello stack.
Se incontriamo una parentesi di apertura, la inseriamo in cima allo stack. Se incontriamo una parentesi di chiusura, estraiamo ogni operatore dallo stack e lo piazziamo alla fine della stringa di output. Il processo va avanti finché la cima dello stack non contiene la parentesi di apertura .La parentesi in cima allo stack va estratta e scartata così come quella di chiusura.