Kompresija stringa

Autor zadatka: Rade Radišić <radisic.rade@uns.ac.rs>

Napisati program koji vrši kompresiju unetog stringa od najviše 99 karaktera. Kompresija se vrši na sledeći način:

  • U unetom stringu se prate ponavljanja određenog karaktera jedan za drugim iste veličine

  • Umesto ponovljenih karaktera, ispisati broj ponavljanja karaktera i sam karakter

  • U slučaju da nema ponavljanja, ne piše se broj ispred karaktera

Na osnovu navedenih pravila kompresije, formirati novi, rezultujući string, koji je neophodno ispisati. Osim kompresovanog stringa, ispisati i procenat kompresije algoritma koji se računa po sledećoj formuli:

\[Kompresija_\% = (1 - \frac{dužina_{kompresovano}}{dužina_{original}}) \cdot 100\]

Napomene

  • S obzirom na to da je ukupni broj karaktera dvocifren broj, broj ponavljanja takođe može biti najviše dvocifren

  • Za ispisivanje procenat karaktera u naredbi printf, navesti %% u format stringu

Primer rada programa:

Unesite string: Primeeeeer nekommmprrrressovanoggg striiiiinga
String nakon kompresije: Prim5er neko3mp4re2sovano3g str5inga
Procenat kompresije: 21.74%

Primer rada programa u slučaju unetog istog slova:

Unesite string: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
String nakon kompresije: 42a
Procenat kompresije: 92.86%

Primer rada programa u slučaju stringa sa karakterima koji se ne ponavljaju:

Unesite string: Primer stringa bez kompresije
String nakon kompresije: Primer stringa bez kompresije
Procenat kompresije: 0.00%

Primer rešenja

 1#include <stdio.h>
 2#include <string.h>
 3
 4#define MAX_STRING 100
 5
 6int main()
 7{
 8    char str[MAX_STRING], str_komp[MAX_STRING];
 9
10    printf("Unesite string: ");
11    fgets(str, MAX_STRING, stdin);
12    int duzina = strlen(str);
13    if (str[duzina - 1] == '\n')
14    {
15        str[duzina - 1] = '\0';
16        duzina--;
17    }
18
19    int i, j, broj_istih = 1, duzina_komp = 0, desetica, jedinica;
20
21    for (i = 0; i < duzina; i++)
22    {
23        for (j = i + 1; j < duzina; j++)
24        {
25            if (str[i] != str[j])
26            {
27                break;
28            }
29
30            broj_istih++;
31        }
32
33        desetica = broj_istih / 10;
34        jedinica = broj_istih % 10;
35
36        if (desetica > 0)
37        {
38            str_komp[duzina_komp++] = desetica + '0';
39            str_komp[duzina_komp++] = jedinica + '0';
40        }
41        else if (jedinica > 1)
42        {
43            str_komp[duzina_komp++] = jedinica + '0';
44        }
45
46        str_komp[duzina_komp++] = str[i];
47
48        i += broj_istih - 1;
49        broj_istih = 1;
50    }
51
52    str_komp[duzina_komp] = '\0';
53
54    printf("String nakon kompresije: %s\n", str_komp);
55    printf("Procenat kompresije: %.2lf%%\n", (1 - (double)duzina_komp / duzina) * 100);
56
57    return 0;
58}