Notació polonesa inversa

La notació polonesa inversa (RPN en anglès, Reverse Polish Notation) o notació postfix és un mètode d'introducció de dades alternatiu a l'algebraic. Va ser creat pel filòsof i científic de la computació australià Charles Leonard Hamblin a mitjans dels anys 1950. Deriva de la notació polonesa inventada pel matemàtic polonès Jan Lukasiewicz.

A la dècada dels 60 aquest mètode va ser introduït als ordinadors. Posteriorment, Hewlett-Packard (HP) el va aplicar per primera vegada a la calculadora de sobretaula HP-9100A el 1968.

El seu principi és el d'avaluar les dades directament quan s'introdueixen i manejar-les dintre d'una estructura LIFO (Last In First Out), mètode que optimitza els processos a l'hora de programar.

Bàsicament les diferències amb el mètode algebraic són que, per avaluar les dades directament quan s'introdueixen, no és necessari ordenar-ne l'avaluació, i que per a executar un ordre, primer s'han d'introduir tots els seus arguments, així, per a fer una simple suma $\,\!a+b=c$ el RPN ho ordenaria $\,\!a\ b\ +$, deixant el resultat $\,\!c$ directament.

Cal tenir en compte que la notació polonesa inversa no és literalment la imatge especular de la notació polonesa: amb operadors no-commutatius (com la resta o la divisió), l'ordre dels operands ha de romandre constant. Així per tant, «$\,\!6/2$» es tradueix a la notació polonesa com «$\,\!/6\ 2$» i a la notació polonesa inversa com «$\,\!6\ 2/$». Amb nombres superiors a 9, també se segueix el costum d'escriure'ls d'esquerra a dreta.

Avantatges

• Els càlculs es realitzen seqüencialment a mesura que es van introduint operadors, en comptes d'haver d'esperar a escriure l'expressió completa. A causa d'això, es cometen menys errades per processar càlculs complexos.

• El procés d'aplicació permet guardar resultats intermedis per un ús posterior. Aquesta característica permet que les calculadores RPN computin expressions de complexitat molt superior que l'aconseguida per calculadores algebraiques.

• No requereix parèntesis ni regles de preferència, com passa amb la notació algebraica, ja que el procés d'empilament permet calcular l'expressió per etapes.

• A les calculadores RPN, el càlcul es realitza sense haver de prémer la tecla "=" (encara que es necessita prémer la tecla «Enter» per afegir xifres a la pila).

• L'estat intern de la calculadora sempre consisteix en una pila de xifres sobre les quals es pot operar. Atès que no es poden introduir operadors a la pila, la notació polonesa inversa és conceptualment més senzilla i provoca menys errors que altres notacions.

• En termes educatius, la notació polonesa inversa requereix que l'estudiant comprengui l'expressió que s'està calculant. Copiar una expressió algebraica directament a una calculadora sense comprendre l'aritmètica donarà un resultat erroni.

Desavantatges

• L'adopció gairebé universal de la notació algebraica en els sistemes educatius fa que no hi hagi moltes raons pràctiques immediates perquè els alumnes aprenguin la notació polonesa inversa. No obstant això, molts estudiants afirmen que, una vegada apresa, la notació polonesa inversa simplifica significativament el càlcul d'expressions complexes.

• És difícil usar la notació polonesa inversa escrivint a mà, donada la importància dels espais per a separar operands. Es requereix una cal·ligrafia molt clara per a evitar confondre, per exemple, 12 34+ (=46) amb 123 4+ (=127) o 1 234+ (=235).

• Les calculadores RPN són relativament rares. Forçat a usar una calculadora algebraica, l'usuari d'una calculadora RPN acostuma a cometre més errors del normal a causa dels seus hàbits d'ús normals. Tanmateix, això no és un problema tan greu en l'actualitat, a causa que molts sistemes operatius poden emular calculadores RPN.

L'algoritme RPN

• Si hi ha elements a la safata d'entrada
  • Llegir el primer element de la safata d'entrada
  • Si l'element és un operant.
    • Posar l'operant a la pila.
  • Si no, l'element és una funció (els operadors, com «+», no són més que funcions que prenen dos arguments).
    • Se sap que la funció x pren n arguments.
    • Si hi ha menys de n arguments a la pila
      • (Error) L'usuari no ha introduït suficients arguments a l'expressió.
    • Si no, prendre els últims n operands de la pila.
    • Avaluar la funció pel que fa als operands.
    • Introduir el resultat (si n'hi hagués) a la pila.
• Si hi ha només un element a la pila
  • El valor d'aquest element és el resultat del càlcul.
• Si hi ha més d'un element a la pila
  • (Error) L'usuari ha introduït massa elements.

Exemple

L'expressió algebraica $\,\!5+\ ((1+2)*4)\ -3$ es tradueix a la notació polonesa inversa com $\,\!5\ 1\ 2\ +\ 4\ *\ +3\ -$ i s'avalua d'esquerra a dreta segons es mostra a la següent taula. La «pila» és la llista dels valors que l'algoritme manté a la seva memòria després de realitzar l'operació donada a la segona columna.

Entrada	Operació	Pila	Comentari
5	Introduir a la pila	5
1	Introduir a la pila	5, 1
2	Introduir a la pila	5, 1, 2
+	Suma	5, 3	Prendre els dos últims valors de la pila (1, 2) i substituir-los pel resultat (3)
4	Introduir a la pila	5, 3, 4
*	Multiplicació	5, 12	Prendre els dos últims valors de la pila (3, 4) i substituir-los pel resultat (12)
+	Suma	17	Prendre els dos últims valors de la pila (5, 12) i substituir-los pel resultat (17)
3	Introduir a la pila	17, 3
−	Resta	14	Prendre els dos últims valors de la pila (17, 3) i substituir-los pel resultat (14)

Quan es finalitza el càlcul, el resultat (en aquest cas, 14) apareix com l'únic element en la pila.

Enllaços externs

• Notació científica Arxivat 2008-09-24 a Wayback Machine.
• RPN: Introducción a la notación polaca inversa Arxivat 2008-09-16 a Wayback Machine. (castellà)
• Que es Reverse Polish Notation? Arxivat 2008-07-04 a Wayback Machine. (castellà)
• Conversor d'expressions algebràiques a notació RPN (anglès)