Algoritmos y Programas – Año 2012

Práctica 3

Encapsulamiento y Abstracción

Objetivos: • Acostumbrarse a utilizar las operaciones para acceder a las estructuras de datos y no

violar el encapsulamiento. • Acostumbrarse a reutilizar el código y no volver codificar desde cero. • Implementar y usar de las estructuras de datos: pila y cola

1) Sea la siguiente especificación del TAD Pila:

• push(pila,elemento): Agrega un elemento a la Pila. • pop(pila): Extraer un elemento de pila. El elemento devuelto siempre es el último

que se añadió.• isEmpty(pila): Retorna si pila está vacía. • top(pila): Retorna el elemento al tope de la pila sin sacarlo de ella. • size(pila): Retorna la cantidad de elementos que tiene pila.• reverse(pila): Retorna pila con los elementos en posición invertida.• pushAll(pila1, pila2): Agrega todos los elementos de pila2 en pila1.

Implementar el TAD Pila en Python.

2) Escriba una función que reciba una cadena y la invierta utilizando una Pila.

3) (A entregar) Sea la siguiente especificación del TAD Cola: • new(): retorna una nueva cola• push(cola, elemento): agrega un nuevo elemento a la cola• pop(cola): saca un elemento del principio de la cola• isEmpty(cola): retorna si la cola está vacía• first(cola): retorna el elemento al principio de la cola• size (cola): retorna la longitud de la cola• reverse(cola): Retorna cola con los elementos en posición invertida.• pushAll(cola1, cola2): agrega todos los elementos de cola2 en cola1

Implementar el TAD Cola en Python.

4) Utilizando el TAD Cola provisto por la cátedra (archivo Cola.pyc) y sabiendo que se encuentran definidas las operaciones antes descriptas, escriba una función llamada sumarColas que reciba 2 Colas de enteros y devuelva una Cola con sus elementos sumados.

5) (A entregar) Ahora reescriba la misma función pero en forma recursiva.

Algoritmos y Programas – Año 2012

6) Recuerdan el siguiente ejercicio de la práctica 1?

Escriba en Python un módulo que lea del teclado una cadena de caracteres e imprima si la cadena esta balanceada o no.

Decimos que una cadena de caracteres S está balanceada si tiene alguna de las siguientes formas:S = ‘’ S es el string de longitud cero.

S = ‘(T)’

S = ‘[T]’

S = ‘{T}’

S = ‘TU’

Donde ambos T y U son cadenas balanceadas. Por ejemplo, ‘{[ ( ) ] }’ está balanceada, pero ‘ ( [ ) ]’ no lo está.

Existe una forma más fácil de hacerlo con Pilas o Colas? De ser así, implementar la nueva solución.

7) Evaluación de expresiones postfijas :Una expresión aritmética en notación postfija (o notación polaca inversa) es una secuencia formada por símbolos de dos tipos diferentes: operadores (para simplificar, consideraremos únicamente los operadores aritméticos binarios +, -, * y /) y operandos (valores de 0 a 9). Cada operador se escribe detrás de sus operandos. Por ejemplo, a la expresión siguiente, escrita en la notación habitual (infija):

4 * 6 / 3 le corresponde la siguiente expresión en notación postfija:

4 6 * 3 /

Escriba una función evaluarPostfija que dada un expresión en notación postfija devuelva el resultado de su evaluación. En el ejemplo anterior el resultado evaluar la expresión sería 8.