CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2002

$[\/]$

CI-1201 Programación II

Examen #2 [solución]

Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] ENCOGE.cpp es un programa que sirve para reducir el tamaño del archivo de texto que recibe como entrada, escogiendo la palabra más corta entre todas los sinónimos, y eleminando todas las que no son significativas. ENCOGE.cpp procesa los siguientes archivos:

SINONIM: Archivo de palabras de sinónimos

IGNORE: Archivo de palabras no significativas

TEXTO: Archivo de renglones a procesar

El archivo SINONIM contiene renglones en los que aparecen dos palabras que tienen el mismo significado. Por ejemplo, este archivo puede contener las parejas (auto, carro), (bello, lindo), etc. Una palabra es simplemente un grupo de letras y/o números delimitado por espacios en blanco. El archivo IGNORE está compuesto de renglones en los que aparece una sólo palabra.

Su programa debe leer los archivos SINONIM e IGNORE para construir dos diccionarios internos de trabajo. Luego su programa procederá a procesar palabra por palabra el archivo TEXTO. La salida de su programa será el archivo RESULT. Si una palabra de TEXTO aparece en SINONIM, entonces aparecerá sustituida por su sinónimo en RESULT. Por el contrario, ninguna palabra que aparezca en IGNORE aparacerá en RESULT. Las demás palabras de TEXTO que no aparezcan en los archivos SINONIM o IGNORE serán copiadas exactamante como aparecen en RESULT. En el siguiente ejemplo se muestra el efecto de su programa.

SINONIM IGNORE TEXTO RESULT

(auto carro) a la casa y el carro casa el auto

(via ruta) son son objetos objetos

(lujosos suntuarios) la suntuarios lujosos

(auto automotor) y

2) [33 pts] Implemente un iterador que permita recorrer, en orden de MAYOR a menor, los valores almaceandos en una lista. Haga su trabajo manera similar a su implementación de la tercera tarea programada.

3) [33 pts] Considere la clase lista cuyo modelo (diagrama) aparece en la figura de abajo.

 L ──>─┐
       │
       v
┌────────┬───┐   ┌────────┬───┐   ┌────────┬───┐
│ elem_1 │ *─┼──>│ elem_2 │ *─┼──>│ elem_3 │ *─┼─> NIL
└────────┴───┘   └────────┴───┘   └────────┴───┘

3.a) [7 pts] Haga las declaración para la clase lista. Incluya en el Rep apenas lo suficiente para implementar la operación lista::k_splice(k).

3.b) [7 pts] Especifique la operación la operación lista::k_splice(k), que traslada al principio de la lista sus últimos k valores, pero sin copiarlos.

3.c) [19 pts] Implemente lista::k_splice(k).

4) [33 pts] Una pila se puede obtener a partir del contenedor lista implementando las operaciones Push() y Pop().

4.a) [5 pts] Especifique una función booleana Parentesis_Balanceados() que regresa el valor true si los paréntesis contenidos en la hilera que recibe como argumento están balanceados. Procese letra por letra la hilera, e ignore todas las letras en que no sean un paréntesis. Para que su función sea más flexible, permita que trabaje con los siguientes tipos de paréntesis: ( ) [ ] { } < >.

4.b) [11 pts] Use métodos inline para declarar y definir el contenedor pila, a partir de las operaciones de la lista de la segunda tarea programada. No se le meta al Rep.

Recuerde que la diferencia entre "definir" y "declarar" un objeto en C++ es que las declaraciones se ponen en los archivos de encabezados <*.h> y <*.hpp>, mientras que las definiciones están en los archivos de implementación <*.c> y <*.cpp>.

Las declaraciones corresponden a la especificación.

Las definiciones corresponden a la implementación. Para facilitarle memorizar este hecho, asocie la palabra "definición" con la directiva #define que sirve para implementar macros en C++:
#define max(a,b) ( (a)>(b) ? (a) : (b) )

4.c) [6 pts] Explique por qué es conveniente que todas las operaciones de la pila sean métodos inline.

4.d) [11 pts] Implemente Parentesis_Balanceados(). Al hacer su implementación use las operaciones definidas para la pila.

Soluciones

$[/\]$

SINONIM:	Archivo de palabras de sinónimos
IGNORE:	Archivo de palabras no significativas
TEXTO:	Archivo de renglones a procesar

SINONIM	IGNORE	TEXTO	RESULT
(auto carro)	a	la casa y el carro	casa el auto
(via ruta)	son	son objetos	objetos
(lujosos suntuarios)	la	suntuarios	lujosos
(auto automotor)	y