Mes: agosto 2012 Página 19 de 22

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.

Este capítulo presenta dos TADs: la Cola y la Cola Priorizada. En la vida real, una cola es una fila de clientes esperando un servicio de algún tipo. En la mayoría de los casos, el primer cliente de la fila es el primero al que se va a servir. Sin embargo, hay excepciones. En los aeropuertos, a veces se saca de la cola a los clientes cuyos vuelos van a salir pronto. En los supermercados, un cliente educado puede dejar que alguien que lleva pocos productos pase antes.

La regla que determina quien va primero se llama táctica de encolamiento. La táctica de encolamiento mas simple se llama FIFO, de “first-in-firrst-out”, el primero que entra es el primero que sale”. La táctica de encolamiento mas general es el encolamiento priorizado, en la que a cada cliente se le asigna una prioridad y el cliente con la prioridad mas alta pasa primero, sin importar el orden de llegada. Decimos que es la tactica mas general porque la prioridad se puede basar en cualquier cosa: a que hora sale el vuelo; cuantos productos lleva el cliente; cuan importante es el cliente. Por supuesto, no todas las tácticas de prioridad son justas”, pero la justicia siempre es subjetiva.

El TAD Cola y el TAD Cola Priorizada tienen el mismo conjunto de operaciones.

La diferencia esta en la semántica de las operaciones: una cola usa la táctica FIFO, y una cola priorizada (como su propio nombre indica) usa una táctica de encolamiento priorizado.

El TAD Cola se define a través de las siguientes operaciones:

__init__ : Inicializa una cola nueva vacía.

inserta: Añade un elemento a la cola.

quita: Elimina y devuelve un elemento de la cola. El elemento devuelto es el primero que se añadió.

estaVacia: Comprueba si la cola esta vacía.

La primera implementación del TAD Cola al que vamos a echar un vistazo se llama cola enlazada porque esta hecha de objetos Nodo enlazados. He aquí

la definición de la clase:

   1: class Cola:

   2:     def __init__(self):

   3:         self.longitud = 0

   4:         self.cabeza = None

   5:     def estaVacia(self):

   6:         return (self.longitud == 0)

   7:     def inserta(self, carga):

   8:         nodo = Nodo(carga)

   9:         nodo.siguiente = None

  10:         if self.cabeza == None:

  11:             # si la lista esta vac³a el nuevo nodo va el primero

  12:             self.cabeza = nodo

  13:         else:

  14:             # encuentra el ultimo nodo de la lista

  15:             ultimo = self.cabeza

  16:         

  17:         while ultimo.siguiente: ultimo = ultimo.siguiente

  18:             # añadir el nuevo nodo

  19:             ultimo.siguiente = nodo

  20:             self.longitud = self.longitud + 1

  21:     def quita(self):

  22:         carga = self.cabeza.carga

  23:         self.cabeza = self.cabeza.siguiente

  24:         self.longitud = self.longitud - 1

  25:         return carga

Los métodos estaVacia y quita son idénticos a los métodos estaVacia y a quitaPrimero de ListaEnlazada. El metodo inserta es nuevo y un poco mas complicado.

Queremos insertar nuevos elementos al final de la lista. Si la cola esta vacía, simplemente hacemos que cabeza se refiera al nuevo nodo.

En caso contrario, recorremos la lista hasta el ultimo nodo y lo fijamos al final.

Podemos reconocer el ultimo nodo porque su atributo siguiente es None.

En un objeto Cola correctamente construido hay dos invariantes. El valor de longitud debería ser el numero de nodos en la cola, y el ultimo nodo debería tener siguiente igual a None. Crease que este metodo cumple con ambas invariantes.

Normalmente cuando invocamos un metodo, no nos importan los detalles de su implementación. Pero hay un “detalle” que podría interesarnos: el rendimiento típico del metodo.

¿Cuanto tarda, y como var³a el tiempo de ejecución al aumentar el numero de elementos de la colección?

Primero mire quita. Ahí no hay bucles ni llamadas a funciones, dando a entender que el tiempo de ejecución de este metodo es siempre el mismo. Un metodo así se llama operación de tiempo constante. En realidad, el metodo podría
ser ligeramente mas rápido cuando la lista esta vacía porque se salta el cuerpo de la condición, pero esa diferencia no es significativa.

El rendimiento de inserta es muy diferente. En el caso general, tenemos que recorrer la lista para encontrar el ultimo elemento.

Este recorrido cuesta un tiempo proporcional a la longitud de la lista. Como el tiempo de ejecución es función lineal de la longitud, este metodo se llama de tiempo lineal. Comparado con el tiempo constante, es muy pobre.