Cap. 25 - Pilas (Stacks)

25.1) Tipos de datos abstractos

Los tipos de datos que hemos visto hasta ahora son todos concretos, en el sentido de que hemos especificado por completo cómo están implementados. - Por ejemplo, la clase Carta representa una carta usando dos enteros. - Como discutimos en su momento, esa no es la única forma posible de representar una carta: hay muchas implementaciones alternativas. Un TDA o Tipo de Datos Abstracto especifica un conjunto de operaciones (o métodos) y la semántica de dichas operaciones (lo que hacen), pero no especifica la implementación de las operaciones. Eso es lo que lo hace abstracto. ¿Por qué es útil? 1. El poder denotar las operaciones necesarias sin tener que pensar en cómo implementarlas simplifica la tarea de especificar un algoritmo. 2. Dado que suele haber muchas formas de implementar un TDA, podría ser útil escribir un algoritmo que pueda ser utilizado con cualquiera de las implementaciones. 3. Los TDAs bien conocidos, como el TDA Pila (Stack) de este capítulo, vienen frecuentemente implementados en librerías estándar de forma que puedan ser escritos una vez y utilizados por varios programadores. 4. Las operaciones de los TDAs proveen un lenguaje común de alto nivel para especificar y hablar a propósito de los algoritmos. Cuando hablamos de TDAs, con frecuencia distinguimos entre el código que usa el TDA, llamado el código cliente, y el código que implementa el TDA, llamado el código implementador/proveedor.

25.2) El TDA Pila (Stack)

En este capítulo veremos un TDA común, la pila (stack). - Una pila es una colección, lo que significa que es una estructura de datos que contiene varios elementos. - Otras colecciones que hemos visto son los diccionarios y las listas. Un TDA se define por las operaciones que se pueden hacer sobre él, lo cual se conoce como su interfaz. La interfaz de un stack incluye las operaciones siguientes: __init__ Inicializa una nueva pila vacía. push Agrega un nuevo elemento a la pila. pop Quita y retorna un elemento de la pila. Este elemento es siempre el último que se agregó en la pila. es_vacía Verifica si la pila está vacía. Una pila es a veces llamada una estructura de datos LIFO ("Last In, First Out"), porque el último elemento agregado es el primero que se quita.

25.3) Implementando pilas (stacks) con listas de Python

Las operaciones de listas que provee Python son similares a las que definen una pila. - La interfaz no es exactamente igual, pero podemos escribir código que traduzca del TDA Pila (Stack) a las operaciones incorporadas. Este código se llama una implementación del TDA Pila (Stack). - En general, una implementación es un conjunto de métodos que satisfacen los requerimientos sintácticos y semánticos de una interfaz. Aquí hay una implementación del TDA Pila (Stack) que usa una lista de Python: class Pila: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def es_vacia(self): return (self.items == []) Un objeto Pila contiene un atributo llamado items que es la lista de items de la pila. - El método de inicialización asigna a items una lista vacía. - Para hacer push de un item en el stack, el método push agrega el item al final del stack (mediante el método append de listas). - Para hacer pop de un item del stack, el método pop utiliza el método homónimo de listas para eliminar y retornar el último elemento de la lista. - Por último, para chequear si la pila está vacía, el método es_vacia compara items con la lista vacía. Una implementación como ésta, en que los métodos consisten en simples llamados a métodos ya existentes, se llama enchapado. - En la vida real, un enchapado es una capa fina de madera de buena calidad que se utiliza para cubrir madera de menor calidad en un mueble. - Los informáticos usan esta metáfora para describir una pequeña pieza de código que oculta los detalles de una implementación y provee una interfaz más simple y estandarizada.

25.4) Push y Pop

Una pila es una estructura general de datos, lo que significa que le podemos agregar cualquier tipo de elemento. - En el ejemplo siguiente, hacemos push de dos enteros y un string en la pila: >>> s = Pila() >>> s.push(54) >>> s.push(45) >>> s.push("+") Podemos usar es_vacia y pop para quitar e imprimir todos los elementos de la pila: while not s.es_vacia(): print(s.pop(), end=" ") El output es + 45 54. En otras palabras, acabamos de usar una pila para imprimir los elementos marcha atrás! - Por supuesto, no es la forma estándar de manejar una lista, pero el uso de una pila facilitó mucho el modo de hacerlo. Deberías comparar estas dos líneas de código con la implementación de print_invertida en el capítulo anterior. - Hay un paralelismo natural entre la versión recursiva de print_invertida y el algoritmo de pila que tenemos aquí. - La diferencia es que print_invertida usa la pila en tiempo real para llevar la cuenta de los nodos mientras va atravesando la lista, y luego las imprime marcha atrás al ir volviendo de la recursión. - El algoritmo basado en la pila hace lo mismo, pero utilizando un objeto Pila en vez de la pila de ejecución en tiempo real.

25.5) Usando una pila (stack) para evaluar expresiones postfix

En muchos lenguajes de programación, las expresiones matemáticas se escriben con el operador entre los dos operandos, como en 1 + 2. Este formato se llama infix. - Una forma alternativa usada por algunas calculadoras se llama postfix. En ésta, el operador sigue a los operandos, como en 1 2 + La razón por la que a veces se usa postfix es que hay una forma natural de evaluar una expresión postfix usando un stack: 1. Comenzando por el principio de la expresión, ir tomando un término (operando u operador) por vez. - Si el término es un operando, ponerlo en la pila. - Si el término es un operador, hacer pop de dos operandos de la pila, ejecutar la operación sobre ellos, y hacer push del resultado en la pila. 2. Para cuando se llega al final de la expresión, debería haber exactamente un operando en la pila. Ese operando es el resultado.

25.6) Parsing

Para implementar el algoritmo descrito en la sección anterior, debemos ser capaces de recorrer un string e ir extrayendo los operandos y operadores que contenga. - Este proceso es un ejemplo de parsing, y los resultados - los trozos individuales que hayamos extraído del string - se llaman tokens. Tal vez recuerdes estas palabras del capítulo 1. Python viene con un método split en los objetos string y también en el módulo re (expresiones regulares). - El método split de un string divide a éste en una lista utilizando un carácter único como delimitador. - Por ejemplo: >>> "Ya es la hora".split(" ") ['Ya', 'es', 'la', 'hora'] En este caso, el delimitador es el carácter espacio, por lo que el string es separado por cada espacio. La función re.split es más poderosa, permitiendo proveer una expresión regular en vez de un delimitador. - Una expresión regular es una forma de expresar un conjunto de strings. Por ejemplo, [A-z] es el conjunto de todas las letras y [0-9] es el conjunto de todos los números. - El operador ^ niega un conjunto, así que [^0-9] es el conjunto de todo lo que no sea un número, que es exactamente el conjunto que queremos usar para subdividir expresiones postfix: >>> import re >>> re.split("([^0-9])", "123+456*/") ['123', '+', '456', '*', '', '/', ''] La lista resultante incluye los operandos 123 y 456 y los operadores * y /. También incluye dos strings vacíos que son insertados después de los operandos. - Nota: parece ser una errata, debería decir "después de los operadores * y /". No se agregan después de "+". Tal vez esto se deba a que * y / no tienen operandos que los separen, pero no lo aclara y habría que revisarlo en la documentación del método split del módulo re.

25.7) Evaluando postfix

Para evaluar una expresión postfix, usaremos el parser de la sección anterior y el algoritmo de la sección que la precedía. - Para mantener las cosas simples, comenzaremos evaluando sólo expresiones que contienen los operadores + y *: def eval_postfix(expr): import re lista_tokens = re.split("([^0-9])", expr) pila = Pila() for token in lista_tokens: if token == "" or token == " ": continue if token == "+": sum = pila.pop() + pila.pop() pila.push(sum) elif token == "*": producto = pila.pop() * pila.pop() pila.push(producto) else: pila.push(int(token)) return pila.pop() La primera condición se ocupa de los espacios y strings vacíos. Las siguientes dos manejan a los operadores. Asumimos, por ahora, que todo lo demás son operadores. - Por supuesto, sería mejor detectar input erróneo y reportarlo en un mensaje de error, pero veremos eso más adelante. Probémoslo evaluando la forma postfix de la expresión (56 + 47) * 2: >>> eval_postfix("56 47 + 2 *") 206 Es un buen comienzo.

25.8) Clientes y proveedores

Una de las metas fundamentales de un TDA es separar los intereses del proveedor, que escribe el código e implementa el TDA, del cliente, que lo usa. - El proveedor sólo tiene que preocuparse sobre si la implementación es correcta - según la especificación del TDA - y no en cómo va a ser usada. - Por otra parte, el cliente asume que la implementación del TDA es correcta y no se preocupa por sus detalles internos. Cuando estás usando uno de los tipos incorporados de Python, puedes darte el lujo de pensar exclusivamente como un cliente. Por supuesto, cuando implementas un TDA, también debes escribir código cliente para testearlo. - En ese momento estás asumiendo los dos roles, lo cual puede ser confuso. - Deberías hacer cierto esfuerzo para tener siempre en mente cuál es el rol que estás asumiendo en cada momento.

25.9) Glosario

- tipo de datos abstracto (TDA), cliente, proveedor, delimitador, estructura genérica de datos, implementación, interfaz, parse, infix, postfix, token, enchapado (veneer)

25.10) Ejercicios

1) Aplicar el algoritmo postfix a la expresión 1 2 + 3 *. - Este ejemplo muestra una de las ventajas de postfix - no hay necesidad de usar paréntesis para controlar el orden de las operaciones. - Para obtener el mismo resultado en infix deberíamos haber escrito (1 + 2) * 3. - Respuesta: el resultado del algoritmo será un 9: >>> eval_postfix("1 2 + 3 *") 9 2) Escribir una expresión postfix que sea equivalente a 1 + 2 * 3. - Respuesta: Aquí la operación central es la suma, y por lo tanto es la que se ejecuta última. Tendremos entonces: "1 2 3 * +"