Notación infija, postfija y prefija

Las pilas son estructuras de datos muy usadas para la solución de diversos tipos de problemas. Pero tal vez el principal uso de estas estructuras es el tratamiento de expresiones matemáticas.

Algoritmo para convertir expresiones infijas en postfijas (rpn)

1. Incrementar la pila
2. Inicializar el conjunto de operaciones
3. Mientras no ocurra error y no sea fin de la expresión infija haz
   • Si el carácter es:
     1. PARENTESIS IZQUIERDO. Colocarlo en la pila
     2. PARENTESIS DERECHO. Extraer y desplegar los valores hasta encontrar paréntesis izquierdo. Pero NO desplegarlo.
     3. UN OPERADOR.
        • Si la pila esta vacía o el carácter tiene más alta prioridad que el elemento del tope de la pila insertar el carácter en la pila.
        • En caso contrario extraer y desplegar el elemento del tope de la pila y repetir la comparación con el nuevo tope.
     4. OPERANDO. Desplegarlo.
4. Al final de la expresión extraer y desplegar los elementos de la pila hasta que se vacíe.

Algoritmo para evaluar una expresión rpn

1. Incrementar la pila
2. Repetir
   • Tomar un caracter.
   • Si el caracter es un operando colocarlo en la pila.
   • Si el caracter es un operador entonces tomar los dos valores del tope de la pila, aplicar el operador y colocar el resultado en el nuevo tope de la pila. (Se produce un error en caso de no tener los 2 valores)
3. Hasta encontrar el fin de la expresión RPN.

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz