Reverse a string in place

R

rajash

Thanks for the additional comments.

Here is a solution to an exercise I had problems with. I still don't
think it's really what's wanted as it uses a "state variable" n - but
I can't see how to do it without this (or changing the function to
take an extra argument). Thanks for any hints.

#include<stdio.h>

#define SWAP(a,b) { char x; x=(a); (a)=(b); (b)=x; }

void reverse();

main(int argc, char**argv)
{
if(argc>1) {
reverse(argv[1]);
printf("%s\n", argv[1]);
} else
printf("Unspecified error\n");
}

void reverse(char *s)
{
static int n=-1;
if(n==-1)
n=strlen(s)-1;
SWAP(*s, s[n]);
if((n-=2)>=0)
reverse(s+1);
else
n=-1; /* make sure function is reentrant */
}
 
L

Lew Pitcher

Thanks for the additional comments.

Here is a solution to an exercise I had problems with. I still don't
think it's really what's wanted as it uses a "state variable" n - but
I can't see how to do it without this (or changing the function to
take an extra argument). Thanks for any hints.

void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end); --end;
/* end points to last character in string */

while (string > end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}
}
 
L

Lew Pitcher

Oops... pardon my typo...

void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end); --end;
/* end points to last character in string */

while (string > end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}

}


void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end); --end;
/* end points to last character in string */

while (string < end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}
}
 
R

rajash

Lew said:
void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end); --end;
/* end points to last character in string */

while (string > end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}
}

Uhh yes! I should have said clearly that it's Exercise 4.13 - write a
**recursive** version of reverse(s).
 
W

Willem

(e-mail address removed) wrote:
) Uhh yes! I should have said clearly that it's Exercise 4.13 - write a
) **recursive** version of reverse(s).

That's silly. Reversing a string is clearly an iterative operation.
However, any iteration can be easily transformed into a tail recursion.

Note, also, that it is perfectly valid to have two functions.
One that recurses, and one that makes the initial call to the other.

Anyways, Here's a stab at a very inefficient and silly solution, using
a single function:

void reverse(char *string)
{
size_t len = strlen(string);
if (len > 1) {
char tmp = string[len-1];
string[len-1] = 0;
reverse(string + 1);
string[len-1] = string[0];
string[0] = tmp;
}
}


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
B

Ben Bacarisse

Thanks for the additional comments.

Here is a solution to an exercise I had problems with. I still don't
think it's really what's wanted as it uses a "state variable" n - but
I can't see how to do it without this (or changing the function to
take an extra argument). Thanks for any hints.

#include<stdio.h>

#define SWAP(a,b) { char x; x=(a); (a)=(b); (b)=x; }

I'd either just write this code out, or I'd make this a function. If
I really needed it to be a macro, I'd use the "do {} while (0)" idiom
so as to get syntactic unit that can be followed by a ; and remain a
single statement.
void reverse();

This is not a prototype for reverse, just a declaration. Tell the
full story by writing:

void reverse(char *s);
main(int argc, char**argv)

int main is better and required in C99.
{
if(argc>1) {
reverse(argv[1]);
printf("%s\n", argv[1]);
} else
printf("Unspecified error\n");
}

void reverse(char *s)
{
static int n=-1;
if(n==-1)
n=strlen(s)-1;
SWAP(*s, s[n]);
if((n-=2)>=0)
reverse(s+1);
else
n=-1; /* make sure function is reentrant */
}

Spaces have come right down in price recently after the discovery of
the Peruvian space deposits. Help yourself to a few more.

Reverse is not a natural candidate for recursion (even in functional
languages a little care is needed to stop it being very inefficient)
but in C we have some extra options because we can modify the string.
I'd write it like this:

void rev(char *start, char *end)
{
if (start + 1 >= end)
return;
else {
char t = end[-1];
end[-1] = *start;
*start = t;
rev(start + 1, end - 1);
}
}

void reverse(char *s)
{
rev(s, strchr(s, 0));
}
 
P

pete

Lew said:
Oops... pardon my typo...



void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end); --end;
/* end points to last character in string */

Unless the string is (""),
in which case (end) is undefined.
 
L

Lew Pitcher

pete said:
Unless the string is (""),
in which case (end) is undefined.

Good catch. I hadn't thought of that edge case when I put together the code.

So, substitute
for (end = string ; *end ; ++end);
if (*end) --end; else return;


--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------
 
C

CBFalconer

pete said:
Lew Pitcher wrote:
.... snip ...


Unless the string is (""), in which case (end) is undefined.

So try:

void reverse(char *string) {
char *end, temp;

for (end = string; *end; end++) continue;
/* leaving *end == 0 */
while (string < end) {
temp = *string;
*string++ = *(--end);
*end = temp;
)
} /* reverse, untested */
 
R

Roland Pibinger

So, substitute
for (end = string ; *end ; ++end);
if (*end) --end; else return;

Wouldn't it be great if C had a function that just returned the length
of a 'string'?
 
P

pete

Roland said:
Wouldn't it be great if C had a function that just returned the length
of a 'string'?

You lose portability on freestanding systems
if your functions use strlen.
 
L

Lew Pitcher

Roland said:
Wouldn't it be great if C had a function that just returned the length
of a 'string'?


Well, there /is/ a standard function that returns the length of a string. But,
why would you want to complicate a simple function like reverse() by calling
external functions like strlen()? reverse() has all the information it needs
to derive the length of the string on it's own; it doesn't /need/ strlen() to
determine the string length for it.

As a professional programmer, I try to keep my code simple and straight
forward, especially when I use the code as an example of /how/ to do
something, and *especially* when I intend the code to provide some indication
of the underlying techniques involved. Because I did not use strlen(), the OP
is now aware that a string is simply a sequence of characters, terminated by a
character of \0 value. The OP is now also aware of the technique of
iteratively reversing a string by working from both ends inward. Hopefully,
these two points will assist him in solving his problem of performing a string
reversal using a recursive method.

In any case, the function does not require additional supportive functions to
complete it's task; strlen() is just overkill.


--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------
 
O

ozbear

Good catch. I hadn't thought of that edge case when I put together the code.

So, substitute
for (end = string ; *end ; ++end);
if (*end) --end; else return;

Shouldn't that be:

So, substitute
for (end = string ; *end ; ++end);
if (*string) --end; else return;
^^^^^^
since

if (*end)

will never be true after the /for/ loop above it has terminated?

Oz
 
P

pete

ozbear said:
Shouldn't that be:

So, substitute
for (end = string ; *end ; ++end);
if (*string) --end; else return;
^^^^^^
since

if (*end)

will never be true after the /for/ loop above it has terminated?

Yes.
 
C

CBFalconer

ozbear said:
.... snip ...

Shouldn't that be:

So, substitute
for (end = string ; *end ; ++end);
if (*string) --end; else return;
^^^^^^
since

No, because that clause detects the original supply of string as
"", when end was never advanced, and exits early.
 
P

pete

CBFalconer said:
No, because that clause detects the original supply of string as
"", when end was never advanced, and exits early.

Did you miss seeing the semicolon
on the same line as the "for" keyword,
in the above posted code?

for (end = string; *end ; ++end) {
;
}
if (*string) {
--end;
} else {
return;
}
/* end points to last character in string */
 
P

pete

CBFalconer said:

You can't read code anymore.
I know that you haven't tested the code either.
I've tested the code.

This version of reverse, does nothing:

void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end);
if (*end) --end; else return;
/* end points to last character in string */

while (string < end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}
}


This version of reverse, reverses a string:

void reverse(char *string)
{
char *end;

for (end = string; *end ; ++end);
if (*string) --end; else return;
/* end points to last character in string */

while (string < end)
{
char temp;

temp = *string;
*string++ = *end;
*end-- = temp;
}
}

If you can't see that, then you can't read code anymore.

Nobody else is seeing that code the way that you do.
 
R

RoS

In data Fri, 14 Dec 2007 12:56:08 -0500, pete scrisse:


what is the difference of the below 2 routines?
 
R

RoS

In data Fri, 14 Dec 2007 20:53:42 +0100, RoS scrisse:
In data Fri, 14 Dec 2007 12:56:08 -0500, pete scrisse:


what is the difference of the below 2 routines?

yes i have seen it ...

void reverse(char *aa)
{char *a=aa, *b, t;
if(a==0||*a==0) return;
for( ; *a; ++a);
for(--a, b=aa; b<a; ++b, --a)
{t=*b; *b=*a; *a=t;}
}

this is my version whithout compile it nor debug it

but str* were not implementation reserved?

when this case "*end!=0" is verified here? (never)

 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top