Chapter 18
{\rtf1\ansi\ansicpg1252\deff0{\fonttbl{\f0\fmodern\fprq1\fcharset0 Courier New;{\f1\fmodern\fprq2\fcharset129 \'b1\'bc\'b8\'b2;}{\f2\fnil\fcharset0 Courier New;}}
\viewkind4\uc1\pard\lang10250\f0\fs20\\chapter\{Pilas\}\par
\par
\\section\{Tipos abstractos de datos\}\par
\\index\{tipo abstracto de datos |ver\{TAD\}\}\par
\\index\{TAD\}\par
\\index\{encapsulaci\'f3n\}\par
\par
Los tipos de datos vistos hasta ahora han sido todos concretos,\par
en el sentido que se ha especificado su implementaci\'f3n completamente.\par
Por ejemplo, la clase \{\\tt Naipe\} representa un naipe que utiliza\par
dos enteros. Como dijimos, esa no es la \'fanica manera de representar\par
un pe\'f3n; existen muchas implementaciones alternativas.\par
\par
Un \{\\bf tipo abstracto de datos\}, a TAD, especifica un conjunto de\par
operaciones (o m\'e9todos) y la sem\'e1ntica de las operaciones (lo que\par
hacen), pero no especifica la implementaci\'f3n de las operaciones. Esta\par
caracter\'edstica lo hace abstracto.\par
\par
\'bfPor qu\'e9 es \'fatil?\par
\par
\\begin\{itemize\}\par
\par
\\item Simplifica la tarea de especificar un algoritmo si se\par
pueden indicar las operaciones necesarias sin preocuparse de c\'f3mo\par
dichas operaciones ser\'e1n ejecutadas.\par
\par
\\item Como a menudo existen muchas maneras de implementar un TAD,\par
puede ser \'fatil desarrollar un algoritmo que se pueda usar con \par
cualquiera de las implementaciones posibles.\par
\par
\\item Los TADs mas conocidos, como el TAD Pila en este cap\'edtulo,\par
se implementas a menudo en bibliotecas, o colecciones, est\'e1ndares\par
de manera que se puedan escribir una vez y se puedan usar por\par
muchos programadores.\par
\par
\\item Las operaciones ejecutados con TADs proveen un lenguaje de\par
alto nivel com\'fan para desarrollar algoritmos.\par
\par
\\end\{itemize\}\par
\par
Cuando hablamos de TADs a menudo se hace la distinci\'f3n entre el\par
c\'f3digo que usa el TAD, el c\'f3digo \{\\cliente\}, y el c\'f3digo que\par
implementa el TAD, el c\'f3digo \{\\bf proveedor\}.\par
\par
\par
\\index\{cliente\}\par
\\index\{proveedor\}\par
\par
\par
\\section\{El TDA Pila\}\par
\\index\{pila\}\par
\\index\{colecci\'f3n\}\par
\\index\{TDA!Pila\}\par
\par
En este cap\'edtulo se presentar\'e1 un TAD com\'fan, la \{\\bf pila\}. Una pila\par
es una colecci\'f3n, lo que significa que es una estructura de datos que\par
contiene elementos m\'faltiples. Otras colecciones que se han visto son\par
los diccionarios y las listas.\par
\par
\\index\{interfaz\}\par
\par
Un TAD es definido por las operaciones que se pueden ejecutar sobre\par
el, lo que se llama un \{\\bf interfaz\}. La interfaz para una pila\par
consiste de estas operaciones:\par
\par
\\begin\{description\}\par
\par
\\item[\{\\tt \\_\\_init\\_\\_\}:] Inicializar una pila nueva y vac\'eda.\par
\par
\\item[\{\\tt push\}:] A\'f1adir un elemento a la pila.\par
\par
\\item[\{\\tt pop\}:] Eliminar un elemento de la pila. El elemento\par
que es devuelto siempre es el \'faltimo que se a\'f1adi\'f3.\par
\par
\\item[\{\\tt isEmpty\}:] Probar si la pila est\'e1 vac\'eda.\par
\par
\\end\{description\}\par
\par
A veces a una pila se la llama una estructura ``\'faltimo en\par
entrar primero en salir'' (``last in, first out'' en ingl\'e9s),\par
o LIFO, porque el elemento a\'f1adido \'faltimo es el primero que\par
es extirpado.\par
\par
\\section \{C\'f3mo implementar pilas con listas de Python\}\par
\\index\{Pila\}\par
\\index\{clase!Pila\}\par
\\index\{estructura gen\'e9rica de datos\}\par
\\index\{estructura de datos!gen\'e9rica\}\par
\par
Las operaciones sobre listas que Python provee son parecidas a las\par
operaciones que definen a una pila. La interfaz no es exactamente lo que\par
deber\'eda de ser, pero se pueden desarrollar programas para convertir del\par
TAD Pila a las operaciones predefinidas.\par
\par
A este programa se lo llama una \{\\bf implementaci\'f3n\} de TAD Pila.\par
En general, una implementaci\'f3n es un conjunto de m\'e9todos que \par
satisfacen los prerrequisitos sint\'e1cticos y sem\'e1nticos de la\par
interfaz.\par
\par
E aqu\'ed una implementaci\'f3n de el TAD Pila que utiliza una lista\par
Python:\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
class Pila :\par
def __init__(self) :\par
self.items = []\par
\par
def push(self, item) :\par
self.items.append(item)\par
\par
def pop(self) :\par
return self.items.pop()\par
\par
def isEmpty(self) :\par
return (self.items == [])\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
\par
Un objeto \{\\tt Pila\} contiene un atributo llamado \{\\tt items\}\par
(elementos), el cual es una lista de elementos en la pila. El\par
m\'e9todo de inicializaci\'f3n pone una lista vac\'eda en \{\\tt items\}.\par
\par
Para apilar un elemento nuevo en la pila, \{\\tt push\} lo apila en\par
\{\\tt items\}. Para quitar un elemento de la pila, \{\\tt pop\} utiliza\par
el m\'e9todo de lista hom\'f3nimo\\footnote\{del mismo nombre\} para quitar y\par
devolver el \'faltimo elemento en la lista.\par
\par
Finalmente, para probar si la pila esta vac\'eda, \{\\tt isEmpty\}\par
(est\'e1 vac\'eda) compara \{\\tt items\} a la lista vac\'eda.\par
\par
\\index\{enchapado\}\par
\par
Una implementaci\'f3n como esta, en la cual los m\'e9todos consisten\par
de llamadas a m\'e9todos existentes, se la llama un \{\\bf enchapado\}.\par
Un enchapado es una capa fina de madera de alta calidad que se\par
utiliza en la fabricaci\'f3n de muebles para ocultar madera de baja\par
calidad. Cient\'edficos inform\'e1ticos utilizan esta met\'e1fora para\par
describir una parte de un programa que esconde los detalles de una\par
implementaci\'f3n y que provee una interfaz mas simple o mas est\'e1ndar.\par
\par
\\section\{Utilizando Push y Pop\}\par
\\index\{push\}\par
\\index\{pop\}\par
\\index\{estructura gen\'e9rica de datos\}\par
\\index\{estructura de datos!gen\'e9rica\}\par
\par
Una pila es una \{\\bf estructura gen\'e9rica de datos\}, lo que quiere\par
decir que se puede a\'f1adir cualquier tipo de elementos a ella. Los\par
ejemplos siguientes utiliza push con dos enteros y una cadena y\par
los coloca en la pila:\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
>>> s = Stack()\par
>>> s.push(54)\par
>>> s.push(45)\par
>>> s.push("+")\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
Se pueden utilizar \{\\tt isEmpty\} y \{\\tt pop\} para quitar y imprimir\par
todos los elementos en la pila:\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
while not s.isEmpty() :\par
print s.pop(),\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
La salida (output) es \{\\tt + 45 54\}. En otras palabras, \'a1se ha\par
utilizado una pila para imprimir los elementos en el orden\par
opuesto! Reconocemos que no es el formato est\'e1ndar de impresi\'f3n de\par
listas, pero fue muy f\'e1cil usar una pila para lograrlo.\par
\par
Compare estas l\'edneas con la implementaci\'f3n de \{\\tt printBackward\}\par
en Section\f1 ~\\\f0 ref\{listrecursion\}. Existe un paralelo natural entre la\par
versi\'f3n recurrente de \{\\tt printBackward\} y el algoritmo de pila que\par
acabamos de ver. La diferencia es que \{\\tt printBackward\} utiliza la\par
pila de tiempo de ejecuci\'f3n para mantenerse al tanto de los nodos\par
mientras atraviesa la lista, y luego los imprime cuando regresa de la\par
recursi\'f3n. El algoritmo de pila hace lo mismo, pero utiliza un\par
objeto \{\\tt Stack\} en vez de la pila de tiempo de ejecuci\'f3n.\par
\par
\par
\\section \{Usar una pila para evaluar postfijo\}\par
\\index\{postfijo\}\par
\\index\{infijo\}\par
\\index\{expresi\'f3n\}\par
\par
Las expresiones matem\'e1ticas en la mayor\'eda de lenguajes de\par
programaci\'f3n son escritas con el operador entre los dos\par
operandos, de esta manera: \{\\tt 1+2\}. A este formato se lo\par
llama \{\\bf infijo\}. Algunas calculadoras utilizan un formato \par
alternativo llamado \{\\bf postfijo\}. Con postfijo, el operador\par
va despu\'e9s de los operandos, as\'ed: \{\\tt 1 2 +\}.\par
\par
La raz\'f3n porque el formato postfijo es \'fatil es que existe una\par
forma natural de evaluar una expresi\'f3n en formato postfijo\par
utilizando una pila:\par
\par
\\begin\{itemize\}\par
\par
\\item Desde el principio de la expresi\'f3n, eval\'faa los \par
operadores y operandos uno por uno.\par
\par
\\begin\{itemize\}\par
\par
\\item Si el t\'e9rmino es un operando, utilice push para\par
colocarlo en la pila.\par
\par
\\item Si el t\'e9rmino es un operador, utilice pop con dos\par
operandos de la pila, ejecute la operaci\'f3n sobre ellos,\par
y coloque el resultado en la pila con push.\par
\par
\\end\{itemize\}\par
\par
\\item Cuando llegue al final de la expresi\'f3n habr\'e1 un operando\par
en la pila. Ese operando es el resultado.\par
\par
\\end\{itemize\}\par
\par
\\begin\{quote\}\par
\{\\em Para practicar, aplique este algoritmo a la expresi\'f3n\par
\{\\tt 1 2 + 3 *\}.\}\par
\\end\{quote\}\par
\par
Este ejemplo demuestra una de las ventajas de el formato postfijo---no\par
hay necesidad de usar par\'e9ntesis para controlar el orden de\par
operaciones. Para obtener el mismo resultado con el formato infijo, se\par
tendr\'eda que escribir \{\\tt (1 + 2) * 3).\par
\par
\\begin\{quote\}\par
\{\\em Para practicar, escriba una expresi\'f3n en formato postfijo que es\par
equivalente a\par
\{\\tt 1 + 2 * 3\}.\}\par
\\end\{quote\}\par
\par
\par
\\section \{An\'e1lisis sint\'e1ctico\}\par
\\index\{analizar\f1\}\par
\\\f0 index\{s\'edmbolo\}\par
\\index\{delimitador\}\par
\\index\{expresi\'f3n regular\}\par
\par
Para implementar el algoritmo previo, necesitamos la habilidad de\par
atravesar una cadena y separarla en operandos y operadores. Este\par
proceso es un ejemplo del \{\\bf an\'e1lisis sint\'e1ctico\}, y los\par
resultados---la piezas individuales de la cadena---son \{\\bf\par
s\'edmbolos\}. Quiz\'e1s se acuerde de esas palabras del Cap\'edtulo 1.\par
\par
Python posee un m\'e9todo llamado \{\\tt split\} (partir) en el m\'f3dulo\par
\{\\tt string\} (cadena) y en el m\'f3dulo \{\\tt re\} (expresiones regulares).\par
La funci\'f3n \{\\tt string.split\} parte a una cadena y la convierte en una\par
lista y utiliza un solo car\'e1cter de \{\\bf delimitador\}.\par
\par
Por ejemplo:\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
>>> import string\par
>>> string.split("La hora ha llegado"," ")\par
['La', 'hora', 'ha', 'llegado']\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
En este caso, el delimitador es el car\'e1cter espacio, y se parte\par
la cadena en cada espacio.\par
\par
La funci\'f3n \{\\tt re.split\} tiene mas poder, y nos permite\par
utilizar una expresi\'f3n regular en vez de un delimitador.\par
Una expresi\'f3n regular es una manera de especificar un serie\par
de cadenas. Por ejemplo, \\verb+[A-z]+ es el conjunto de todas\par
las letras y \\verb+[0-9]+ es el conjunto de todos los n\'fameros.\par
El operador \\verb+^+ niega un conjunto, y \\verb+[^0-9]+ es el\par
conjunto de todo lo que no es un n\'famero, lo cual es exactamente\par
lo que queremos utilizar para partir expresiones en el formato\par
postfijo:\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
>>> import re\par
>>> re.split("([^0-9])", "123+456*/")\par
['123', '+', '456', '*', '', '/', '']\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
F\'edjese que el orden de los argumentos es diferente del de\par
\{\\tt string.split\}; el delimitador viene antes de la cadena.\par
\par
La lista resultante incluye los operandos \{\\tt 123 y \{\\tt 456\} y\par
los operadores \{\\tt *\} y \{\\tt /\}. Tambi\'e9n incluye dos cadenas vac\'edas\par
que se insertan despu\'e9s de los operandos.\par
\par
\\section \{Evaluar un postfijo\}\par
\par
Para evaluar una expresi\'f3n en formato postfijo, usaremos el\par
analizador sint\'e1ctico de la secci\'f3n pasada y el algoritmo de la\par
secci\'f3n previa a esa. Para que esto sea simple, comenzaremos con\par
un evaluador que solo implementa los operadores \{\\tt +\} y \{\\tt *\}:\par
\par
\\adjustpage\{-3\}\par
\\pagebreak\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
def evalPostfijo(expr):\par
import re\par
listaSimbolos = re.split("([^0-9])", expr)\par
pila = Pila()\par
for simbolo in listaSimbolos:\par
if simbolo == '' or simbolo == ' ':\par
\lang1033 continue\par
if simbolo == '+':\par
\lang10250 suma = pila.pop() + pila.pop()\par
pila.push(suma)\par
elif simbolo == '*':\par
producto = pila.pop() * pila.pop()\par
pila.push(producto)\par
else:\par
\lang1033 pila.push(int(simbolo))\par
return pila.pop()\par
\lang10250\f1\\\f0 end\{verbatim\}\par
\\afterverb\par
%\par
La primera condici\'f3n se encarga de espacios y cadenas vac\'edas. Las\par
dos condiciones siguientes controlan los operadores. Asumimos, por \par
ahora, que todo lo dem\'e1s es un operando. Por supuesto, ser\'eda mejor\par
verificar si la entrada tiene errores y mostrar un mensaje con el\par
error, pero eso se har\'e1 despu\'e9s.\par
\par
Comprobemos con una evaluaci\'f3n de la forma postfijo \{\\tt\par
(56+47)*2):\par
\par
\\beforeverb\par
\\begin\{verbatim\}\par
>>> print evalPostfix ("56 47 + 2 *")\par
206\par
\\end\{verbatim\}\par
\\afterverb\par
%\par
Esto es suficiente.\par
\par
\\section \{Clientes and proveedores\}\par
\\index\{encapsulaci\'f3n\}\par
\\index\{TAD\}\par
\par
Uno de los goles fundamentales de un TAD es el de separar los\par
intereses del proveedor, quien escribe el c\'f3digo de programa\par
que implementa el TAD, y los del cliente, quien utiliza el TAD.\par
El proveedor solo se preocupa de la implementaci\'f3n y de si esta\par
correcta o no---de acuerdo a las especificaciones del TAD---y no\par
de c\'f3mo ser\'e1 utilizado.\par
\par
A la inversa, el cliente \{\\em supone\} que la implementaci\'f3n de el\par
TAD es correcta y no se preocupa de los detalles. Cuando se usa\par
uno de los tipos predefinidos de Python, uno se puede dar el lujo\par
de pensar exclusivamente como un cliente.\par
\par
Por supuesto, cuando uno implementa un TAD, uno tambi\'e9n debe \par
desarrollar c\'f3digo de cliente para probarlo. En ese case, uno\par
toma ambos papeles, lo cual puede causar confusi\'f3n. Uno tiene\par
que encargarse del papel que esta tomando en todo momento.\par
\par
\\section\{Glosario\f1\}\par
\\\f0 index\{TAD\}\par
\\index\{cliente\}\par
\\index\{proveedor\}\par
\\index\{infijo\}\par
\\index\{postfijo\}\par
\\index\{analizar sint\'e1cticamente\}\par
\\index\{s\'edmbolo\}\par
\\index\{delimitador\}\par
\par
\\begin\{description\}\par
\par
\\item[tipo abstracto de datos (TAD):] Un tipo de datos (a menudo una\par
colecci\'f3n de objetos) que se devine por un conjunto de operaciones\par
pero que se puede implementar de varias maneras.\par
\par
\\item[interfaz:] El conjunto de operaciones que definen un TAD.\par
\par
\\item[implementaci\'f3n:] El c\'f3digo de programa que satisface los\par
prerrequisitos sint\'e1cticos y sem\'e1nticos de un interfaz.\par
\par
\\item[cliente:] Un programa (o la persona que lo escribi\'f3) que\par
utiliza un TAD.\par
\par
\\item[proveedor:] Un programa (o la persona que lo escribi\'f3) que\par
implementa un TAD.\par
\par
\\item[enchapado:] La definici\'f3n de clase que implementa un TAD con\par
definiciones de m\'e9todos que son las invocaciones de otros m\'e9todos,\par
a veces con transformaciones simples. El enchapado no ejecuta nada\par
de gran valor, pero mejora la interfaz vista por el cliente o la\par
hace mas est\'e1ndar.\par
\par
\\item[estructura de datos gen\'e9rica:] Un tipo de estructura de datos\par
que puede contener datos de cualquier tipo.\par
\par
\\item[infijo:] Un m\'e9todo de escribir expresiones matem\'e1ticas con\par
los operadores entre los operandos.\par
\par
\\item[postfijo:] Un m\'e9todo de escribir expresiones matem\'e1ticas con\par
los operadores despu\'e9s de los operandos.\par
\par
\\item[analizar sint\'e1cticamente:] Leer una cadena de caracteres o\par
s\'edmbolos y analizar su estructura gram\'e1tica.\par
\par
\\item[s\'edmbolo:] Un conjunto de caracteres que se tratan como una\par
unidad y son analizados sint\'e1cticamente, como las palabras de\par
un lenguaje natural.\par
\par
\\item[delimitador:] Un car\'e1cter utilizado para separar s\'edmbolos,\par
como puntuaci\'f3n en un lenguaje natural.\par
\par
\\end\{description\}\lang1042\f2\par
}