Notazione polacca inversa

La notazione polacca inversa (in inglese reverse polish notation o semplicemente RPN) è una sintassi utilizzata per le formule matematiche. La notazione polacca è stata introdotta dal filosofo polacco Jan Łukasiewicz nel 1924. La notazione polacca inversa (NPI), una variante della notazione polacca, è stata proposta da Friedrich L. Bauer nel 1959 e successivamente resa popolare da Edsger W. Dijkstra negli anni '60 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.

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.

1. 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.
2. Si aggiunge ogni operando incontrato alla fine della stringa di output.
3. 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).
   • Se l'operatore attualmente presente in cima allo stack ha una precedenza maggiore o uguale rispetto a quello corrente, estraiamo l'operatore dallo stack, lo aggiungiamo alla fine della stringa di output e inseriamo l'operatore corrente in cima allo stack.
     • 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.
4. 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 (se lo stack si svuota senza aver incontrato la parentesi di apertura, riportiamo un errore di parentesi non bilanciate). La parentesi in cima allo stack va estratta e scartata così come quella di chiusura.
5. Dopo aver letto e trattato l'ultimo carattere dalla stringa di input, estraiamo tutti gli operatori dallo stack e li aggiungiamo alla stringa di output.

NOTA: Questa versione dell'algoritmo è valida solo se gli operatori sono associativi a sinistra.

Voci correlate

• Notazione polacca
• Programmazione stack-oriented

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla notazione polacca inversa

Collegamenti esterni

• Notazione polacca inversa, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• RPN, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Reverse Polish Notation, su MathWorld, Wolfram Research.