Next Up Previous Hi Index

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 }


Next Up Previous Hi Index