Notacion Polaca Inversa - Notacion Postfija (Parte 1)

La notación polaca inversa, notación de postfijo, o notación posfija, (en inglés, Reverse Polish notation, o RPN), es un método algebraico alternativo de introducción de datos. Su nombre viene por analogía con la relacionada notación polaca, una notación de prefijo introducida en 1920 por el matemático polaco Jan Łukasiewicz, en donde cada operador está antes de sus operandos. En la notación polaca inversa es al revés, primero están los operandos y después viene el operador que va a realizar los cálculos sobre ellos. Tanto la notación polaca como la notación polaca inversa no necesitan usar paréntesis para indicar el orden de las operaciones mientras la aridad del operador sea fija. Leer mas en wikipedia

Ver la segunda parte del articulo con código fuente disponible

Existen varias notaciones para representar expresiones aritméticas, que se diferencian en el orden en que se escriben los argumentos (operandos) de los operadores. Las más relevantes son:

Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando. 

Notación prefija: El orden es operador, primer operando, segundo operando. 

Notación postfija: El orden es primer operando, segundo operando, operador. 

Notación funcional: Se escribe el operador/función y despues, entre paréntesis, los operadores separados por comas. 

La notación infija tiene el problema de que en expresiones con más de un operador existe ambiguedad sobre cual es el orden de evaluación. Por ejemplo, la expresión 8/4/2 se puede interpretar como (8/4)/2 o bien como 8/(4/2). Las otras notaciones no sufren este problema.

Un problema interesante en computación es poder convertir expresiones en notación INFIJA a su equivalente en notacion POSTFIJA. 

Dada la expresión A+B se dice que está en notación INFIJA, y su nombre se debe a que el operador (+) esta entre los operadores (A y B). 

La ventaja de usar expresiones en notación polaca postfija radica en que no son necesarios los paréntesis para indicar orden de operación, ya que este queda establecido por ubicación de los operadores con respecto a los operandos. 

Para convertir una expresión dada en notación infija a una notación postfija, deberán establecerse previamente ciertas condiciones

Convertir de notacion infija a postfija

Pseudocódigo

1. Inicializar la pila
2. Repetir hasta que no haya caracteres en la expresión de
entrada
2.1 Leer un carácter de la expresión
2.2 Si es un operando se pasa a la expresión postfija de salida
2.3 Si el elemento es un operador distinto de ‘)’ entonces:
2.3.1 Si la pila está vacía se mete en la pila.
2.3.2 Si la pila NO está vacía
• Si la prioridad del operador es mayor que la prioridad del
operador de la cima de la pila ⇒ se mete en la pila
• Si la prioridad del operador es menor o igual que la prioridad
del operador de la cima de la pila ⇒ se saca el operador de la
cima y se coloca en la expresión postfija. Volvemos a 2.3
2.4 Si el elemento es el operador ‘)’ entonces:
2.4.1 Se sacan operadores de la pila hasta encontrar el paréntesis ‘(‘
que se elimina (las expresiones postfijas no llevan paréntesis)
3. Al finalizar el recorrido por la expresión aritmética se pasa todo
el contenido de la pila a la expresión postfija

Evaluar una expresion postfija para obtener su resultado

Pseudocódigo

1. Inicializar la pila
2. Repetir hasta que no haya caracteres en la expresión
a evaluar
2.1 Obtener el siguiente item de la expresión
2.2 Si el elemento es un operando se mete en la pila
2.3 Si el elemento es un operador (denominado &) entonces:
2.3.1 Se extraen los dos elementos superiores de la pila,
denominados Op2 y Op1 respectivamente.
2.3.2 Se evalúa el resultado de Op1 & Op2 y se almacena en Z
2.3.3 Se introduce Z en la cima de la pila
3. Obtener el valor de la expresión de la cima de la pila

¿Necesitas mas documentacion o informacion?
Puedes ir a los siguientes enlaces
Documentacion en pdf
Presentacion en PowerPoint


Visita nuestra pagina en Facebook