• Author / Uploaded
• Fred Bello

Citation preview

UNIVERSIDAD ANDINA DEL CUSCO INGENIERIA DE SISTEMAS

EXPRESIONES ARITMETICAS CON PILAS (NOTACIONES POLACAS)

ALUMNOS

: FREDY BELLO PACCO

SEMESTRE

: IlI

ASIGNATURA

: Algorítmica y laboratorio de programación II

CUSCO – PERU 2015

INTRODUCCION Todos hemos utilizado alguna vez una calculadora. La gran mayoría de ellas, incluida la que viene por defecto en nuestro sistema operativo favorito, utilizan un sistema denominado “notación de infijo”, en el que los operadores separan los operandos. Sin embargo, existe otra forma de realizar cálculos llamada “notación de postfijo” o “ Notación Polaca Inversa” en la que primero se introducen los operandos y después el operador que va a realizar los cálculos sobre ellos. Desde 1968, este sistema ha sido aplicado en una gran cantidad de calculadoras

EXPRESIONES ARITMETICAS CON PILAS Una expresión aritmética esta formada por operandos y operadores, como por ejemplo (a+b) - c*d. En este caso +, -, * son los operadores y a, b, c, d los operandos. Los operandos pueden ser valores, variables o incluso otras expresiones, mientras que los operadores son los conocidos de las expresiones matemáticas, por lo que el resultado puede ser de tipo numérico o variables. La forma habitual que tenemos de escribir las operaciones matemáticas es poniendo el operador entre dos operando, y que puede llevar paréntesis para encerrar subexpresiones con mayor prioridad en cada operación, al igual que los operadores tienen cada uno una prioridad diferente, ya que, por ejemplo, la multiplicación * tienen prioridad sobre la suma +.Veamos el grado de prioridad de estos operadores. 1. Paréntesis ( ) 2. Potencial ^ 3. Producto/cociente * / 4. Suma/resta + También hay que tener en cuenta que cuando se evalúa una operación se hace de izquierda a derecha, excepto en el caso de las potencias, que se hace de derecha a izquierda. Esta forma de escribir una expresión, se denomina notación usual o infija. Existen otras formas de escribir expresiones aritméticas, en el que se diferencian por la situación de los operadores respecto de los operandos. La forma en la que los operadores se colocan delante de los operandos es conocida como notación polaca o prefija. Vemos un ejemplo: Notación infija: a*b/(a+c) Notación polaca: */ab+ac Además de estas existe otro tipo de notación, el que a nosotros más nos interesa, que es la notación postfija, en la que se colocan los operadores a 9 continuación de los operandos, y en la cuál no existe jerarquía en las operaciones. Las diferentes formas de escribir una misma expresión algebraica dependen de la ubicación de los operadores respecto a los operandos. Es importante tener en cuenta que tanto en la notación prefija como en la postfija no son necesarios los paréntesis para cambiar el orden de evaluación. Veamos algunos ejemplos de notación infija respecto de la notación postfija

NOTACIÓN INFIJA 2*(3+8/(6-4)) 3+2*7-1 1*2*3*4+5

NOTACIÓN POSTFIJA 23864-/+* 327*+112*3*4*5+

Vemos que hacemos lo mismo que haríamos en notación infija y no hemos tenido que acudir a paréntesis ni a jerarquías de operaciones. Por eso la evaluación de expresiones postfijas es muy fácil de implementar. A la hora de evaluar una expresión aritmética de notación infija, tendremos que realizar dos pasos: • Transformación de notación infija a notación postfija. • Evaluación de la notación postfija. Para ello tendremos que emplear un tipo TDA pila. Veamos que ocurre en cada uno de los casos. CORRESPONDENCIA DE DELIMITADORES La pila es muy útil en situaciones cuando los datos deben almacenarse y luego recuperarse en orden inverso. Una aplicación de la pila es la correspondencia de delimitadores en un programa. Esto es un ejemplo importante debido a que la correspondencia de delimitadores es parte de cualquier compilador. Ningún programa se considera correcto si los delimitadores no tienen su pareja. Ejemplo: while (m