Pila (informática) | expresión de evaluación y análisis sintáctico

Expresión de evaluación y análisis sintáctico

Se calcula empleando la notación polaca inversa utilizando una estructura de pila para almacenar temporalmente los valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de expresión a otra forma, necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. antes de traducir a código de bajo nivel. Los lenguajes de programación de alto nivel son compilados o traducidos a código máquina realizando la conversión de expresiones a la notación que mejor se adapte a las características de su modo de operar, buscando siempre la simplicidad.

Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, se traduciría o notación postfija con la ventaja de no tener que atender a la jerarquía de prioridades:

En notación postfija: 1 2 + 4 * 3 +

La expresión es evaluada de izquierda a derecha utilizando una pila:

Diagrama de flujo para resolver una expresión en notación postfija
  • Apilar cuando el dato sea un operando
  • Desapilar dos operandos y evaluar el valor cuando el dato sea un operador.
  • Apilar el resultado de la operación.

(los datos de la pila se muestran después de haberse llevado a cabo la operación):

 ENTRADA         OPERACIÓN                 PILA
 1             Apilar operando             1
 2             Apilar operando             1, 2
 +             Sumar operandos*            3
 4             Apilar operando             3, 4
 *             Multiplicar operandos*      12
 3             Apilar operando             12, 3
 +             Sumar  operandos*           15 

El resultado final, 15, se encuentra en la pila, y el puntero apuntado a su dirección. Se lee haciendo pop y la pila vuelve a quedar vacía. 
*.- Se extraen los dos operandos con lo que el puntero los da por eliminados y, atendiendo a su orden (necesario en operaciones de resta, división y potencia) se realiza la operación. El resultado se coloca en la pila.