Ir al contenido principal

Expresiones Aritméticas en Notación Postfija (I)

La Notación Polaca Inversa, Notación Posfija o RPN (Reverse Polish Notation) no es más que una forma de representación de expresiones aritméticas. Se trata de una notación que permite omitir los paréntesis en las expresiones, pero manteniendo el orden o prioridad de los distintos operadores y los cálculos se van realizando de forma secuencial en el momento en que se introduce un operador.


Si quieres programar una calculadora, un interprete, un evaluador de expresiones, un compilador, etc., sin duda te resultará muy interesante.

A modo de ejemplo, consideremos la siguiente expresión aritmética simple para obtener su notación en postfijo:

(9 - (5 + 2)) * 3

En primer lugar evaluamos el paréntesis interior, obteniendo la siguiente expresión:

(9 - (52+)) * 3

Ahora evualuamos el paréntesis exterior:

(952+-)

y finalmente el producto:

952+-3*

Con lo que finalmente hemos obtenido la notación posfija 952+-3* correspondiente a la expresión (9 - (5 + 2)) * 3

Ni que decir tiene, que para poder evaluar una expresión en notación postfija, tenemos que recorrerla de izquierda a derecha en busca del primer operador y posteriormente obtener los operandos inmediatamente a su izquierda:

952+-3* => 97-3* => 23* => 6

Como vemos, en el primer paso se llega al operador '+' y se hace la suma de 5+2=7, quedando la expresión como 97-3*. A continuación llegamos al operador resta '-', y hacemos la resta de 9-7=2 con lo que ya tenemos 23*. Y por último nos queda el operador del producto '*' obteniendo el valor 6 como resultado de la expresión.

Desde el punto de vista de la programación y de la estructura de datos necesaria para evaluar una expresión en postfijo, nos bastará con una simple PILA en la que iremos depositando los distintos operandos y en el momento de entrar un operador, lo que haremos será extraer de la pila los operandos correspondientes, aplicar la operación indicada por el operador y guardar el resultado en la pila.

Obviamente si lo que queremos es programar un "conversor" de expresiones algebraicas (en Infijo) a expresiones en Postfijo, podremos emplear una estructura de datos arbórea (AST - Arbol de Sintaxis Abstracta) y haciendo un recorrido del árbol en Postorden. También podríamos hacer uso del "Algoritmo Shunting Yard" inventado por Edsger Dijkstra, sin duda un gran físico y científico en materia computacional, por desgracia falleció en 2002 pero nos dejó un gran legado:


  •  Algoritmo de Dijkstra (Solución al problema del camino más corto)
  •  Algoritmo Shunting Yard (Notación Polaca Inversa - Postfijo)
  •  El Algoritmo del banquero (interbloqueo en Sistemas Operativos)
  •  Propuso el problema de la cena de filósofos (Sincronización de procesos en un Sistema Operativo)
  •  etc.

Comentarios

Entradas populares de este blog

Driver L293D de Texas Instruments

El L293D de Texas Instruments es sin lugar a dudas un circuito integrado de un gran valor cuando necesitamos controlar motores de corriente continua o bipolares de pasos (Bipolar stepping motors)Es cierto que se trata de un puente en H (o medios puentes), en este caso cuádruple, que sin bien podríamos crearlo con transistores, el echo de que se encuentre integrado en un único chip es de agradecer.Capáz de conducir corrientes bidireccionales de hasta 1 amperio en el modelo L293 y hasta 600 mA en el modelo L293D y con tensiones que van desde los 4.5V hasta los 36V en ambos modelos.Por supuesto podemos utilizarlo en otras aplicaciones o para controlar otros componentes: motores de corriente continua, relés, motores de paso bipolares, solenoides en general y cualquier carga que requiera una alta corriente y tensión.Las entradas son de tipo TTL y se activan por parejas, es decir, desde la pata Enable 1,2EN, activamoslas entradas 1 y 2 y desde la pata Enable 3,4EN activamos la 3 y la 4. Cad…

Árbol binario de expresión y Notación Posfija (II)

En una publicación anterior, hablaba sobre que es la notación posfija, para que puede ser útil y mostraba un pequeño ejemplo con una expresión aritmética simple:
(9 - (5 + 2)) * 3
Pues bien, hoy voy a mostraros como podemos crear el árbol binario correspondiente para analizar o evaluar esta expresión, haciendo uso del recorrido en postorden.
Lo primero que debemos hacer es crear el árbol, respetando las siguientes reglas:
⦁ Los nodos con hijos (padres) representarán los operadores de la expresión.
⦁ Las hojas (terminales sin hijos) representarán los operandos.
⦁ Los paréntesis generan sub-árboles.
A continuación podemos ver cómo queda el árbol para la expresión del ejemplo (9 - (5 + 2)) * 3:




Si queremos obtener la notación postfija a partir de este árbol de expresión, debemos recorrerlo en postorden (nodo izquierdo – nodo derecho – nodo central), obteniendo la expresión: 952+-3x
Así, si quisiéramos evaluar la expresión, podemos hacer uso de un algoritmo recursivo. A continuación tene…

GNUPG - Instalación en Windows

Podemos descargar GNUPG para windows en su versión 1.4.9 desde aquí.El proceso de instalación de GNUPG es un proceso muy sencillo que básicamente consiste en pulsar siguiente..., instalar y finalizar. Una vez instalado estará en "C:\Program Files\GNU\GnuPG", eso si no hemos cambiado nosotros la ubicación, la cual será muy importante recordar.

Para poder utilizar cómodamente GNUPG desde la "Shell de comandos", tenemos que asegurarnos de que en la variable de entorno PATH, está añadido el path al directorio de instalación de GNUPG. Esto no es estrictamente necesario, ya que, podemos acceder al directorio de GNUPG y desde ahí ejecutar los comandos pero, personalmente recomiendo que asigneis a la variable de entorno PATH los valores correctos para poder ejecutar GNUPG desde cualquier ubicación.

Hay varias formas de modificar o añadir variables de entorno. Podemos hacerlo desde la propia shell o desde el panel de control de windows. Una forma rápida de llegar a la ventana…