Ejercicios de Genéricos y Algoritmos

1. Defina e implemente la clase Pila para enteros. Fíjese en la transparencia de clase. Haga
una primera versión con un tamaño máximo fijo que se pasa al constructor (array) y sin
comprobar errores. Luego compruebe errores y lance una excepción en caso de violación
(sacar de una pila vacía o meter en una pila llena).

2. Defina a partir de la Pila anterior una Pila sin restricciones de tamaño. Emplee una lista de
Elementos para que pueda crecer indefinidamente, con referencias al siguiente y al previo
en la lista. Hágala de modo que si se suprimen elementos de la pila no se pierda la
memoria, guárdela por si luego se añaden más elementos no haya que pedir memoria.

3. Defina a partir de la Pila anterior una Pila genérica, que pueda contener cualquier tipo de
Objeto, es decir, que pueda emplearse luego como una pila de Strings o como una pila de
Coches.

4. Defina a partir de la Pila anterior una Pila que valga para todos los Números (Numbers).

5. Use la clase Pila genérica para invertir una palabra. A partir de este programa determinar si
una palabra es palíndromo (se lee igual de izquierda a derecha que de derecha a izquierda:
reconocer, rotor, somos,..)

6. Defina e implemente una función buscar que localice un elemento en un array de

elementos, ambos se le pasan como argumentos. Pruébela con enteros. Luego hágala
genérica, para cualquier tipo de objetos. Suponga que los objetos tienen un método
equals(obj o) que compara el objeto en curso (this) con el objeto que recibe como
parámetro, este método devuelve true si son iguales y false si no lo son.

7. Defina e implemente una función ordenar que ordene enteros de mayor a menor. Recibirá
un array con los enteros a ordenar.

8. Defina a partir de la función ordenar anterior una genérica que permita ordenar objetos.
Recibirá un array con los objetos a ordenar. Suponga que los objetos tienen un método
compareTo(obj o) que permite comparar el objeto en curso (this) con el objeto recibido,
que devuelve -1 si es menor que el recibido, 0 si son iguales y 1 si es mayor que el
recibido. Use esta función con el array de enteros anterior. Apóyese en una función
intercambiar que reciba un array de objetos y dos enteros, que marcan las posiciones de los
elementos a intercambiar.

9. Defina una clase Empleado, con nombre, apellidos, fecha de contratación y número de
empleado y use la función anterior para ordenar un array de Empleados. Use la antigüedad
como criterio a seguir (es “mayor” si es más antiguo). Si entraron en el mismo día, utilice
el número de empleado para desempatar

10. Defina una clase que representa una entrada de una agenda, con el nombre, primer apellido,
segundo apellido, teléfono, e-mail y móvil. Use la función anterior para ordenar un array de
entradas de agenda, usando como criterio de ordenación los apellidos y luego el nombre.

11. Defina e implemente un directorio de teléfonos. En el mismo tendrá entradas de agenda con
los campos anteriores. Se buscará por el nombre y apellidos y devolverá la entrada de
agenda correspondiente. Estos esquemas, para no recorrer toda la información, que puede
tener miles de entradas, se apoyan en tablas Hash, que tienen dos partes, una clave que nos
permite buscar la información (nombre y apellidos) y una información a recuperar asociada
a esa clave.

Una posible implementación es mediante un array de listas de entradas de agenda. Para no

recorrer todas las posiciones del array se dispone de una función hash que nos devuelve un
 código que marca la posición del array donde buscarlo. Por ejemplo, una función que sume
el valor de todos los caracteres del nombre y apellidos y obtenga el módulo respecto al
tamaño del array, esto nos devolverá un entero entre 0 y length-1. Suele no considerarse los
blancos y pasarse las mayúsculas a minúsculas para que no dependa de cómo se escriba el
nombre y los apellidos. En esa posición del array estará una lista con todas entradas que
tengan dicho código, se recorre y se busca, pero ya sobre una pequeña lista.

Pruebe a insertar unas pocas entradas y luego a buscar alguna de ellas. Pruebe a insertar
dos nombre iguales, que cambie simplemente en el orden de los apellidos, para asegurar
que irán a la misma posición.

12. Use otra tabla Hash para contar palabras iguales. Deberá buscar cada palabra y si ya está
incrementar el contador asociado. Si no está deberá insertarla con el contador a 1.

13. Defina una función barajar que reordena aleatoriamente los elementos de un array. Recibe
un array y un objeto de tipo Random que genera números aleatorios. Recorre el array, en
orden decreciente, e intercambia la posición actual con una aleatoriamente elegida que va
desde la primera posición del array a la actual. Puede emplear la función intercambiar
anterior. Para obtener una posición aleatoria llamar al método “int nextInt(int i)” que
devuelve un entero entre 0 y i-1.

14. Construir un array de Strings que represente una baraja americana, con 4 palos (corazones,
picas, diamantes y tréboles) y 12 cartas cada uno (as, 2, 3,…10, paje, reina, rey). Construir
el array con dos bucles anidados. Construir una función repartir que dada una baraja
devuelva una mano de “n” cartas, empezando por el final del array (¡la baraja está boca
abajo!) y que suprime las cartas de la baraja (del array), para evitar poder dar dos veces la
misma carta. Esta función recibe tres argumentos, un array de cartas, la baraja, otro array
de cartas, la mano a construir, y un entero “n” con el número de cartas a dar a esa mano.
Emplee esta función para repartir “n” cartas a “m” jugadores, recibiendo tanto n como m a
través de los argumentos del programa. Previamente debe barajar las cartas, para
asegurarse que nadie sabe que carta se repartirán a cada uno.

15. Construya una calculadora basada en la notación polaca inversa. Esta notación indica
primero los argumentos y luego el operador a aplicar. Es decir, 6+7 se ve como 6 7 +. Un
ejemplo con una expresión más compleja sería: (6+2)*5-8/4 que sería 6 2 + 5 * 8 4 / -. En
un primer paso deberá transforma la expresión a notación polaca inversa. El algoritmo, que
se apoya en el uso de una pila, se muestra a continuación:

• Mientras haya tokens a ser leídos:

o Lea un token.
o Si el token es un número, entonces agréguelo al final de la expresión de
salida
o Si el token es un operador, o1, entonces
 mientras que haya un operador, o2, en el tope de la pila y o1 la
precedencia de o1 es menor o igual que la de o2, retire de la pila o2,
y póngalo al final de la expresión de salida
 ponga o1 en el tope de la pila
o Si el token es un paréntesis abierto, entonces póngalo en la pila
o Si el token es un paréntesis derecho
 Hasta que el token en el tope de la pila sea un paréntesis abierto,
retire (pop) a los operadores de la pila y colóquelos al final de la
expresión de salida.
 Retire y descarte el paréntesis abierto de la pila
 Si la pila se termina sin encontrar un paréntesis abierto, entonces hay
paréntesis sin pareja: Error, expresión errónea
• Cuando no hay más tokens para leer:
o Mientras todavía haya tokens de operadores en el stack
  retire el operador de la pila y póngalo al final de la expresión de
salida
 Si encuentra un paréntesis en la pila, hay paréntesis sin la pareja
correspondiente: Error, expresión errónea.

La precedencia de los operadores es: ^ tiene mayor precedencia que los demás, *, /, y %
tienen la misma entre si y tienen mayor precedencia (deben evaluarse antes) que + y -, que
tienen entre si la misma. A misma precedencia se opera de izquierda a derecha.

Se recomienda apoyarse en dos funciones, esOperador, que devuelve verdadero si el

argumento es un operador, y precedencia, que compara dos operadores y devuelve cual
tiene mayor precedencia.

A modo de ejemplo se muestra la expresión 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3, que debe

transformarse en 3 4 2 * 1 5 - 2 3 ^ ^ / +:

Entrada: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Stack de
Token Acción Salida Notas
operadores
3 agrega token a la salida 3
+ Push token al stack 3 +
4 agrega token a la salida 34 +
* Push token al stack 34 * + * tiene mayor precedencia que +
2 agrega token a la salida 342 *+
Pop stack a la salida 342* + / y * tienen la misma precedencia
/
Push token al stack 342* / + / tiene mayor precedencia que +
( Push token al stack 342* (/+
1 agrega token a la salida 342*1 (/+
- Push token al stack 342*1 -(/+
5 agrega token a la salida 342*15 -(/+
Pop stack a la salida 342*15- ( / + Repite hasta que sea encontrado "("
)
Pop stack 342*15- / + Descarta paréntesis emparejados
^ Push token al stack 342*15- ^ / + ^ tiene mayor precedencia que /
2 agrega token a la salida 342*15-2 ^/+
^ Push token al stack 342*15-2 ^ ^ / + ^ es evaluado de derecha a izquierda
3 agrega token a la salida 342*15-23 ^^/+
end Pop todo el stack a la salida 3 4 2 * 1 5 - 2 3 ^ ^ / +

16. En un segundo paso, implemente un evaluador de expresiones en notación polaca inversa.

El algoritmo es relativamente simple, se basa en usar una pila:
• Si hay elementos en la bandeja de entrada:
i. Leer el primer elemento de la bandeja de entrada.
ii. Si el elemento es un operando, poner el operando en la pila
iii. Si no, el elemento es un operador, con dos argumentos
1. Si hay menos de 2 argumentos en la pila: Error, expresión errónea
2. Si no, tomar los últimos 2 operandos de la pila
3. Evaluar el operador con respecto a los operandos
4. Introducir el resultado (si lo hubiere) en la pila.
• Si hay un sólo elemento en la pila, el valor de ese elemento es el resultado
 • Si hay más de un elemento en la pila: Error, expresión errónea.

A modo de ejemplo se muestra la expresión algebraica 5+((1+2)*4)-3, que se traduce a la

notación polaca inversa como 5 1 2 + 4 * + 3 - y se evalúa de izquierda a derecha según se
muestra en la siguiente tabla:

Entrada Operación Pila Comentario

5 Introducir en la pila 5

1 Introducir en la pila 5, 1

2 Introducir en la pila 5, 1, 2

Tomar los dos últimos valores de la pila (1, 2) y

+ Suma 5, 3
sustituirlos por el resultado (3)

4 Introducir en la pila 5, 3, 4

Tomar los dos últimos valores de la pila (3, 4) y

* Multiplicación 5, 12
sustituirlos por el resultado (12)
Tomar los dos últimos valores de la pila (5, 12) y
+ Suma 17
sustituirlos por el resultado (17)

3 Introducir en la pila 17, 3

Tomar los dos últimos valores de la pila (17, 3) y

− Resta 14
sustituirlos por el resultado (14)