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

WinRT with C++ Standard vs C++/CX

OFFTOPIC: Nota: Hoy he decidido escribir esta publicación del blog en inglés. Note: Today I decided to write this blog post in English. In a new application than I am developing for a company, I had to decide if to make use of C++/CX (C++ with Component Extension) or make all the main stuff in C++ standard and ABI/COM. All of you than have had to work with COM (Component Object Model) and fighting with the interfaces, reference count, etc. known the tricky and heavy that it can become. As an example of the easy approach using C++/CX, I am creating a new Uri object, like this: auto uriEasyWay = ref new Windows::Foundation:: Uri ( http://www.manuelvillasur.com ); assert (wcscmp(uriEasyWay->AbsoluteUri->Data(), L"http://www.manuelvillasur.com/" ) == 0); Now, I going to show you the more difficult approach using C++ Standard and  ABI/COM interfaces: HSTRING_HEADER header = {}; HSTRING string = nullptr ; HRESULT hr = WindowsCreateStringRefer
1 comentario
Leer más

Á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
5 comentarios
Leer más