Ver índice de contenidos del libro

17.1. Pilas

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: devuelve True o False segú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ía

17.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"),
  • 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.0

El 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 operandos

El 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álido

El 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.0

El 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.0

El 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.0

El 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.0

Ejercicio 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.

Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.