1 EJERCICIOS Listas, Pilas y ColasFacultad de Ciencias y Tecnología Departamento de Computación

2 Enunciado: Intercambiar el tope y el fondo de una pilaÑ F fondo

3 Análisis de la soluciónT TOPE F Ñ P fondo A T Pila original Pila Auxiliar

4 Análisis de la soluciónT TOPE F Ñ P fondo A Pila original Pila Auxiliar

5 Análisis de la soluciónTOPE F Ñ P fondo A T Pila original Pila Auxiliar

6 Análisis de la soluciónT TOPE F Ñ P fondo Pila original Pila Auxiliar

7 Análisis de la soluciónP A T TOPE F Ñ fondo Pila original Pila Auxiliar

8 Análisis de la soluciónÑ P A T TOPE F Pila original Pila Auxiliar

9 Análisis de la soluciónF Ñ P A T TOPE Pila original Pila Auxiliar

10 Análisis de la soluciónF Ñ P A T TOPE Pila original Pila Auxiliar

11 Análisis de la soluciónF T TOPE Ñ P A Pila original Pila Auxiliar

12 Análisis de la soluciónF Ñ P A TOPE T Pila original Pila Auxiliar

13 Análisis de la soluciónF TOPE Ñ P T A Pila original Pila Auxiliar

14 Análisis de la soluciónF TOPE P Ñ T A Pila original Pila Auxiliar

15 Análisis de la soluciónF TOPE A P Ñ T Pila original Pila Auxiliar

16 Análisis de la soluciónTOPE F A P Ñ T Pila original Pila Auxiliar

17 Algoritmo P1,P2: Pila[Elemento]; Top,Fondo:Elemento; Vaciap(p2);TopTope(p1); Si ( EsVacia(p1)) Entonces Desapilar(p1); Mientras( EsVacia(p1)) Hacer FondoTope(p1) Apilar(p2,Fondo); FMientras //Creación de la pila con el tope y fondo invertidos Apilar(p1,Top) Si ( EsVacia(p2)) Entonces Desapilar(p2); Mientras ( EsVacia(p2))Hacer Apilar(p1,Tope(p2)) Desapilar(p2) Apilar(p1,Fondo) Sino Escribir(“Error, pila vacia”) Fsi Escribir(“Error, pila vacia”); fsi

18 Enunciado: Modificar una lista eliminando los n primeros elementos Eliminar los primeros 3 elementos

19 Enunciado: Modificar una lista eliminando los n primeros elementos

20 Enunciado: Modificar una lista eliminando los n primeros elementos

21 Enunciado: Modificar una lista eliminando los n primeros elementos

22 Si (n<=Longitud(L1) Entonces Mientras(i<=n   EsVacia(L1) Hacer Algoritmo L1: Lista; i,n : entero; Leer(n); ***Suponemos que la lista está creada y tiene elementos i1 Si (n<=Longitud(L1) Entonces Mientras(i<=n   EsVacia(L1) Hacer Resto(L1); ii+1; fMientras

23 Enunciado: Intercambiar las posiciones p y q de una lista 2 5

24 Análisis de la solución 2 5 25 44 Se obtienen los elementos de las posiciones p y q a intercambiar

25 Análisis de la solución 2 5 44 Eliminando el elemento de la posición p, en este caso 2

26 Análisis de la solución 2 5 Insertando en la posición p el elemento que estaba en q

27 Análisis de la solución 2 5 25 Eliminando de la posición q el elemento allí colocado

28 Análisis de la solución 2 5 Insertando en la posición q el elemento que estaba en p

29 Algoritmo L: Lista[Elemento]; p,q: entero; Elem_p,Elem_q: Elemento;Leer(p,q); Si (EsVacia(L)  p<=Longitud(L)  q<=Longitud(L)) Entonc Elem_pConsultar(L,p); Elem_qConsultar(L,q); Eliminar(L,p) Insertar(L,Elem_q,p) Eliminar(L,q) Insertar(L,Elem_p,q) Sino Escribir(“Error, posiciones invalidas o lista vacia”); Fsi

30 Elaborar un algoritmo que evalúe una expresión en notación polaca inversa (postfija)

31 Análisis de la SoluciónUna expresión en notación Infija (usual) es de la forma: (2*5) + 3 =

32 Análisis de la SoluciónY su evaluación se realiza de izquierda a derecha de acuerdo a la prioridad de los operadores (2*5) + 3 =

33 Análisis de la SoluciónY su evaluación se realiza de izquierda a derecha de acuerdo a la prioridad de los operadores (2*5) + 3 = 13

34 Análisis de la SoluciónInfija Postfija (2*5) * 3 +

35 Análisis de la SoluciónEvaluaremos expresiones en notación postfija usando pilas

36 Análisis de la SoluciónPara evaluar una expresión en notación postfija: Se apilan los operandos Cuando aparece un operador, se desapilan dos operandos y el resultado, también se apila

37 Análisis de la SoluciónDada la expresión en postfija: 2 5 * 3 + Se lee el operando 2 y se apila TOPE 2

38 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se lee el operando 5 y se apila 2 TOPE 5

39 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se lee el Siguiente elemento: Es un operador TOPE 2 5

40 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se desapilan dos operandos 2 5 TOPE x2

41 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se desapilan dos operandos 5 2 x2 x1 TOPE

42 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se operan entre si * 5 2 x2 x1 TOPE

43 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + El resultado se apila * 5 2 x2 x1 10 TOPE

44 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + El resultado se apila * 5 2 TOPE 10

45 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se lee el siguiente elemento: Es un operando, Por lo tanto se apila TOPE 10

46 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se lee el siguiente elemento: Es un operando, Por lo tanto se apila TOPE 3 10

47 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se lee el siguiente elemento: Es un operador, TOPE 3 10

48 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se desapilan 2 operandos TOPE 10 3 x2

49 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se desapilan 2 operandos 3 10 TOPE x2 x1

50 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + Se operan los elementos: + 3 10 TOPE x2 x1

51 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + El resultado se apila + 3 10 x2 x1 TOPE

52 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + El resultado se apila + 3 10 x2 x1 13 TOPE

53 Análisis de la SoluciónEvaluando la expresión: 2 5 * 3 + El resultado se apila + 3 10 x2 x1 TOPE 13

54 Algoritmo Variables p: Pila[Elemento] s:cadena; x1,x2: Entero;c: carácter; Leer(s); **Cadena que contiene la expresion (en postfija) Vaciap (p);

55 Algoritmo Mientras (Longitud(s)>0) Hacer cPrimero(s);Si (EsNumero(c)) Entonces Selección(c) caso ‘+’: x2Tope(p); Desapilar(p); x1Tope(p) Apilar(p,x1+x2); . fSeleccion Sino Apilar(p,c); Fsi Resto (s) fMientras Escribir(“La expresion evaluada fue:”,Tope(p));

56 Algoritmo Casos de la selección (división) Selección(c)caso ’/’: x2Tope(p); Desapilar(p); x1Tope(p); Si(x20) Entonces Apilar(P,x1/x2) Sino Escribir(“Error, division por cero) fsi fSeleccion

57 Dada una expresión en notación infija, llevarla a notación postfija usando pilas

58 Procedimiento Dada la expresión en notacion infija (5*4)+3Al llevarla a notación postfija: 5 4 * 3 + Las expresiones en postfija, no tienen paréntesis.

59 Procedimiento Dada una cadena, que contiene una expresión en notación infija, la idea es leer caracter a caracter de la cadena de entrada y tomar en cuenta lo siguiente:

60 Procedimiento Si el caracter es un operando, inmediatamente se añade a la expresión resultado. Si es un operador, se apila inmediatamente, de igual forma se van a apilar los paréntesis izquierdos. Si el elemento leído, es un paréntesis derecho, se sacan elementos de la pila (operadores) hasta que aparece un paréntesis izquierdo (correspondiente), el cual se desapila pero no se añade a la expresión resultado.

61 Procedimiento Si se ve cualquier otro símbolo en la entrada (‘+’, ’*’ , ’(‘ )´, entonces se sacan elementos de la pila hasta encontrar uno de menor prioridad. (Por lo que no se saca un ‘(‘ de la pila hasta que se vea su correspondiente paréntesis derecho ‘)’ en la cadena de entrada. Para los propósitos de esta operación + tiene la menor prioridad y ‘(’ la más alta, cuando se termina de sacar de la pila, se mete el operando en ella. Por último, si se llega al final de la entrada, se saca todo lo que está en la pila enviando cada elemento a la salida.

62 Ejemplo Llevar a postfija la siguiente expresión en notación infija:a + b * c + (d * e + f) * g

63 Ejemplo a + b * c + (d * e + f) * g Primer carácter: es un operandoExpresión en infija a + b * c + (d * e + f) * g Primer carácter: es un operando Por lo tanto se añade a la Expresión resultado: a

64 Ejemplo + + b * c + (d * e + f) * g Siguiente carácter: es un operadorExpresión en infija + b * c + (d * e + f) * g Siguiente carácter: es un operador Por lo tanto se apila a TOPE +

65 Ejemplo + b * c + (d * e + f) * g Siguiente carácter: es un operando,Expresión en infija b * c + (d * e + f) * g Siguiente carácter: es un operando, Se añade a la expresión resultado: a b TOPE +

66 Ejemplo * + * c + (d * e + f) * g Siguiente carácter: es un operador,Expresión en infija * c + (d * e + f) * g Siguiente carácter: es un operador, Por lo que se apila a b TOPE * +

67 Ejemplo * + c + (d * e + f) * g Siguiente carácter: operando,Expresión en infija c + (d * e + f) * g Siguiente carácter: operando, Se añade a la expresión resultado: a b c TOPE * +

68 Ejemplo * + + (d * e + f) * g Siguiente carácter: ’+’operando,Expresión en infija + (d * e + f) * g Siguiente carácter: ’+’operando, Caso Especial a b c Se desapilan operadores hasta conseguir uno de menor o igual prioridad al operador leído y se envían a la expresión resultado TOPE * +

69 Ejemplo + + (d * e + f) * g Caso Especial a b c * Expresión en infijaSe desapilan operadores hasta conseguir uno de menor o igual prioridad al operador leído y se envían a la expresión resultado TOPE +

70 Ejemplo + (d * e + f) * g Caso Especial a b c * + Expresión en infijaSe desapilan operadores hasta conseguir uno de menor o igual prioridad al operador leído y se envían a la expresión resultado TOPE

71 Ejemplo + + (d * e + f) * g Caso Especial a b c * +Expresión en infija + (d * e + f) * g Caso Especial a b c * + Luego se apila el operador leído TOPE +

72 Ejemplo + ( (d * e + f) * g Siguiente carácter: un paréntesis:Expresión en infija (d * e + f) * g Siguiente carácter: un paréntesis: Se apila. a b c * + TOPE ( +

73 Ejemplo + ( d * e + f) * g Siguiente carácter: un operando,Expresión en infija d * e + f) * g Siguiente carácter: un operando, Se añade a la expresión a b c * + d TOPE ( +

74 Ejemplo + * ( * e + f) * g Siguiente carácter: operador *Expresión en infija * e + f) * g Siguiente carácter: operador * Se apila aun cuando es de menor Prioridad que ‘(‘ a b c * + d TOPE “Los paréntesis no pueden desapilarse hasta que no aparezca un paréntesis derecho” * ( +

75 Ejemplo + * ( e + f) * g Siguiente carácter: ‘e’ seExpresión en infija e + f) * g Siguiente carácter: ‘e’ se Añade a la expresión a b c * + d e TOPE “Los paréntesis no pueden desapilarse hasta que no aparezca un paréntesis derecho” * ( +

76 Ejemplo + * ( + f) * g Siguiente carácter: + , sacamos *Expresión en infija + f) * g Siguiente carácter: + , sacamos * De la pila y lo añadimos a la expresion, Apilamos + a b c * + d e * TOPE * ( +

77 Ejemplo + ( + f) * g Siguiente carácter: + , sacamos *Expresión en infija + f) * g Siguiente carácter: + , sacamos * De la pila y lo añadimos a la expresion, Apilamos + a b c * + d e * TOPE ( +

78 Ejemplo + + ( + f) * g Siguiente carácter: + , sacamos *Expresión en infija + f) * g Siguiente carácter: + , sacamos * De la pila y lo añadimos a la expresion, Apilamos + a b c * + d e * TOPE + ( +

79 Ejemplo + + ( f) * g Siguiente carácter: f, se añade a laExpresión en infija f) * g Siguiente carácter: f, se añade a la Expresión resultado a b c * + d e * f TOPE + ( +

80 Ejemplo + + ( ) * g Siguiente carácter: ‘)’ se desapilanExpresión en infija ) * g Siguiente carácter: ‘)’ se desapilan Todos los operadores hasta que aparezca Un paréntesis izquierdo a b c * + d e * f TOPE + ( +

81 Ejemplo + ( ) * g Siguiente carácter: ‘)’ se desapilanExpresión en infija ) * g Siguiente carácter: ‘)’ se desapilan Todos los operadores hasta que aparezca Un paréntesis izquierdo a b c * + d e * f + TOPE ( +

82 Ejemplo + ) * g Siguiente carácter: ‘)’ se desapilanExpresión en infija ) * g Siguiente carácter: ‘)’ se desapilan Todos los operadores hasta que aparezca Un paréntesis izquierdo a b c * + d e * f + TOPE +

83 Ejemplo * + * g Siguiente carácter: *, se apila a b c * + d e * f +Expresión en infija * g Siguiente carácter: *, se apila a b c * + d e * f + TOPE * +

84 Ejemplo * + g Siguiente carácter: g, se añade a la Expresión resultadoExpresión en infija g Siguiente carácter: g, se añade a la Expresión resultado a b c * + d e * f + g TOPE * +

85 Ejemplo * + Al quedar la cadena vacía, se desapilanExpresión en infija Al quedar la cadena vacía, se desapilan Los operadores y se añaden a la expresión resultado. a b c * + d e * f + g TOPE * +

86 Ejemplo + Al quedar la cadena vacía, se desapilanExpresión en infija Al quedar la cadena vacía, se desapilan Los operadores y se añaden a la expresión resultado. a b c * + d e * f + g * TOPE +

87 Ejemplo Al quedar la cadena vacía, se desapilanExpresión en infija Al quedar la cadena vacía, se desapilan Los operadores y se añaden a la expresión resultado. a b c * + d e * f + g * + TOPE

88 Ejercicio Propuesto Dada una cadena que contiene una expresión en notación infija, elabore un algoritmo que obtenga una expresión equivalente en notación Postfija. Use pilas.