Chapter 18
\newcommand{\tab{\hspace{5mm}}
\chapter{Pilas}
\section{Tipos abstractos de datos}
\index{tipo abstracto de datos {\textbar}ver{TAD}}
\index{TAD}
\index{encapsulación}
Los tipos de datos vistos hasta ahora han sido todos concretos,
en el sentido que se ha especificado su implementación completamente.
Por ejemplo, la clase {\tt Carta} representa un naipe por medio de
dos enteros. Como dijimos, esa no es la única manera de representar
una carta; existen muchas implementaciones alternativas.
Un {\bf tipo abstracto de datos}, o TAD, especifica un conjunto de
operaciones (o métodos) y la semántica de las operaciones (lo que
hacen), pero no especifica la implementación de las operaciones.
Esto es lo hace lo abstracto.
¿Para qué sirve?
\begin{itemize}
\item Simplifica la tarea de especificar un algoritmo si se
pueden indicar las operaciones necesarias sin preocuparse de cómo
se ejecutarán dichas operaciones.
\item Como suelen existir muchas maneras de implementar un TAD,
puede ser útil desarrollar un algoritmo que se pueda usar con
cualquiera de las implementaciones posibles.
\item Los TADs mas conocidos, como el TAD Pila de este capítulo,
se implementan a menudo en bibliotecas estándares de manera que
se puedan escribir una vez y usarlas luego muchos programadores.
\item Las operaciones ejecutadas con TADs proporcionan un lenguaje de
alto nivel común para desarrollar y hablar sobre algoritmos.
\end{itemize}
Cuando hablamos de TADs a menudo se hace la distinción entre el
código que usa el TAD, el código {\bf cliente}, y el código que
implementa el TAD, el código {\bf proveedor}.
\index{cliente}
\index{proveedor}
\section{El TAD Pila}
\index{pila}
\index{colección}
\index{TAD!Pila}
En este capítulo se presentará un TAD común, la {\bf pila}. Una pila
es una colección, lo que significa que es una estructura de datos que
contiene elementos múltiples. Otras colecciones que se han visto son
los diccionarios y las listas.
\index{interfaz}
Un TAD se definido por medio de las operaciones que se pueden ejecutar
sobre él, lo que se llama un {\bf interfaz}. La interfaz para una pila
consta de estas operaciones\footnote{Mantenemos los nombres ingleses
porque son estándar en otros TADs en Python y otros lenguajes.}:
\begin{description}
\item[{\tt \_\_init\_\_}:] Inicializar una pila nueva y vacía.
\item[{\tt push}:] Añadir un elemento a la pila.
\item[{\tt pop}:] Extraer un elemento de la pila. El elemento
devuelto siempre es el último que se añadió.
\item[{\tt isEmpty}:] Probar si la pila está vacía.
\end{description}
A veces a una pila se la llama una estructura ``último en
entrar primero en salir'' (``last in, first out'' en inglés),
o LIFO, porque el elemento añadido en último lugar es el primero que
extraemos.
\section {Cómo implementar pilas con listas de Python}
\index{Pila}
\index{clase!Pila}
\index{estructura genérica de datos}
\index{estructura de datos!genérica}
Las operaciones sobre listas que posee Python son parecidas a las
operaciones que definen a una pila. La interfaz no es exactamente
la que debería de ser, pero se pueden desarrollar programas para
convertir el TAD Pila a las operaciones predefinidas.
A este programa se lo llama {\bf implementación} del TAD Pila.
En general, una implementación es un conjunto de métodos que
satisfacen los prerrequisitos sintácticos y semánticos de la
interfaz.
He aquí una implementación de el TAD Pila que utiliza una lista Python:
\beforeverb
\begin{verbatim}
class Pila :
def __init__(self) :
self.elementos = []
def push(self, elemento) :
self.elementos.append(elemento)
def pop(self) :
return self.elementos.pop()
def isEmpty(self) :
return (self.elementos == [])
\end{verbatim}
\afterverb
%
Un objeto {\tt Pila} contiene un atributo llamado {\tt elementos}
que es una lista de elementos en la pila. El método de inicialización
pone una lista vacía en {\tt elementos}.
Para meter un elemento nuevo en la pila, {\tt push} lo apila en
{\tt elementos}. Para quitar un elemento de la pila, {\tt pop} utiliza
el método de lista homónimo\footnote{del mismo nombre} para quitar y
devolver el último elemento de la lista.
Finalmente, para probar si la pila esta vacía, {\tt isEmpty}
(está vacía) compara {\tt elementos} con la lista vacía.
\index{enchapado}
Una implementación como esta, en la cual los métodos consisten
de llamadas a métodos existentes, se llama {\bf enchapado}.
En la vida real, un enchapado es una capa fina de madera de
alta calidad que se utiliza en la fabricación de muebles para
ocultar madera de baja calidad. Los científicos informáticos
utilizan esta metáfora para describir una parte de un programa
que esconde los detalles de una implementación y que provee una
interfaz mas simple o mas estándar.
\section{Uso de {\tt push} y {\tt pop}}
\index{push}
\index{pop}
\index{estructura genérica de datos}
\index{estructura de datos!genérica}
Una pila es una {\bf estructura genérica de datos}, lo significa
que se puede añadir cualquier tipo de elementos a ella. El
ejemplo mete en la pila dos enteros y una cadena:
\beforeverb
\begin{verbatim}
>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")
\end{verbatim}
\afterverb
%
Se pueden utilizar {\tt isEmpty} y {\tt pop} para quitar e imprimir
todos los elementos en la pila:
\beforeverb
\begin{verbatim}
while not s.isEmpty() :
print s.pop(),
\end{verbatim}
\afterverb
%
La salida es {\tt + 45 54}. En otras palabras, ¡se ha
utilizado una pila para imprimir los elementos en orden
inverso! Reconocemos que no es el formato estándar de impresión de
listas, pero fue muy fácil usar una pila para lograrlo.
Compare estas líneas con la implementación de {\tt imprimeAlReves} que vimos
en la Sección~\ref{listrecursion}. Existe un paralelo natural entre la
versión recurrente de {\tt imprimeAlReves} y el algoritmo de pila que
acabamos de ver. La diferencia es que {\tt imprimeAlReves} utiliza la
pila de tiempo de ejecución para mantenerse al tanto de los nodos
mientras recorre la lista y luego los imprime cuando regresa de la
recursión. El algoritmo de pila hace lo mismo, pero utiliza un
objeto {\tt Pila} en vez de la pila de tiempo de ejecución.
\section {Usar una pila para evaluar postfijo}
\index{postfijo}
\index{infijo}
\index{expresión}
Las expresiones matemáticas en la mayoría de lenguajes de
programación se escriben con el operador entre los dos
operandos, de esta manera: {\tt 1+2}. A este formato se le
llama {\bf infijo}. Algunas calculadoras utilizan un formato
alternativo llamado {\bf postfijo}. Con postfijo, el operador
va después de los operandos, así: {\tt 1 2 +}.
La razón por la que el formato postfijo es útil es que existe una
forma natural de evaluar una expresión en formato postfijo
utilizando una pila:
\begin{itemize}
\item Desde el principio de la expresión, evalúe los
operadores y operandos uno por uno.
\begin{itemize}
\item Si el término es un operando, utilice push para
colocarlo en la pila.
\item Si el término es un operador, utilice pop con dos
operandos de la pila, ejecute la operación sobre ellos,
y coloque el resultado en la pila con push.
\end{itemize}
\item Cuando llegue al final de la expresión habrá un operando
en la pila. Ese operando es el resultado.
\end{itemize}
\begin{quote}
{\em Para practicar, aplique este algoritmo a la expresión
{\tt 1 2 + 3 *}.}
\end{quote}
Este ejemplo demuestra una de las ventajas de el formato postfijo---no
hay necesidad de usar paréntesis para controlar el orden de
operaciones. Para obtener el mismo resultado con el formato infijo, se
tendría que escribir {\tt (1 + 2) * 3)}.
\begin{quote}
{\em Para practicar, escriba una expresión en formato postfijo que sea
equivalente a {\tt 1 + 2 * 3}.}
\end{quote}
\section {Análisis sintáctico}
\index{analizar}
\index{token}
\index{delimitador}
\index{expresión regular}
Para implementar el algoritmo anterior, necesitamos ser capaces
de recorrer una cadena y separarla en operandos y operadores. Este
proceso es un ejemplo del {\bf análisis sintáctico}, y los
resultados---la piezas individuales de la cadena---son {\bf
tokens}\footnote{Podríamos traducir ``token'' como
``cospel'' o ``pieza'', en ocasiones también como ``símbolo'' pero
la expresión inglesa está tan introducida en el vocabulario
informático que sólo añadiría confusión.}. Quizás se acuerde de esas
palabras del Capítulo 1.
Python posee un método llamado {\tt split} (partir) en el módulo
{\tt string} (cadena) y en el módulo {\tt re} (expresiones regulares).
La función {\tt string.split} parte una cadena y la convierte en una
lista utilizando un sólo carácter como {\bf delimitador}.
Por ejemplo:
\beforeverb
\begin{verbatim}
>>> import string
>>> string.split("La hora ha llegado"," ")
['La', 'hora', 'ha', 'llegado']
\end{verbatim}
\afterverb
%
En este caso, el delimitador es el carácter espacio, y se parte
la cadena en cada espacio.
La función {\tt re.split} tiene más potente, y nos permite
utilizar una expresión regular en vez de un delimitador.
Una expresión regular es una manera de especificar un conjunto
de cadenas. Por ejemplo, \verb+[A-z]+ es el conjunto de todas
las letras y \verb+[0-9]+ es el conjunto de todas las cifras.
El operador \verb+^+ niega un conjunto, y \verb+[^0-9]+ es el
conjunto de todo lo que no es un número, lo cual es exactamente
lo que queremos utilizar para partir expresiones en el formato
postfijo:
\beforeverb
\begin{verbatim}
>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']
\end{verbatim}
\afterverb
%
Fíjese que el orden de los argumentos es diferente del de
{\tt string.split}; el delimitador viene antes de la
cadena.
La lista resultante incluye los operandos {\tt 123} y {\tt 456} y
los operadores {\tt *} y {\tt /}. También incluye dos cadenas vacías
que se insertan después de los operandos.
\section {Evaluar un postfijo}
Para evaluar una expresión en formato postfijo usaremos el
analizador sintáctico de la sección anterior y el algoritmo de la
sección previa a ésa. Para no complicar las cosas, comenzaremos con
un evaluador que solo implementa los operadores {\tt +} y {\tt *}:
\adjustpage{-3}
\beforeverb
\begin{verbatim}
def evalPostfijo(expr):
import re
listaTokens = re.split("([^0-9])", expr)
pila = Pila()
for token in listaTokens:
if token == '' or token == ' ':
continue
if token == '+':
suma = pila.pop() + pila.pop()
pila.push(suma)
elif token == '*':
producto = pila.pop() * pila.pop()
pila.push(producto)
else:
pila.push(int(token))
return pila.pop()
\end{verbatim}
\afterverb
%
La primera condición se encarga de espacios y cadenas vacías. Las
dos condiciones siguientes controlan los operadores. Asumimos, por
ahora, que todo lo demás es un operando. Por supuesto, sería mejor
verificar si la entrada tiene errores y mostrar un mensaje con el
error, pero eso se hará después.
Comprobemos con una evaluación de la forma postfijo {\tt (56+47)*2)}:
\beforeverb
\begin{verbatim}
>>> print evalPostfijo ("56 47 + 2 *")
206
\end{verbatim}
\afterverb
%
Esto es suficiente.
\section {Clientes y proveedores}
\index{encapsulación}
\index{TAD}
Uno de los objetivos fundamentales de un TAD es el de separar los
intereses del proveedor, quien escribe el código de programa
que implementa el TAD, y los del cliente, quien utiliza el TAD.
El proveedor sólo se preocupa de la implementación y de si es
correcta o no---de acuerdo a las especificaciones del TAD---y no
de cómo se va a utilizar.
A la inversa, el cliente {\em supone} que la implementación del
TAD es correcta y no se preocupa de los detalles. Cuando se usa
uno de los tipos predefinidos de Python, uno se puede dar el lujo
de pensar exclusivamente como un cliente.
Por supuesto, cuando usted implemente un TAD, también debe
desarrollar código de cliente para probarlo. En ese case, uno
toma ambos papeles, lo cual puede causar confusión. Tiene
que fijarse bien en del papel que está tomando en todo momento.
\section{Glosario}
\index{TAD}
\index{cliente}
\index{proveedor}
\index{infijo}
\index{postfijo}
\index{analizar sintácticamente}
\index{token}
\index{delimitador}
\begin{description}
\item[tipo abstracto de datos (TAD):] Un tipo de datos (a menudo una
colección de objetos) que se define por un conjunto de operaciones
pero que se puede implementar de varias maneras.
\item[interfaz:] El conjunto de operaciones que definen un TAD.
\item[implementación:] El código de programa que satisface los
prerrequisitos sintácticos y semánticos de un interfaz.
\item[cliente:] Un programa (o la persona que lo escribió) que
utiliza un TAD.
\item[proveedor:] Un programa (o la persona que lo escribió) que
implementa un TAD.
\item[enchapado:] La definición de clase que implementa un TAD con
definiciones de métodos que son las invocaciones de otros métodos,
a veces con transformaciones simples. El enchapado no ejecuta nada
de gran valor, pero mejora la interfaz vista por el cliente o la
hace mas estándar.
\item[estructura de datos genérica:] Un tipo de estructura de datos
que puede contener datos de cualquier tipo.
\item[infijo:] Un método de escribir expresiones matemáticas con
los operadores entre los operandos.
\item[postfijo:] Un método de escribir expresiones matemáticas con
los operadores después de los operandos.
\item[analizar sintácticamente:] Examinar una cadena de caracteres o
tokens y analizar su estructura gramátical.
\item[token:] Un conjunto de caracteres que se tratan como una
unidad y son analizados sintácticamente, como las palabras de
un lenguaje natural.
\item[delimitador:] Un carácter utilizado para separar tokens,
como la puntuación en un lenguaje natural.
\end{description}
