Cesar Systems

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 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 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 que sirve?
  Simplifica la tarea de especificar un algoritmo si se pueden indicar las operaciones necesarias sin preocuparse de como se ejecutaran dichas operaciones.
• 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.
• 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.
• Las operaciones ejecutadas con TADs proporcionan un lenguaje de alto nivel común para desarrollar y hablar sobre algoritmos.

Cuando hablamos de TADs a menudo se hace la distinción entre el código que usa el TAD, el código cliente, y el código que implementa el TAD, el código proveedor.

En este capítulo se presentara un TAD común, la 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.

Un TAD se definido por medio de las operaciones que se pueden ejecutar sobre el, lo que se llama un interfaz. La interfaz para una pila consta de estas
operaciones:

__init__ : Inicializar una pila nueva y vacía.

push: Añadir un elemento a la pila.

pop: Extraer un elemento de la pila. El elemento devuelto siempre es el ultimo que se añadió.

isEmpty: Probar si la pila esta vacía.

A veces a una pila se la llama una estructura ultimo en entrar primero en salir” (last in, first out” en ingles), o LIFO, porque el elemento añadido en ultimo lugar es el primero que extraemos.

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 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:

   1: class Pila :

   2:     def __init__(self) :

   3:         self.elementos = []

   4:     def push(self, elemento) :

   5:         self.elementos.append(elemento)

   6:     def pop(self) :

   7:         return self.elementos.pop()

   8:     def isEmpty(self) :

   9:         return (self.elementos == [])

Un objeto Pila contiene un atributo llamado elementos que es una lista de elementos en la pila. El metodo de inicialización pone una lista vacía en elementos.

Para meter un elemento nuevo en la pila, push lo apila en elementos. Para quitar un elemento de la pila, pop utiliza el metodo de lista homónimo para quitar y devolver el ultimo elemento de la lista.

Finalmente, para probar si la pila esta vacía, isEmpty (esta vacía) compara elementos con la lista vacía.

Una implementación como esta, en la cual los métodos consisten de llamadas a métodos existentes, se llama 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.

Una pila es una estructura genérica de datos, lo significa que se puede a~nadir cualquier tipo de elementos a ella.

El ejemplo mete en la pila dos enteros y una cadena:

   1: >>> s = Stack()

   2: >>> s.push(54)

   3: >>> s.push(45)

   4: >>> s.push("+")

Se pueden utilizar isEmpty y pop para quitar e imprimir todos los elementos en la pila:

   1: while not s.isEmpty() :

   2: print s.pop(),

La salida es + 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 imprimeAlReves que vimos en la Sección 17.4. Existe un paralelo natural entre la versión recurrente de imprimeAlReves y el algoritmo de pila que acabamos de ver. La diferencia e que 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 Pila en vez de la pila de tiempo de ejecución.

Las expresiones matemáticas en la mayoría de lenguajes de programación reescriben con el operador entre los dos operandos, de esta manera: 1+2. A este formato se le llama infijo. Algunas calculadoras utilizan un formato alternativo
llamado postfijo. Con postfijo, el operador va después de los operandos, así: 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:

• Desde el principio de la expresión, evalué los operadores y operandos uno por uno.
  Si el termino es un operando, utilice push para colocarlo en la pila.
  Si el termino 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.
• Cuando llegue al final de la expresión habrá un operando en la pila. Ese operando es el resultado.

Para practicar, aplique este algoritmo a la expresión 1 2 + 3 *.

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 (1 + 2) * 3).

Para practicar, escriba una expresión en formato postfijo que sea equivalente a 1 + 2 * 3.

Para implementar el algoritmo anterior, necesitamos ser capaces de recorrer una cadena y separarla en operandos y operadores. Este proceso es un ejemplo del analisis sintactico, y los resultados|la piezas individuales de la cadena|son tokens. Quizás se acuerde de esas palabras del Capítulo 1.

Python posee un metodo llamado split (partir) en el modulo string (cadena) y en el modulo re (expresiones regulares). La función string.split parte una cadena y la convierte en una lista utilizando un solo carácter como delimitador.

Por ejemplo:

   1: >>> import string

   2: >>> string.split("La hora ha llegado"," ")

   3: ['La', 'hora', 'ha', 'llegado']

En este caso, el delimitador es el carácter espacio, y se parte la cadena en cada espacio.

La función re.split tiene mas 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, [A-z] es el conjunto de todas las letras y [0-9] es el conjunto de todas las cifras. El operador ^ niega un conjunto, y [^0-9] es el conjunto de todo lo que no es un numero, lo cual es exactamente lo que queremos utilizar para partir expresiones en el formato postfijo:

   1: >>> import re

   2: >>> re.split("([^0-9])", "123+456*/")

   3: ['123', '+', '456', '*', '', '/', '']

Fíjese que el orden de los argumentos es diferente del de string.split; el delimitador viene antes de la cadena.

La lista resultante incluye los operandos 123 y 456 y los operadores * y /.

También incluye dos cadenas vacías que se insertan después de los operandos.

Para evaluar una expresión en formato postfijo usaremos el analizador sintactico de la sección anterior y el algoritmo de la sección previa a esa. Para no complicar las cosas, comenzaremos con un evaluador que solo implementa los operadores
+ y *:

   1: def evalPostfijo(expr):

   2:     import re

   3:     listaTokens = re.split("([^0-9])", expr)

   4:     pila = Pila()

   5:     for token in listaTokens:

   6:         if token == '' or token == ' ':

   7:         continue

   8:         if token == '+':

   9:             suma = pila.pop() + pila.pop()

  10:         pila.push(suma)

  11:         elif token == '*':

  12:         producto = pila.pop() * pila.pop()

  13:         pila.push(producto)

  14:     else:

  15:         pila.push(int(token))

  16:         return pila.pop()

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 (56+47)*2):

   1: >>> print evalPostfijo ("56 47 + 2 *")

   2: 206

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 solo se preocupa de la implementación y de si es correcta o no|de acuerdo a las especificaciones del TAD|y no de como se va a utilizar.

A la inversa, el cliente 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 esta tomando en todo
momento.

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.

interfaz: El conjunto de operaciones que definen un TAD.

implementación: El código de programa que satisface los prerrequisitos sintácticos y semánticos de un interfaz.

cliente: Un programa (o la persona que lo escribió) que utiliza un TAD.

proveedor: Un programa (o la persona que lo escribió) que implementa un TAD.

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. estructura de datos genérica: Un tipo de estructura de datos que puede contener datos de cualquier tipo.

infijo: Un metodo de escribir expresiones matemáticas con los operadores entre los operandos.

postfijo: Un metodo de escribir expresiones matemáticas con los operadores después de los operandos.analizar sintacticamente: Examinar una cadena de caracteres o tokens y analizar su estructura gramatical.

token: Un conjunto de caracteres que se tratan como una unidad y son analizados sintacticamente, como las palabras de un lenguaje natural.

delimitador: Un carácter utilizado para separar tokens, como la puntuación en un lenguaje natural.