C style , one argument, recursive, string reverse

[zahy[dot]bnaya[At]gmail[dot]com]

Hi,
I am trying to come up with a c style string reverser, I want it to
take 1 argument
Altough I would never do this in real life. Is there a way to do it?

I wrote this function that fails :

Any idea why it fails?

char * C_recReverse(char * str)
{
char* sub, *res, *tmp;
if (strlen(str) == 0)
return "";
else
{
sub = (char*)malloc(sizeof(char)*strlen(str)-1);
res = (char*)malloc(sizeof(char)*strlen(str));
strcpy(sub,str);
sub[strlen(str)-1] = '\0';
cout<<"Calling with :"<<&str[strlen(str)-1]<<"\t And \t"<<sub<<endl;
strcpy(res,"");
strncpy(res,&str[strlen(str)-1],1);
tmp = C_recReverse(sub);
strcat(res,tmp);
res[strlen(str)] = '\0';
cout<<"res:"<<res<<endl;
free(sub);
free(tmp);
return res;
}

}


Thanks.

 

[Phlip]

zahy[dot]bnaya[At]gmail[dot]com" <[email protected]>

Your spam guard won't work because the actual address is in clear text. Nice
try, but give up spam guarding GMail. I post my raw address, and get >100
spams per day. Google ... Googles them, and nicely keeps 98% of them out of
my Inbox. Props to Google!

I am trying to come up with a c style string reverser,

Exam, right?

Any idea why it fails?

Write it again, from scratch. Sometimes when something fails, just start
again. And get much less complex.

char * C_recReverse(char * str)

Return void. You should reverse str in-place

sub = (char*)malloc(sizeof(char)*strlen(str)-1);

And never allocate anything unless you must.

Try this algorithm:

void reverse(char * str, int len)
if 0 >= len return
swap str[0], str[len-1]
reverse(str + 1, len - 2)

Do you see the reversing in your mind now?

 

[zahy[dot]bnaya[At]gmail[dot]com]

Exam, right?

Actually no, I got it on a job interview, I instinctively tried
the recursive style then I
came to my senses and did it with a loop

char * C_recReverse(char * str)

Return void. You should reverse str in-place

sub = (char*)malloc(sizeof(char)*strlen(str)-1);

And never allocate anything unless you must.

Try this algorithm:

void reverse(char * str, int len)
if 0 >= len return
swap str[0], str[len-1]
reverse(str + 1, len - 2)

Do you see the reversing in your mind now?

I am trying to do something like this:


string recReverse(string str)
{
if(str.empty())
return "";
else
return
str.substr(str.length()-1,str.length()).append(recReverse(str.substr
(0,str.length()-1)));
}

Sorry for the ugly one line return statement.. but this is the idea I
am trying to do in C style strings.

Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!

Thanks.

 

[Tomás]

zahy[dot]bnaya[At]gmail[dot]com posted:

Hi,
I am trying to come up with a c style string reverser, I want it to
take 1 argument
Altough I would never do this in real life. Is there a way to do it?

#include <algorithm>
#include <cstring>

void ReverseString( char * const p )
{
std::reverse( p, p + std::strlen(p) );
}


Or if you don't want the help of the Standard Library...

Untested code:


void ReverseString( register char *p_begin )
{
register char *p_end = p_begin;

while ( *p_end++ );

--p_end;


if ( p_begin == p_end ) return;


for( ; ; ++p_begin, --p_end )
{
switch( p_end - p_begin )
{
case 1:
case 2:
{
char temp = *p_begin;
*p_end = *p_begin;
*p_begin = temp;
return;
}
}
}
}



-Tomás

 

[Tomás]

Tomás posted:

Untested code.

Revised:

void ReverseString( register char *p_begin )
{
register char *p_end = p_begin;

while ( *p_end++ );

--p_end;


if ( p_begin == p_end ) return;


for( ; ; ++p_begin, --p_end )
{
char temp = *p_begin;
*p_end = *p_begin;
*p_begin = temp;

switch( p_end - p_begin )
{
case 1:
case 2:
return;
}
}
}

-Tomás

 

[zahy[dot]bnaya[At]gmail[dot]com]

All previous advices were good and appreciated..
Sorry about my stubborness I am really intrested to know why my code
does not work
I remarked it better.

I know it is probably not the best way to do it but can you see a
problem in there?
not for the sake of solving the problem , just for education...
Thanks.



/*
Algorithm pseudo:

reverse(str)
if(str="")
return ""
else
return append(last_char(str),
reverse(all_but_last_char(str))
*/

char * C_recReverse(char * str)
{
// Sub is storing the substring
// res is the returned string
// tmp is for storing the previos result so it can be deleted
char* sub, *res, *tmp;

if (strlen(str) == 0)
return "";
else
{
/* the sub and res are allocated per recursion stack*/
sub = (char*)malloc(sizeof(char)*strlen(str)-1);
res = (char*)malloc(sizeof(char)*strlen(str));

/* prepering the substring, stored on the heap*/
strcpy(sub,str);
sub[strlen(str)-1] = '\0';


/* the return value is preperaed , filled with last char*/
strcpy(res,"");
strncpy(res,&str[strlen(str)-1],1);

/* calling the reverse function of the "sub" stored
on local variable tmp*/
tmp = C_recReverse(sub);

/* adding the result of substring reverse to the result string (res)
*/
strcat(res,tmp);

/*"closing" the string (???) */
res[strlen(str)] = '\0';

/* Freeing the substring, I dont really need it anymore*/
free(sub);

/* Freeing the "previous" recursion closure,
Can I do it? I think this is the
problem */
free(tmp);
return res;
}
}


Thanks.

 

[Phlip]

void ReverseString( register char *p_begin )

Mr Manners reminds the Gentle Poster not to do others' homework, no matter
how great the temptation to show off!

We don't need a reputation here that will draw more low-quality posts!

And it's not "homework" because a professor at an acredited university
assigned it; it's homework because it's a learning project.

 

[Tomás]

Phlip posted:

Mr Manners reminds the Gentle Poster not to do others' homework, no
matter how great the temptation to show off!

Guilty. : )

We don't need a reputation here that will draw more low-quality posts!

But it sure would be fun to have a show-off tournament.

And it's not "homework" because a professor at an acredited university
assigned it; it's homework because it's a learning project.

I was about to say we should use ROT-13 for showing off... but then I
realised efforts would go unnoticed for the most part. ;-)


-Tomás

 

[Thomas J. Gritzan]

All previous advices were good and appreciated..
Sorry about my stubborness I am really intrested to know why my code
does not work
I remarked it better.

I know it is probably not the best way to do it but can you see a
problem in there?
not for the sake of solving the problem , just for education...
Thanks.

Yes. You forget, that
a) you can't free() space you did't malloc().
b) strings are zero-terminated.

/*
Algorithm pseudo:

reverse(str)
if(str="") // return ""
else
return append(last_char(str),
reverse(all_but_last_char(str))
*/

char * C_recReverse(char * str)
{
// Sub is storing the substring
// res is the returned string
// tmp is for storing the previos result so it can be deleted
char* sub, *res, *tmp;

if (strlen(str) == 0)

{
// return "";

res= (char*)malloc(1);
res[0] = '\0';
return res;
}

else
{
/* the sub and res are allocated per recursion stack*/
sub = (char*)malloc(sizeof(char)*strlen(str)-1);
res = (char*)malloc(sizeof(char)*strlen(str));

You will copy the entire string "str" into "sub", so "sub" has to hold
enough space for strlen(str)+1.

"res" has to hold "str" reverse, so dito.

sizeof(char) is defined to be 1.

/* prepering the substring, stored on the heap*/
strcpy(sub,str);
sub[strlen(str)-1] = '\0';


/* the return value is preperaed , filled with last char*/
strcpy(res,"");
strncpy(res,&str[strlen(str)-1],1);

Bad.
res is not null-terminated after this.

/* calling the reverse function of the "sub" stored
on local variable tmp*/
tmp = C_recReverse(sub);

/* adding the result of substring reverse to the result string (res)
*/
strcat(res,tmp);

/*"closing" the string (???) */
res[strlen(str)] = '\0';

/* Freeing the substring, I dont really need it anymore*/
free(sub);

/* Freeing the "previous" recursion closure,
Can I do it? I think this is the
problem */
free(tmp);
return res;
}
}

This is evil C++ code, and I think its evil C, too.

Thomas

 

[Phlip]

Guilty. : )

Thank you. Actually, the admonition is against doing homework where the
student did nothing and posted the assignment. So the student posting code
and you posting contrary code is perfectly acceptable.

 

[Kanenas]

On 29 May 2006 12:15:43 -0700, "zahy[dot]bnaya[At]gmail[dot]com"

First, a C newsgroup would be better suited for this discussion,
despite the fact the source in your original posting was tainted by
C++ iostreams. We're so far into it at this point we may as well
finish it here.

All previous advices were good and appreciated..
Sorry about my stubborness I am really intrested to know why my code
does not work

That's an admirable trait in a programmer.

I remarked it better.

I know it is probably not the best way to do it but can you see a
problem in there?

I see three levels of problems. The most basic you're already aware
of: the recursive approach is not the best design because of time and
space inefficiencies. The other two are problems of logic (i.e. is
the implementation correct?) and problems of style/micro-optimization
(like the basic level but applied to statements rather than design).

When I'm having problems with an algorithm, I follow Feynman's lead
and try it out with a specific test case. I'll use a call of
'C_recReverse("12345")' as an example.

not for the sake of solving the problem , just for education...
Thanks.

It is an interesting approach, and even though there turns out to be a
better one, considering alternate approaches keeps the mind flexible.

/*
Algorithm pseudo:

reverse(str)
if(str="")
return ""
else
return append(last_char(str),
reverse(all_but_last_char(str))
*/

char * C_recReverse(char * str)
{
// Sub is storing the substring
// res is the returned string
// tmp is for storing the previos result so it can be deleted
char* sub, *res, *tmp;

if (strlen(str) == 0)
return "";
else
{
/* the sub and res are allocated per recursion stack*/
sub = (char*)malloc(sizeof(char)*strlen(str)-1);

Logic error. 'strlen("12345")' == 5, so 'sub' is allocated 4
characters, one of which must be '\0' (e.g. 'sub' can hold "123").
Need to hold 6 ('strlen(sub)+1).

res = (char*)malloc(sizeof(char)*strlen(str));

Logic error. 'res' can hold 5 characters (e.g. "5432"), but need to
hold 6.

/* prepering the substring, stored on the heap*/
strcpy(sub,str);

Logic error. Copies 6 characters from 'str' into 'sub'. That's 2
characters more than 'sub' can hold. Undefined behavior; possible
segfault.

sub[strlen(str)-1] = '\0';

Logic error. In our example, that's 'sub[4] = 0'. The maximum legal
index for 'sub' is 3.

/* the return value is preperaed , filled with last char*/
strcpy(res,"");
strncpy(res,&str[strlen(str)-1],1);

Logic error: 'res' may be improperly terminated. Imagine 'res'
points to previously used memory ("raths outgrabe."). After
'strcpy(res,"")', 'res' points to "\0aths outgrabe.". After the 2nd
strcpy, 'res' points to "5aths outgrabe."; there's now no terminator
within the bounds of 'res'. The next call to 'strcat' will place
characters after the '.'. Another possible segfault.
Micro-optimization: Each line assigns a single character within 'res'.
More efficient alternative:
res[0] = str[strlen(str)-1];
res[1] = '\0';

/* calling the reverse function of the "sub" stored
on local variable tmp*/
tmp = C_recReverse(sub);

/* adding the result of substring reverse to the result string (res)
*/
strcat(res,tmp);

/*"closing" the string (???) */
res[strlen(str)] = '\0';

Micro-optimization. 'strcat' will terminate the destination string;
no need for this line.

/* Freeing the substring, I dont really need it anymore*/
free(sub);

/* Freeing the "previous" recursion closure,
Can I do it? I think this is the
problem */
free(tmp);

This step is necessary. 'C_recReverse' allocates a char array
(pointed to by 'res') that it doesn't free. After a recursive call to
'C_recReverse', 'tmp' points to such an array and the calling
'C_recReverse' is now responsible for the memory.