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

Publicar un comentario

Entradas populares de este blog

Como usar el TL431 (muy facil)

En este artículo, no vamos a entrar en el funcionamiento interno de este IC, ni tampoco en sus características técnicas, puesto que para esos fines ya existe su hoja de datos correspondiente. Más bien, lo que pretendo aquí es dejar constancia de como podemos utilizar este IC desde un punto de vista práctico, útil y sobre todo de una manera sencilla, con el objetivo de que cualquiera pueda utilizarlo. Si has llegado hasta aquí, probablemente ya sabes que por internet hay mucha información sobre este IC, pero también bastante confusa o excesivamente técnica, sin mostrar tan siquiera un ejemplo de funcionamiento, o como calcular sus pasivos. Pues se acabó, a partir de hoy y después de leer este post, ya te quedará claro como utilizar el TL431 para obtener una tensión de referencia estable y precisa. Vamos al grano y que mejor que empezar aclarando que el TL431 NO ES EXACTAMENTE UN ZENER como se empeñan en decir en muchos sitios, es verdad que se le conoce como el Zener Progra...
9 comentarios
Leer más

I designed a PCB Holder

If you're one of those people who like electronics, then you know how frustrating it can be when you need to hold a PCB for soldering a component. Download Link: https://www.thingiverse.com/thing:1103401 That was my case when I decided to make a stand PCB. First I was looking at what was available in the market (Weller by example), in order to have some reference on which to base my design. Finally, I decided on a type of support that allows to turn the PCB in order to be able to have easy access to both sides of it. The hardest part was to design the clamping mechanism. In the end I think I found a good solution, based on three springs that allow the PCB firmly secure but at the same time release with little effort, to rotate if necessary. Here you can download all files you need to make my PCB Holder: https://www.thingiverse.com/thing:1103401
Publicar un comentario
Leer más

El Robin Hood de los procesos pobres (Vamos de escalada)

Pues sí, has leído bien, hoy nos vamos de escalada, pero ojo! No nos vamos a las montañas, nos vamos al interior, al kernel del sistema operativo Windows 10 en esta ocasión, aunque es aplicable a otras versiones con algunos mínimos cambios. Hoy la cosa va de EoP (Elevation of Privilege), escalada de privilegios en el sistema. Vamos a ver cómo hacer de Robin Hood para "mangarle" el “Access Token” al usuario "NT AUTHORITY\SYSTEM" a través de la estructura _EPROCESS del proceso “System” para dárselo al pobre CMD.EXE. ¿Con qué fin? Pues darle poder absoluto sobre el sistema a un usuario limitado, por ejemplo para que pueda utilizar la calculadora, o el notepad sin limitaciones :) Venga vale, que es broma, que en realidad será para utilizarlo en una shellcode y un driver de dispositivo firmado por alguien :) Antes  de  comenzar  hay  que  dejar  claro  que  vamos  a  necesitar  algunas herramientas para realizar este proce...
Publicar un comentario
Leer más