Una pila es un TAD que tiene las siguientes operaciones (se describe también la acción que lleva adelante cada operación):
__init__: inicializa una pila nueva, vacía.apilar: agrega un nuevo elemento a la pila.desapilar: elimina el tope de la pila y lo devuelve. El elemento que se devuelve es siempre el último que se agreg6.es_vacia: devuelveTrueoFalsesegún si la pila está vacía o no.
El comportamiento de una pila se puede describir mediante la frase "Lo último que se apiló es lo primero que se usa", que es exactamente lo que uno hace con una pila (de platos por ejemplo): en una pila de platos uno sólo puede ver la apariencia completa del plato de arriba, y sólo puede tomar el plato de arriba (si se intenta tomar un plato del medio de la pila lo más probable es que alguno de sus vecinos, o él mismo, se arruine).
Como ya se dijo, al crear un tipo abstracto de datos, es importante decidir cuál será la representación a utilizar. En el caso de la pila, si bien puede haber más de una representación, por ahora veremos la más sencilla: representaremos una pila mediante una lista de Python.
Sin embargo, para los que construyen programas que usan un TAD vale el siguiente llamado de atención:
17.1.1. Pilas representadas por listas
Definiremos una clase Pila con un atributo, items, de tipo lista, que
contendrá los ele-mentos de la pila. El tope de la pila se encontrará
en la última posición de la lista, y cada vez que se apile un nuevo
elemento, se lo agregará al final.
El método __init__ no recibirá parámetros adicionales, ya que
deberá crear una pila vacía (que representaremos por una lista vacía):
Advertencia Al usar esa pila dentro de un programa, deberemos ignorar que se está trabajando sobre una lista: solamente podremos usar los métodos de pila.
Si alguien viola este principio, y usa la representación dentro del programa usuario, termina por recibir el peor castigo imaginable para un/a programador/a: sus programas pueden dejar de funcionar el cualquier momento, tan pronto como quien produce del TAD decida cambiar, aunque sea sutilmente, dicha representación.
class Pila:
""" Representa una pila con operaciones de apilar, desapilar y
verificar si está vacía. """
def __init__(self):
""" Crea una pila vacía. """
# La pila vacía se representa con una lista vacía
self.items=[]El método apilar se implementará agregando el nuevo elemento al final de la lista:
def apilar(self, x):
""" Agrega el elemento x a la pila. """
# Apilar es agregar al final de la lista.
self.items.append(x)Para implementar desapilar, se usará el método pop de lista que hace
exactamente lo requerido: elimina el último elemento de la lista y
devuelve el valor del elemento eliminado. Si la lista está vacía levanta
una excepción, haremos lo mismo, pero cambiaremos el tipo de excepción,
para no revelar la implementación.
def desapilar(self):
""" Devuelve el elemento tope y lo elimina de la pila.
Si la pila está vacía levanta una excepción. """
try:
return self.items.pop()
except IndexError:
raise ValueError("La pila está vacía")Nota Utilizamos los métodos append y pop de las listas de Python, porque
sabemos que estos métodos se ejecutan en tiempo constante. Queremos
que el tiempo de apilar o desapilar de la pila no dependa de la
cantidad de elementos contenidos.
Finalmente, el método para indicar si se trata de una pila vacía.
def es_vacia(self):
""" Devuelve True si la lista está vacía, False si no. """
return self.items == []Construimos algunas pilas y operamos con ellas:
>>> from clasePila import Pila
>>> p = Pila()
>>> p.es_vacia()
True
>>> p.apilar(1)
>>> p.es_vacia()
False
>>> p.apilar(5)
>>> p.apilar("+")
>>> p.apilar(22)
>>> p.desapilar()
22
>>> p
<clasePila.Pila instance at 0xb7523f4c>
>>> q=Pila()
>>> q.desapilar()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "clasePila.py", line 24, in desapilar
raise ValueError("La pila está vacía")
ValueError: La pila está vacía17.1.2. Uso de pila: calculadora científica
La famosa calculadora portátil HP-35 (de 1972) popularizó la notación
polaca inversa (o notación prefijo) para hacer cálculos sin necesidad
de usar paréntesis. Esa notación, inventada por el lógico polaco Jan
Lukasiewicz en 1920, se basa en el principio de que un operador
siempre se escribe a continuación de sus operandos. La operación (5 −
3) + 8 se escribirá como ``5 3 - 8 +, que se interpretará como: "restar
3 de 5, y al resultado sumarle 8".
Es posible implementar esta notación de manera sencilla usando una pila de la siguiente manera, a partir de una cadena de entrada de valores separados por blancos:
- Mientras se lean números, se apilan.
- En el momento en el que se detecta una operación binaria
+,-,*,/o%se desapilan los dos últimos números apilados, se ejecuta la operación indicada, y el resultado de esa operación se apila. - Si la expresión está bien formada, tiene que quedar al final un único número en la pila (el resultado).
- Los posibles errores son:
- Queda más de un número al final (por ejemplo si la cadena de entrada
fue
"5 3"),
- Queda más de un número al final (por ejemplo si la cadena de entrada
fue
- Ingresa algún caracter que no se puede interpretar ni como número ni
como una de las cinco operaciones válidas (por ejemplo si la
cadena de entrada fue
"5 3 &") - No hay suficientes operandos para realizar la operación (por ejemplo
si la cadena de entrada fue
"5 3 - +").
La siguiente es la estrategia de resolución:
Dada una cadena con la expresión a evaluar, podemos separar sus
componentes utilizando el método split(). Recorreremos luego la lista
de componentes realizando las acciones indicadas en el párrafo
anterior, utilizando una pila auxiliar para operar. Si la expresión
está bien formada devolveremos el resultado, de lo contrario
levantaremos una excepción (devolveremos None).
En el código 17.1 está la implementación de la calculadora descripta. Veamos algunos casos de prueba:
El caso de una expresión que es sólo un número (es correcta):
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 5
DEBUG: 5
DEBUG: apila 5.0
5.0El caso en el que sobran operandos:
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: error pila sobran operandos
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "calculadora_polaca.py", line 64, in main
print calculadora_polaca(elementos)
File "calculadora_polaca.py", line 59, in calculadora_polaca
raise ValueError("Sobran operandos")
ValueError: Sobran operandosEl caso en el que faltan operandos:
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 %
DEBUG: 4
DEBUG: apila 4.0
DEBUG: %
DEBUG: desapila 4.0
DEBUG: error pila faltan operandos
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "calculadora_polaca.py", line 64, in main
print calculadora_polaca(elementos)
File "calculadora_polaca.py", line 37, in calculadora_polaca
raise ValueError("Faltan operandos")
ValueError: Faltan operandos# Código 17.1: calculadora_polaca.py: Una calculadora polaca inversa
#!/usr/bin/env python
#encoding: latin1
from clasePila import Pila
def calculadora_polaca(elementos):
""" Dada una lista de elementos que representan las componentes de
una expresión en notacion polaca inversa, evalúa dicha expresión.
Si la expresion está mal formada, levanta ValueError. """
p = Pila()
for elemento in elementos:
print "DEBUG:", elemento
# Intenta convertirlo a número
try:
numero = float(elemento)
p.apilar(numero)
print "DEBUG: apila ", numero
# Si no se puede convertir a número, debería ser un operando
except ValueError:
# Si no es un operando válido, levanta ValueError
if elemento not in "+-*/ %" or len(elemento) != 1:
raise ValueError("Operando inválido")
# Si es un operando válido, intenta desapilar y operar
try:
a1 = p.desapilar()
print "DEBUG: desapila ",a1
a2 = p.desapilar()
print "DEBUG: desapila ",a2
# Si hubo problemas al desapilar
except ValueError:
print "DEBUG: error pila faltan operandos"
raise ValueError("Faltan operandos")
if elemento == "+":
resultado = a2 + a1
elif elemento == "-":
resultado = a2 - a1
elif elemento == "*":
resultado = a2 * a1
elif elemento == "/":
resultado = a2 / a1
elif elemento == " %":
resultado = a2 % a1
print "DEBUG: apila ", resultado
p.apilar(resultado)
# Al final, el resultado debe ser lo único en la Pila
res = p.desapilar()
if p.esPilaVacia():
return res
else:
print "DEBUG: error pila sobran operandos"
raise ValueError("Sobran operandos")
def main():
expresion = raw_input("Ingrese la expresion a evaluar: ")
elementos = expresion.split()
print calculadora_polaca(elementos)El caso de un operador inválido:
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5 &
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: &
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "calculadora_polaca.py", line 64, in main
print calculadora_polaca(elementos)
File "calculadora_polaca.py", line 26, in calculadora_polaca
raise ValueError("Operando inválido")
ValueError: Operando inválidoEl caso de 4 % 5:
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5 %
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: %
DEBUG: desapila 5.0
DEBUG: desapila 4.0
DEBUG: apila 4.0
4.0El caseo de (4 + 5) * 6:
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5 + 6 *
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: +
DEBUG: desapila 5.0
DEBUG: desapila 4.0
DEBUG: apila 9.0
DEBUG: 6
DEBUG: apila 6.0
DEBUG: *
DEBUG: desapila 6.0
DEBUG: desapila 9.0
DEBUG: apila 54.0
54.0El caso de 4 * (5 + 6):
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5 6 + *
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: 6
DEBUG: apila 6.0
DEBUG: +
DEBUG: desapila 6.0
DEBUG: desapila 5.0
DEBUG: apila 11.0
DEBUG: *
DEBUG: desapila 11.0
DEBUG: desapila 4.0
DEBUG: apila 44.0
44.0El caso de (4 + 5) * (3 + 8):
>>> calculadora_polaca.main()
Ingrese la expresion a evaluar: 4 5 + 3 8 + *
DEBUG: 4
DEBUG: apila 4.0
DEBUG: 5
DEBUG: apila 5.0
DEBUG: +
DEBUG: desapila 5.0
DEBUG: desapila 4.0
DEBUG: apila 9.0
DEBUG: 3
DEBUG: apila 3.0
DEBUG: 8
DEBUG: apila 8.0
DEBUG: +
DEBUG: desapila 8.0
DEBUG: desapila 3.0
DEBUG: apila 11.0
DEBUG: *
DEBUG: desapila 11.0
DEBUG: desapila 9.0
DEBUG: apila 99.0
99.0Ejercicio 17.1. Si se oprime la tecla <BACKSPACE> (o <←>) del
teclado, se borra el último caracter ingresado. Construir una función
visualizar para modelar el tipeo de una cadena de caracteres desde un
teclado:
La función recibe una cadena de caracteres con todo lo que el usuario
ingresó por teclado (incluyendo <BACKSPACE> que se reconoce como
\b), y devuelve el texto tal como debe presentarse (por ejemplo,
visualizar("Hola\b chau") debe devolver 'Hola chau').
Atención, que muchas veces la gente aprieta de más la tecla de
<BACKSPACE>, y no por eso hay que cancelar la ejecución de toda la
función.
17.1.3. ¿Cuánto cuestan los métodos?
Al elegir de una representación debemos tener en cuenta cuánto nos costarán los métodos implementados. En nuestro caso, el tope de la pila se encuentra en la última posición de la lista, y cada vez que se apila un nuevo elemento, se lo agregará al final.
Por lo tanto se puede implementar el método apilar mediante un append
de la lista, que se ejecuta en tiempo constante. También el método
desapilar, que se implementa mediante pop de lista, se ejecuta en
tiempo constante.
Vemos que la alternativa que elegimos fue barata.
Otra alternativa posible hubiera sido agregar el nuevo elemento en la
posición 0 de la lista, es decir implementar el método apilar mediante
self.items.insert(0,x) y el método desapilar mediante del self.items[0].
Sin embargo, ésta no es una solución inteligente, ya
que tanto insertar al comienzo de la lista como borrar al comienzo de
la lista consumen tiempo proporcional a la longitud de la lista.
Ejercicio 17.2. Diseñar un pequeño experimento para verificar que la implementación elegida es mucho mejor que la implementación con listas en la cual el elemento nuevo se inserta al principio de la lista.
Ejercicio 17.3. Implementar pilas mediante listas enlazadas. Analizar el costo de los métodos a utilizar.