Evaluador de expresiones postfijas (código fuente)

Las notaciones postfijas y prefijas son una técnica muy utilizada en los compiladores para representar los cálculos matemáticos de una forma mucho más simples y con ello, un mejor rendimiento en tiempo de ejecución.

Hace unos días, trasteando mis archivos viejos de la computadora para liberar un poco de espació, me encontré una joya de mi universidad. Se trata de un proyecto que me toco desarrollar cuando todavía estudiaba en la universidad.  Este proyecto era realizar un programa muy simple que convirtiera una expresión Infija a Postfija, para finalmente evaluar la expresión y dar un resultado.

Como anécdota, les cuento que este proyecto me fue solicitado en consola, pero como siempre, me quería ganar unos puntos extras, así que me esforcé un poco más y lo hice 100% gráfico.

Este articulo continua con una serie de proyectos universitarios que me toco desarrollar durante mi carrera, cliquea aquí si quieres ver más proyectos.

Expresiones Infijas:

Antes de entrar en materia, me gustaría dar un poco de contexto. Las expresiones Infijas, con las que tiene los operadores en medio de los operandos, es decir, es la notación que siempre utilizamos para representar una operación matemática, por ejemplo:

• 10 + 2
• 10 / 6
• 10 + 12 * 12
• 10 + (1 + 2)

Las notaciones infijas también permiten el uso de paréntesis para forzar la forma el orden en que las operaciones se tiene que realizar. Por ejemplo 1 + 2 * 3, como sabremos, el operador * tiene prioridad sobre el +, por lo que la expresión 2*3 se evaluara primero y al resultado se le sumará uno, dando como resultado: 7, en cambio, si modificamos ligeramente la expresión para que quede de la siguiente manera el resultado será muy diferente: (1 + 2) * 3. En este caso, las operaciones entre paréntesis tendrán más prioridad, dando como resultado la suma de 1 + 2 y el resultado multiplicado por 3, lo que nos da: 9.

Expresiones Postfijas:

Las operaciones postfijas buscan resolver los mismos problemas de las expresiones infijas, pero atacan el problema de otra manera. En estas expresiones, no existen los paréntesis y los operados y operandos se representa de forma distinta, por ejemplo:

• 10 + 2       => 10, 2, +
• 10 / 6 => 10, 6, /
• 10 + 12 * 12 => 10, 12, 12, *, +
• 10 + (1 + 2) => 10, 1, 2, +, +

En las expresiones Postfijas, la ecuación de evalúa de forma lineal, pues los operadores y operandos están ordenados de tal forma que ya no es necesario tener en cuenta la precedencia de los operadores.

Como lo comenté anteriormente, los compiladores realizan la conversión de expresiones infijas a postfijas, para aumentar la efectividad en tiempo de ejecución.

Para realizar la conversión de infijas a postfijas es necesario utilizar una Pila y seguir las siguientes reglas:

• Operador = precedencia > se cambia
• Operador > precedencia > se agrega a la pila
• Operador < precedencia > sacar operador de la pila
• Paréntesis derecho > vaciar pila

1. No te preocupes si no quedan claras las reglas, las analizaremos con el ejemplo 10 + ( 1 + 2) * 2.
2. Lo primero será tomar el 10 de la expresión y pintarla en el resultado: Resultado => 10
3. Luego, tenemos el operados + el cual deberemos agregar a la pila: pila => [+]
4. Luego, tenemos un paréntesis izquierdo, lo agregamos a la pila: pila => [ + , ( ]
5. Seguido, tenemos el número 1 y lo pasamos directo al resultado: Resultado => 10, 1
6. El siguiente operador es +, el cual es almacenado en la pila: pila => [ + , (, +]
7. El siguiente número en aparecer es el 2, el cual pasa directo al resultado: resultado => 10, 1, 2
8. El siguiente valor es un paréntesis derecho, por lo que tendremos que vaciar la pila hasta el siguiente paréntesis izquierdo. Por lo que sacamos de la pila el operador +, dejando el resultado de la siguiente manera: Resultado => 10, 1, 2, + y la pila: [ + ]
9. El siguiente valor es el operador *, el cual al ser de mayor precedencia que +, entra en la pila: pila => [ +, * ]
10. Nuevamente aparece el operando 2, el cual pasa directo al resultado: resultado => 10, 1, 2, +, 2
11. En este punto hemos terminado de evaluar la expresión, por lo que solo resta vaciar toda la pila: resultado => 10, 1, 2, +, 2, *, + y la pila => []

Resultado final:  10, 1, 2, +, 2, *, +

Evaluación de expresiones postfijas:

Una vez que tenemos la expresión postfija generada, será necesario evaluarla, por lo que el procedimiento será algo similar al de la generación, ya que nos apoyaremos de una pila para evaluar.

En este caso, cada número que encontremos en la expresión, deberá ser introducido en la pila, y cuando se encuentre un operador, deberemos sacar los dos últimos valores de la pila y aplicarles el operador. El resultado deberá ser introducido nuevamente en la pila.

Evaluando la expresión: 10, 1, 2, +, 2, *, +

1. El valor 10 es encontrado y puesto en la pila: pila => [10]
2. El valor 1 es encontrado y puesto en la pila: pila => [10, 1]
3. El valor 2 es encontrado y puesto en la pila: pila => [10, 1, 2]
4. El operador + es encontrado, por lo que se suma los valores 1 + 2 = 3, y la pila queda de la siguiente manera: [10, 3]
5. El valor 2 es encontrado y puesto en la pila: [10, 3, 2]
6. El operador * es encontrado y se multiplica 3 * 2 = 6, dejando la pila: [10, 6]
7. El operador + es encontrado y se suma 10 + 6 = 16.

El proyecto terminado:

Una vez explicada la teoría, les presentaré mi proyecto, pero antes que eso… quiero prevenirlos de que este fue un proyecto universitario, desarrollado cuando apenas empezaba a programar, por lo que es muy posible que encuentres malas prácticas de programación o algunas cosas extrañas J.

Dado que es un proyecto universitario, no quise refactorizarlo, sino más bien, mostrar el trabajo original que entré en aquel momento.

Para utilizar la aplicación, solo es necesario escribir la operación matemática sin utilizar espacios, ya que era novato y no preví esto. Los operadores que se pueden utilizar son únicamente +, -, *, / y solo evalúa número enteros.

Una vez capturada la expresión, solo deberemos presionar enter y la expresión será convertida en postfija y evaluada.

La aplicación también evalúa que la expresión tenga correctamente los paréntesis y en pares, inicie con operandos y termino con operandos.

También se evalúa la alternancia entre operandos y operadores.

El código fuente completo se encuentra en la siguiente URL:

https://github.com/oscarjb1/evaluador.git