Informatica

Estructura de Datos y de la Información Pilas y expresiones aritméticas
LIDIA Laboratorio de Investigación y desarrollo en Inteligencia Artificial Departamento de Computación Universidade da Coruña, España

Índice
1. Introducción
• • • • Expresión aritmética Notaciones infija, prefija y postfija Evaluación de una notación postfija Conversión de infija a postfija

2. Algoritmos

2Pilas
Notación Prefija, Infija y Postfija
• Expresión aritmética:
– Formada por operandos y operadores: A*B / (A+C) – Operandos: variables que toman valores enteros o reales – Operadores: Paréntesis () Nivel mayor de prioridad
Potencia Multiplicación / División Suma / Resta ^ * / + Nivel menor de prioridad

– En caso de igualdad de prioridad
• Son evaluados de izquierda a derecha (se evalúaprimero el que primero aparece) ⇒ 5*4/2 = (5*4)/2 = 10 • Cuando aparecen varios operadores de potenciación juntos la expresión se evalúa de derecha a izquierda ⇒ 2^3^2 = 2^(3^2) = 2^9 = 512

• Notación Infija
– Es la notación ya vista que sitúa el operador entre sus operandos. – Ventaja: Es la forma natural de escribir expresiones aritméticas – Inconveniente: Muchas veces necesita de paréntesispara indicar el orden de evaluación: A*B/(A+C) ≠ A*B/A+C
3

Pilas
Notación Prefija, Infija y Postfija
• Notación Prefija o Polaca
– En 1920 un matemático de origen polaco, Jan Lukasiewicz, desarrollo un sistema para especificar expresiones matemáticas sin paréntesis. – Esta notación se conoce como notación prefija o polaca (en honor a la nacionalidad de Lukasiewicz) y consiste en situar aloperador ANTES que los operandos. – Ejemplo: la expresión infija A*B / (A+C) se representaría en notación prefija como: /*AB+AC

• Notación Postfija o Polaca Inversa
– La notación postfija o polaca inversa es una variación de la notación prefija de forma que el operador de pone DESPUÉS de los operandos. – Ejemplo: la expresión infija A*B / (A+C) se representaría en notación postfija como:AB*AC+/ – Ventajas:
• La notación postfija (como la prefija) no necesita paréntesis. • La notación postfija es más utilizada por los computadores ya que permite una forma muy sencilla y eficiente de evaluar expresiones aritméticas (con pilas).
4

Pilas
Evaluación de una Notación Postfija
• Pseudocódigo
1. Inicializar la pila 2. Repetir hasta que no haya caracteres en la expresión a evaluar
2.1Obtener el siguiente item de la expresión 2.2 Si el elemento es un operando se mete en la pila 2.3 Si el elemento es un operador (denominado &) entonces:
2.3.1 Se extraen los dos elementos superiores de la pila, denominados Op2 y Op1 respectivamente. 2.3.2 Se evalúa el resultado de Op1 & Op2 y se almacena en Z 2.3.3 Se introduce Z en la cima de la pila

3. Obtener el valor de la expresión dela cima de la pila

5

Pilas
Evaluación de una Notación Postfija
• Ejemplo:
– Expresión aritmética infija: – Expresión aritmética postfija: – Valores A=4, B=5 y C=6: A*B / (A+C) AB*AC+/ 45*46+/
Cima Carácter leído Acción 4 Meter(4) 5 Meter(5) Op2=Sacar → 5 Op1=Sacar → 4 * 4 * 5 = 20 Meter(20) 4 Meter(4) 6 Meter(6) Op2=Sacar → 6 Op1=Sacar → 4 + 4 + 6 = 10 Meter(10) Op2=Sacar → 10 Op1=Sacar→ 20 / 20 / 10 = 2 Meter(2) Fin cadena Fin evaluación Pila 4 5, 4 20 4, 20 6, 4, 20 10, 20

2 2

6

Pilas
Evaluación de una Notación Postfija
• Código:
– Precondición: La expresión postfija es correcta y consiste en un string donde cada carácter es o un operando o un operador. – Utilizamos una pila que almacena valores reales
function EvaluaPostfija (ExpPostfija: string): real; var P:tPila; Op1, Op2, Z: real; i: integer; begin PilaVacia(P); for i:=1 to Length(ExpPostFija) do // Recorremos la expresion postfija begin // Si es un operando lo metemos en la pila if ExpPostfija[i] in ['0'..'9'] then Meter(P,StrToInt(ExpPostfija[i])) else begin // Si es un operador sacamos los dos primeros elementos Cima(P,Op2);Sacar(P); // de la pila y realizamos la operación indicada con...