Realizar conteo de ocurrencias de palabras en una oración con C
Ya estamos aquí con otro tutorial de C. Lo que haremos ahora será analizar una cadena o string, contar las palabras que tiene (ignorando puntos, espacios y signos) y luego agruparlas para indicar la frecuencia con la que se repiten.
Este ejercicio puede resolverse de varias maneras pero yo he decidido hacerlo a través de una pila en donde almacenaremos structs.
Aquí puedes ver un ejemplo de una pila de enteros, la modificaremos un poco para que funcione con structs.
¿Por qué una pila en lugar de un arreglo? muy fácil, porque la pila puede tener un tamaño infinito.
Al final generaremos una tabla como la que se ve en la imagen (aunque la frecuencia es 1 en la mayoría de veces, la función trabaja bien; el problema fue que la cadena de prueba no tenía muchas palabras repetidas):
El struct que tiene los detalles de palabras
Para no complicarnos, he creado un struct que tiene la palabra y su frecuencia. La palabra es una cadena, o más bien un arreglo de caracteres. Y la frecuencia un entero.
#define MAXIMA_LONGITUD_PALABRA 100
struct DetalleDePalabra {
char palabra[MAXIMA_LONGITUD_PALABRA];
int frecuencia;
};
Como no podemos tener strings infinitas le hemos puesto un límite de 100. Se podría ampliar pero es un simple ejercicio, no algo de la vida real (aunque igualmente funciona de maravilla).
Más tarde crearemos un nodo que nos ayudará a formar nuestra pila. Ese nodo tendrá como dato un detalle de palabra:
struct nodo {
struct DetalleDePalabra detalleDePalabra;
struct nodo *siguiente;
};
También tendrá un apuntador a otro nodo; esto es por la naturaleza de la pila (si no entiendes, mira el post de las pilas que dejé al inicio).
Operaciones de la pila de structs
El ejercicio anterior fue para demostrar en todo su esplendor cómo trabajar con pilas en C. Sin embargo ahora aplicaremos esas pilas y quitaremos lo innecesario; por lo que quedan las operaciones agregar e imprimir.
El método de agregar pone un nuevo elemento, y el de imprimir recorre toda la pila para imprimir las palabras en una bonita tabla con frecuencias.
Adicionalmente (y este no es un método de las pilas) tenemos una función que busca una palabra… si ya existe, le aumenta la frecuencia.
Si no existe, entonces agrega un nuevo elemento a la pila y le pone la frecuencia en 1. Dicho método se llama agregarPalabra.
El prototipo de las funciones queda así:
void agregar(struct DetalleDePalabra detalleDePalabra);
void agregarPalabra(char palabra[MAXIMA_LONGITUD_PALABRA]);
void imprimir(void);
Analizaremos una a una; sin caer en lo redundante.
Agregar a la pila
Es la operación push. Agrega un struct y ya:
void agregar(struct DetalleDePalabra detalleDePalabra) {
// El que se agregará; reservamos memoria
struct nodo *nuevoNodo = malloc(sizeof(struct nodo));
// Le ponemos el dato
nuevoNodo->detalleDePalabra = detalleDePalabra;
// Y ahora el nuevo nodo es el superior, y su siguiente
// es el que antes era superior
nuevoNodo->siguiente = superior;
superior = nuevoNodo;
}
Insertar palabra en la pila en caso de que no exista
Este sí es más complicado. Recorre toda la pila y va comparando sin ser sensible a mayúsculas y minúsculas con strcasecmp.
Si encuentra la palabra, le aumenta la frecuencia y termina la función.
Si el ciclo termina y llega al fondo de la pila, entonces llama al método agregar, le pasa un nuevo struct que tiene la palabra establecida en la búsqueda; y la frecuencia en 1.
void agregarPalabra(char palabra[MAXIMA_LONGITUD_PALABRA]) {
struct nodo *temporal = superior;
while (temporal != NULL) {
// Comprobar si la encontramos
int resultadoDeComparacion =
strcasecmp(temporal->detalleDePalabra.palabra, palabra);
// Si es 0, entonces sí
if (resultadoDeComparacion == 0) {
// Aumentar frecuencia y terminar ciclo y función
temporal->detalleDePalabra.frecuencia++;
return;
}
temporal = temporal->siguiente;
}
// Si no encontramos nada, agregamos una nueva
struct DetalleDePalabra detalleDePalabra;
strcpy(detalleDePalabra.palabra, palabra);
detalleDePalabra.frecuencia = 1; // La primera vez es 1
agregar(detalleDePalabra);
}
Por cierto, podemos pensar que para asignar la palabra usaríamos:
detalleDePalabra.palabra = palabra
Pero no se puede asignar así; tenemos que copiar la cadena a un búfer, por eso usamos strcpy
.
Imprimir resultados del conteo
El último método genera una tabla parecida a las que crea MySQL en la terminal.
Es generar encabezados, recorrer la pila y luego dibujar el pie:
void imprimir(void) {
// Un simple encabezado, no hay que confundirse
char guiones[] = "--------------------";
printf("+%s+%s+\n", guiones, guiones);
printf("|%-20s|%-20s|\n", "PALABRA", "FRECUENCIA");
printf("+%s+%s+\n", guiones, guiones);
// A partir de aquí el código sí importa; simplemente recorremos la pila
struct nodo *temporal = superior;
while (temporal != NULL) {
printf("|%-20s|%-20d|\n", temporal->detalleDePalabra.palabra,
temporal->detalleDePalabra.frecuencia);
temporal = temporal->siguiente;
}
// El pie
printf("+%s+%s+\n", guiones, guiones);
}
Separar y contar palabras
Bueno, ya tenemos nuestra pila lista para trabajar. Lo que falta es leer toda una oración o texto e ir agregando cada palabra limpia.
Para ello usamos algo así como un split de la vieja escuela con strtok. Esta función divide o parte una cadena si encuentra delimitadores que le indicamos..
Recomiendo leer: dividir cadenas en C con strtok
Pero comencemos definiendo nuestra cadena que analizaremos, la cual es un poema de Ozymandias o algo así que sale en Breaking Bad:
char granCadena[] =
"Conoci a un viajero de una tierra antigua quien dijo: dos enormes "
"piernas petreas, sin su tronco se yerguen en el desierto. A su lado, en "
"la arena, semihundido, yace un rostro hecho pedazos, cuyo cenio y mueca "
"en la boca, y desden de frio dominio, cuentan que su escultor "
"comprendio bien esas pasiones las cuales aun sobreviven, grabadas en "
"estos inertes objetos, a las manos que las tallaron y al corazon que "
"las alimento. Y en el pedestal se leen estas palabras: 'Mi nombre es "
"Ozymandias, rey de reyes: Contemplad mis obras, poderosos, y "
"desesperad' Nada queda a su lado. Alrededor de la decadencia de estas "
"colosales ruinas, infinitas y desnudas se extienden, a lo lejos, las "
"solitarias y llanas arenas";
char delimitador[] = ",;:. \n!\"'"; // coma, punto y coma, dos puntos, punto,
// espacios y saltos de línea
Esa cadena también podría proporcionarla el usuario, no lo olvides.
De ahí el delimitador es un arreglo de caracteres. Cada que strtok encuentre uno de ellos, separará la cadena. De este modo ignoramos espacios, comas y esas cosas.
Ahora sí viene la magia, y justo aquí recorremos toda la cadena, tomamos cada palabra y trabajamos con ella:
// Sacar el primer token
char *token = strtok(granCadena, delimitador);
// Y sacar todos los siguientes
// Por cada uno, agregar la palabra a la pila
while (token != NULL) {
agregarPalabra(token);
token = strtok(NULL, delimitador);
}
// Luego de agregar todas las palabras, imprimimos nuestra pila
imprimir();
La primera vez esta función devuelve el primer token que encuentre; o sea, la primer palabra que no sea un delimitador. Si no encontrara nada devolvería NULL, por eso la comprobación.
En caso de que sí regrese algo, entonces la agregamos. Y hacemos un ciclo while que seguirá hasta que ya no encontremos más palabras. En cada iteración agregamos la palabra.
Al terminar el ciclo, imprimimos los resultados.
Código completo
El código completo en donde ponemos todo junto lo dejo en un gist a continuación:
/**
Contar la frecuencia con la que ocurre una palabra dada una oración
Se utiliza una pila para poder tener palabras infinitas
@author parzibyte
Visita: https://parzibyte.me/blog
*/
#include <stdio.h> // printf
#include <stdlib.h> // malloc y free
#include <string.h> // strcasecmp
#define MAXIMA_LONGITUD_PALABRA 100
struct DetalleDePalabra {
char palabra[MAXIMA_LONGITUD_PALABRA];
int frecuencia;
};
struct nodo {
struct DetalleDePalabra detalleDePalabra;
struct nodo *siguiente;
};
void agregar(struct DetalleDePalabra detalleDePalabra);
void agregarPalabra(char palabra[MAXIMA_LONGITUD_PALABRA]);
void imprimir(void);
// Todo comienza con el nodo superior :-)
struct nodo *superior = NULL;
int main() {
// Sin acentos, porque se imprime mal. El original es:
/*
Conocí a un viajero de una tierra antigua
quien dijo: «dos enormes piernas pétreas, sin su tronco
se yerguen en el desierto. A su lado, en la arena,
semihundido, yace un rostro hecho pedazos, cuyo ceño
y mueca en la boca, y desdén de frío dominio,
cuentan que su escultor comprendió bien esas pasiones
las cuales aún sobreviven, grabadas en estos inertes objetos,
a las manos que las tallaron y al corazón que las alimentó.
Y en el pedestal se leen estas palabras:
"Mi nombre es Ozymandias, rey de reyes:
¡Contemplad mis obras, poderosos, y desesperad!"
Nada queda a su lado. Alrededor de la decadencia
de estas colosales ruinas, infinitas y desnudas
se extienden, a lo lejos, las solitarias y llanas arenas»
*/
char granCadena[] =
"Conoci a un viajero de una tierra antigua quien dijo: dos enormes "
"piernas petreas, sin su tronco se yerguen en el desierto. A su lado, en "
"la arena, semihundido, yace un rostro hecho pedazos, cuyo cenio y mueca "
"en la boca, y desden de frio dominio, cuentan que su escultor "
"comprendio bien esas pasiones las cuales aun sobreviven, grabadas en "
"estos inertes objetos, a las manos que las tallaron y al corazon que "
"las alimento. Y en el pedestal se leen estas palabras: 'Mi nombre es "
"Ozymandias, rey de reyes: Contemplad mis obras, poderosos, y "
"desesperad' Nada queda a su lado. Alrededor de la decadencia de estas "
"colosales ruinas, infinitas y desnudas se extienden, a lo lejos, las "
"solitarias y llanas arenas";
char delimitador[] = ",;:. \n!\"'"; // coma, punto y coma, dos puntos, punto,
// espacios y saltos de línea
// Sacar el primer token
char *token = strtok(granCadena, delimitador);
// Y sacar todos los siguientes
// Por cada uno, agregar la palabra a la pila
while (token != NULL) {
agregarPalabra(token);
token = strtok(NULL, delimitador);
}
// Luego de agregar todas las palabras, imprimimos nuestra pila
imprimir();
}
void agregar(struct DetalleDePalabra detalleDePalabra) {
// El que se agregará; reservamos memoria
struct nodo *nuevoNodo = malloc(sizeof(struct nodo));
// Le ponemos el dato
nuevoNodo->detalleDePalabra = detalleDePalabra;
// Y ahora el nuevo nodo es el superior, y su siguiente
// es el que antes era superior
nuevoNodo->siguiente = superior;
superior = nuevoNodo;
}
void agregarPalabra(char palabra[MAXIMA_LONGITUD_PALABRA]) {
struct nodo *temporal = superior;
while (temporal != NULL) {
// Comprobar si la encontramos
int resultadoDeComparacion =
strcasecmp(temporal->detalleDePalabra.palabra, palabra);
// Si es 0, entonces sí
if (resultadoDeComparacion == 0) {
// Aumentar frecuencia y terminar ciclo y función
temporal->detalleDePalabra.frecuencia++;
return;
}
temporal = temporal->siguiente;
}
// Si no encontramos nada, agregamos una nueva
struct DetalleDePalabra detalleDePalabra;
strcpy(detalleDePalabra.palabra, palabra);
detalleDePalabra.frecuencia = 1; // La primera vez es 1
agregar(detalleDePalabra);
}
void imprimir(void) {
// Un simple encabezado, no hay que confundirse
char guiones[] = "--------------------";
printf("+%s+%s+\n", guiones, guiones);
printf("|%-20s|%-20s|\n", "PALABRA", "FRECUENCIA");
printf("+%s+%s+\n", guiones, guiones);
// A partir de aquí el código sí importa; simplemente recorremos la pila
struct nodo *temporal = superior;
while (temporal != NULL) {
printf("|%-20s|%-20d|\n", temporal->detalleDePalabra.palabra,
temporal->detalleDePalabra.frecuencia);
temporal = temporal->siguiente;
}
// El pie
printf("+%s+%s+\n", guiones, guiones);
}
Bonus: frecuencia de palabras de una oración que el usuario introduzca
El poema que puse no nos da la forma de que juguemos con él si no somos programadores. Por ello vamos a modificar un poco la función de manera que el usuario introduzca la cadena y más tarde el programa imprima los valores.
Nada cambiará, únicamente la declaración de la cadena.
char granCadena[MAXIMA_LONGITUD_ORACION_USUARIO];
printf("Pon una cadena de hasta %d caracteres, presiona enter y te diré la "
"frecuencia de las "
"palabras:\n",
MAXIMA_LONGITUD_ORACION_USUARIO);
// fgets para escanear también los espacios; y prevenir un desbordamiento de
// búfer
fgets(granCadena, MAXIMA_LONGITUD_ORACION_USUARIO, stdin);
De ahí el algoritmo es el mismo, únicamente cambia la declaración como decía.
En mi caso probé con una cadena sin sentido, pero que demostrará lo abordado en el post: