Analisis

Aplicaciones de las estructuras de datos Pilas y Colas

Calculadora Post fija Considérese la suma A y B, pensando que la aplicación del operador "+" a los operandos A y B, se escribirá A+B, esta representación se denomina infijo o entrefijo. Existen otras dos formas de representar la suma de A + B utilizando el signo "+", estas son el prefijo y el postfijo. Los prefijos PRE y POST se refieren ala posición relativa del operador con respecto a los operandos. En la notación de PREFIJO el operador precede a los dos operandos y en la notación POSTFIJO el operador va después de los dos operandos. Consideremos en la expresión a+b*c escrita en infijo, observe que existen dos operadores, se quiere saber cual de estos se realizará primero, es lógico que por jerarquía se realizaría primero lamultiplicación y posteriormente la suma. La única regla durante el proceso de conversión es que las operaciones que tienen relación o jerarquía más alta se convertirá primero y después de que esta parte de la expresión ha sido convertida se maneja como operando simple. El orden de precedencia o jerarquía de los operadores son: primero el exponente, posteriormente multiplicación y división y porúltimo la suma y la resta, Cuando dos operadores tienen la misma precedencia, se sigue el orden de izquierda a derecha, a excepción de la exponenciación donde se asume un orden de derecha a izquierda. Reglas 1.- Dar jerarquías o precedencias sin afectar a la expresión 2.- De acuerdo a las jerarquías iniciar las conversiones 3.- Las conversiones se harán de la siguiente manera: a) El orden de losoperandos no cambia, solo el de los operadores b) Los paréntesis que aparezcan el la expresión original, no aparecerán en las conversiones c) El operador irá precedido de los operandos y operadores que del prefijo. En forma contraria funcionará el postfijo. afecten, esto en el caso

En expresiones de postfijo no existen los paréntesis, pero el orden en que se presentan los operadores determina el ordenactual de las operaciones al evaluar la expresión, haciendo en este caso que los paréntesis no sean necesarios. Al hacer las expresiones de infijo a postfijo a simple vista perdemos la habilidad de observar a los operandos asociados con un operador, por lo tanto la notación postfija de la expresión original puede parecer simple si no fuera por el hecho que parece difícil de evaluar.

Lasolución a este problema es la aplicación de un algoritmo para evaluar expresiones en postfijo.

Algoritmo para evaluar expresiones en post fijo 1.- Si no hay más caracteres en la cadena entonces ir al paso # 5 de lo contrario 2.- Lee symb 3.- Si symb = operandos entonces opndstk.Push(symb) de lo contrario opnd2= opndstk.Pop() opnd1= opndstk.Pop() valor=resultado de aplicar symb a opnd1 sobre opnd2opndstk.Push(valor) 4.- ir al paso # 1 5.- Resultado = opndstk.Pop() Donde: opndstk = PILA DE OPERANDOS opnd2 = PRIMER OPERANDO RETIRADO opnd1 = SEGUNDO OPERANDO RETIRADO symb = SIGUIENTE SIMBOLO A LEER Ejemplo: 3-(2*8)+9 = 328*-9+ = -4

Algoritmo de Conversión de notación In fija a Post fija Antes de poder aplicar el algoritmo de evaluación de expresiones postfijas, es necesario poder implementarun convertidor de nomenclatura infija (común) a la nomenclatura postfija, que es con la que opera el algoritmo anterior. A continuación, el algoritmo de conversión: Para nuestro problema una expresión matemática será un medio que permite indicar el orden en que se deben realizar una serie de operaciones para obtener un resultado. Las operaciones se indican mediante operadores, que en nuestro casorepresentan las operaciones suma, resta, producto, división e igualdad, todas ellas operaciones binarias (necesitan exactamente dos argumentos para poderse evaluar). Existen varias notaciones para representar expresiones matemáticas, que se diferencian en el orden en que se escriben los argumentos (operandos) de los operadores. Las más relevantes son:
   

Notación infija: La notación...