Notazione polacca inversa

Da Wikipedia, l'enciclopedia libera.

La notazione polacca inversa (in inglese reverse polish notation o semplicemente RPN) è una sintassi utilizzata per le formule matematiche. Fu inventata dall'australiano Hamblin, 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.). 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.

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, che tutt'oggi continua a produrre modelli basati su RPN.

Algoritmo per la trasformazione da notazione infissa a RPN[modifica | modifica sorgente]

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.


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica