I'm working on this problem to decode a compressed string to its original. Does anyone know how to solve this problem? It should decode "W28bA4B2CB2CB2Ca3" to its original "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa", I don't know how to extract number from this string
int getcount(char *rle)
{
int count=0;
return count;
}
char *decode_rle(char *rle, char *str)
{
char *ptr=rle;
char *ptrend=&rle[strlen(rle)];
char decoding[100];
int i=0,j=0,count=0, digit=0;
strcpy(str, "");
```
str[i] = '\0';
return str;
}
int main(){
char str_org[]="WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa";
char rle[100];
runlengthencoding(str_org,rle);
printf("str_org:[%s] => rle:[%s]\n",str_org,rle);
char str_dec[100];
decode_rle(rle,str_dec);
printf("rle:[%s] => str_dec:[%s]\n",rle, str_dec);
return 0;
}
CodePudding user response:
- You can define the function to extract numbers from
RLE
encoded strings as below. Call it every time you encounter a digit in encoded-string.
#include <ctype.h>
static inline int
rle_ext_count (const char *rle) {
int count = 0;
for (int di = 0; isdigit (rle[di]); di) {
count = count * 10 rle[di] - '0';
}
return count;
}
With
static inline
we're telling compiler that this function is local to translation unit, and try toinline
this small piece of code wherever it's called to mitigate small functions' call overheads.Then your
RLE-Decode
of a validRLE
encoded string will be :
// Note it doesn't validates the encoding
// e.g "W28bA4B2CB2CB2Ca3" to "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa"
int rle_decode (const char *rle, char *data) {
int dlen = 0;
for (int ci = 0; rle[ci]; /* ci */) {
int repeat_count = 0;
if (isdigit(rle[ci])) {
repeat_count = rle_ext_count(rle ci);
while (isdigit(rle[ci])) ci; // skip digits;
}
if (repeat_count) {
if (!dlen) return -1; // only this validation is necessary (rle can't begin with a number)
for (int rch = data[dlen -1], ri = 1; ri < repeat_count; )
data[dlen ] = rch;
} else
data[dlen ] = rle[ci ];
}
data[dlen] = '\0';
return dlen;
}
- Assuming you already have a working
RLE-Encode
function, testingrle_decode()
:
int main() {
// char str_org[] = "WWWWWWWWWWWWWWWWWWWWWWWWWWWWbAAAABBCBBCBBCaaa";
char rle[] = "W28bA4B2CB2CB2Ca3";
char str_dec[100];
int dec_len = rle_decode (rle, str_dec);
if (dec_len < 0) {
printf ("ERROR: Decoding RLE string [%s]\n", rle);
return 1;
}
printf ("rle:[%s] => str_dec:[%s] Length %d\n", rle, str_dec, dec_len);
return 0;
}
- Validating a RLE-String is a different question.
CodePudding user response:
Here's a decoding program that produces the desired output:
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
int main()
{
int c, lst = EOF;
int n = 0;
while ((c = getchar()) != EOF) {
if (isdigit(c)) {
n *= 10;
n = c - '0';
} else {
if (lst != EOF) {
if (n == 0) n ; /* 0 -> 1 */
for (int i = 0; i < n; i )
putchar(lst);
lst = EOF; /* already printed */
}
n = 0;
lst = c;
}
}
return 0;
}
if you want it decoded as arrays, you can use the following routine:
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
char *rle_decode(char *src, char *dst, size_t sz)
{
int c, lst = 0;
int n = 0;
char *saved = dst;
while ((c = *src ) != 0) {
if (isdigit(c)) {
n *= 10;
n = c - '0';
} else {
if (lst) {
if (n == 0) n ; /* 0 -> 1 */
for (int i = 0; i < n; i )
if (sz--) *dst = lst;
lst = 0; /* already printed */
}
n = 0;
lst = c;
}
}
if (lst) {
if (n == 0) n ;
for (int i = 0; i < n; i )
if (sz--) *dst = lst;
}
*dst = 0;
return saved;
}
int main()
{
char buffer[256];
char source[] = "W28bA4B2CB2CB2Ca3";
printf("rle_decode(\"%s\", buffer, %zd) => \"%s\"\n",
source, sizeof buffer,
rle_decode(source, buffer, sizeof buffer));
return 0;
}