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}
" + str + "Close window
