|
|
|
|
|
|
|
Todos los tipos de datos que has visto hasta ahora son precisos en el sentido de que hemos indicado cómo se implementan totalmente. Por ejemplo, la clase Tarjeta representa una tarjeta que utiliza dos enteros. Tal y como hemos tratado, esta no es la única forma de representar una tarjeta: hay muchas implentaciones alternativas.
Un tipo abstracto de datos, o TAD, especifica un conjunto de operaciones, o métodos, y la semántica de dichas operaciones, lo que ejecutan. Sin embargo, no especifica la implementación de las operaciones. Esto es lo que lo convierte en abstracto.
¿Por qué es útil?
Cuando hablamos de TADs, solemos distinguir el código que se emplea en el TAD, denominado código cliente, a partir del cual se implementa el TAD, conocido como código proveedor.
Comentarios
En este capítulo, trataremos un TAD común, el TAD de pila. Una pila es un conjunto, una estructura de datos que contiene numerosos elementos. Otros conjuntos que hemos visto incluyen diccionarios y listas.
Un TAD se define por las operaciones que se pueden ejecutar en él, lo que se denomina interfaz. La interfaz de una pila se compone de las siguientes operaciones:
A las pilas también se les conoce como estructuras de datos LIFO ("last in, first out") porque el último item insertado es el primero que se elimina.
Comentarios
Las operaciones de lista que proporciona el Python son similares a las operaciones que definen una pila. La interfaz no es exactamente lo que debería ser, pero se puede escribir el código para traducir el TAD de pila en las operaciones predeterminadas.
Este código se conoce como implementación de la TAD de pila. En general, una implementación es un conjunto de métodos que cumple los requisitos sintácticos y semánticos de una interfaz.
Este es un ejemplo de una implementación de la TAD de pila que utiliza una lista Python:
class Stack :
def __init__(self) :
self.items = []
def push(self, item) :
self.items.append(item)
def pop(self) :
return self.items.pop()
def isEmpty(self) :
return (self.items == [])
Un objeto Pila contiene un atributo denominado items que consiste en una lista de items de la pila. El método de inicialización inserta los items en la lista vacía.
Para introducir un nuevo item en la pila push lo añade a items. Para sacar un item de la lista, pop utiliza el método de lista homónimo * Nota para eliminar y devolver el último item a la lista.
Finalmente, para revisar si la pila está vacía isEmpty compara items con la lista vacía.
Una implementación de este tipo, en la que los métodos consisten en simples invocaciones de métodos existentes, se llama chapa. En realidad, una chapa es una capa fina de madera de buena calidad que se emplea para la elaboración de muebles y así ocultar la madera de calidad inferior que se encuentra debajo. Los programadores utilizan esta metáfora para describir una pieza pequeña de código que oculta los detalles de una implementación y garantiza una interfaz más sencilla o más normal.
Comentarios
Una pila es una estructura de datos genérica, lo que significa que se le puede agregar todo tipo de items. El siguiente ejemplo introduce dos enteros y una serie a la pila:
>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")
Podemos utilizar isEmpty y pop para eliminar e imprimir todos los items de una pila:
while not s.isEmpty() :
print s.pop(),
El resultado es + 45 54. Es decir, únicamente hemos empleado una pila para imprimir los items hacia atrás. Hay que admitir que no es el formato convencional para imprimir una lista, pero gracias a la pila, resultó mucho más fácil de realizar.
Deberías comparar esta pieza de código con la implementación de printBackward en la Sección 17.4. Existe un paralelismo entre la versión recurrente de printBackward y este algoritmo de la pila. La diferencia estriba en que printBackward recurre a la pila que se está ejecutando para mantener el orden de los nodos mientras recorre la lista. Y, seguidamente, los imprime a la inversa de la recursión. El algoritmo de pila actúa exactamente de la misma manera, salvo que utiliza un objeto Pila en lugar de la pila activa.
Comentarios
En la mayoría de los lenguajes de programación, la expresiones matemáticas se escriben con el operador entre los dos operandos, como en 1+2. Este formato se llama notación infija. Una alternativa que utilizan algunas calculadoras es la notación postfija. En la notación postfija, el operador se sitúa tras los operandos, como en 1 2 +.
La razón postfija a veces resulta útil si exsite un método natural para analizar una expresión postfija utilizando una pila:
Como ejercicio, aplica este algoritmo a la expresión 1 2 + 3 *.
Este ejemplo pone de manifiesto una de las ventajas del postfijo, con lo que no es necesario recurrir a los paréntesis para controlar el orden de las operaciones. Para obtener el mismo resultado en notación infija, deberíamos escribir (1 + 2) * 3.
Como ejercicio, escribe la expresión postfija equivalente a 1 + 2 * 3.Comentarios
Para implementar el algoritmo anterior, necesitamos poder recorrer una serie y dividirla en operandos y operadores. Este proceso es un ejemplo de análisis, y el resultado son pedazos individuales de la serie, a los que se les llama símbolos. Deberías recordar estas palabras mencionadas anteriormente en el Capítulo 1.
El Python proporciona un método split tanto en la serie como en los módulos (expresiones normales) re. La función string.splitdivide una serie en una lista utilizando un único carácter como delimiter. Por ejemplo:
>>> import string
>>> string.split("Ahora es el momento"," ")
['Ahora', 'es', 'el', 'momento']
En este caso, el delimitador es el espaciador, de manera que la serie se divide con cada espacio.
La función re.split es mucho más segura pues nos permite garantizar una expresión convencional en lugar de un delimitador. Una expresión convencional es una manera de especificar un conjunto de series. 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, de forma que [^0-9] es todo aquello que no sean números, que es exactamente el conjunto que queremos utilizar para dividir las expresiones postfijas:
>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']
Fíjate en que el orden de los parámetros es diferente a string.split; el delimitador va delante de la serie.
La lista resultante incluye los operandos 123 y 456 y los operadores * y /. Del mismo modo, incluye dos series vacías que se han añadido tras los operandos.
Comentarios
Para analizar una expresión postfija, utilizaremos el analizador sintáctico de la sección anterior y el algoritmo de la sección anterior a esta. Para que resulte más fácil, comenzaremos con un evaluador que únicamente implementa los operadores + y *:
def evalPostfix(expr):
import re
tokenList = re.split("([^0-9])", expr)
stack = Stack()
for token in tokenList:
if token == '' or token == ' ':
continue
if token == '+':
sum = stack.pop() + stack.pop()
stack.push(sum)
elif token == '*':
product = stack.pop() * stack.pop()
stack.push(product)
else:
stack.push(int(token))
return stack.pop()
La primera condición tiene en cuenta los espacios de las series vacías. Las siguientes dos condiciones se encargan de los operadores. Por el momento, suponemos que cualquier otro elemento debe ser un operando. Evidentemente, sería conveniente que revisar los datos erróneos y emitir un mensaje de error, pero ya llegaremos a eso más adelante.
Hagamos una prueba analizando la forma postfija de (56+47)*2:
>>> print evalPostfix ("56 47 + 2 *")
206
Es suficientemente directa.
Comentarios
Uno de los objetivos fundamentales de un TAD es separar los intereses del proveedor, que es quien escribe el código e implementa el TAD, de los del cliente, la persona que utiliza el TAD. El proveedor tan sólo tiene que preocuparse de si la implementación es correcta, considerando las características del TAD, y no de qué uso se le daráa este.
En cambio, el cliente supone que la implementación del TAD es correcta y no le interesan los detalles. Cuando utilizas uno de los tipos predeterminados de Python, disfrutas del placer de pensar exclusivamente como un cliente.
Queda claro que cuando implementas un TAD, también tienes que escribir un código de cliente para probarlo. En ese caso, estás desempeñando ambos papeles, lo que puede resultar confuso. Deberías esforzarte en recordar el papel que estés desempeñando en cada momento.
Comentarios
|
|
|
|
|
|
|