Author |
Topic: CS: String reversal (Read 2048 times) |
|
ootte
Newbie
Posts: 19
|
 |
CS: String reversal
« on: Jul 24th, 2002, 3:30am » |
 Quote  Modify
|
#!/usr/bin/perl
$string = <STDIN>;
chomp($string);
@parts = split(/ /, $string);
foreach $_ (@parts) { push(@list, $_); $i++}
for ($_ = 0; $_ < $i; $_++) { print pop(@list) . " "; }
Working Perl implementation. Obviously not the best.
--
Oliver
|
|
 IP Logged |
|
|
|
ChOas
Guest
|
Or maybe:
#!/usr/bin/perl -w
use strict;
$_=<STDIN>;
print join ' ',reverse split;
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: CS: String reversal
« Reply #2 on: Jul 27th, 2002, 6:07pm » |
Quote Modify
|
OK, now do it without perl!
The direct assault on this problem in C turns out to be hard. Try writing to code to properly swap around space-delimited words in a character array, accounting for different sizes, etc.
The slick answer I know is to reverse the entire string, then reverse each word individually. This uses no (well, some constant) additional storage and is about as fast as is possible. I'm not sure the messier version is any better in time or space.
|
|
IP Logged |
|
|
|
-D-
Guest
|
Here's another answer...
If you have a temporary buffer of the same length as the input string...
traverse the string backwards until a space. then strcat (concatenate) from the current index +1 into the new string and append a space. mark a '\0' (NULL) at the current location and continue backwards. If your index becomes negative, exit the loop and concatente from index 0.
I think it's slower and takes more space than your method though... but I like it. :)
-D-
|
|
IP Logged |
|
|
|
ChOas
Newbie
Gender:
Posts: 1
|
|
Re: CS: String reversal
« Reply #4 on: Jul 30th, 2002, 3:19am » |
Quote Modify
|
on Jul 27th, 2002, 6:07pm, srowen wrote:OK, now do it without perl!
The direct assault on this problem in C turns out to be hard. Try writing to code to properly swap around space-delimited words in a character array, accounting for different sizes, etc.
The slick answer I know is to reverse the entire string, then reverse each word individually. This uses no (well, some constant) additional storage and is about as fast as is possible. I'm not sure the messier version is any better in time or space. |
|
Here you go, it isn`t that hard...
(Only using pointers, reverse could have been done
inline, and I could skip the *Tmp, but I wont  ) :
I`ll leave coding this in assembler to the reader, as
it is trivial...
(By the way, I had been thinking about doing it the way -D-
suggested it first (which might be a bit quicker (because
you move blocks instead of chars, and the way I do it now
each char is examined twice, instead of once, but I love
pointer hopping, so here you go  )
#include <stdio.h>
void Reverse(char *, char *);
int main(argc,argv)
int argc;
char *argv[];
{
char *P1,*P2;
char String[]="My name is ChOas";
printf("Before: String: '%s'\n",String);
P1=P2=String;
while(*P2) ++P2;
--P2;
Reverse(P1,P2);
P2=P1;
while(*P2)
{
while(*P2&&(*P2!=' ')) ++P2;
P2--;
Reverse(P1,P2);
P2+=2;
P1=P2;
};
printf("After: String: '%s'\n",String);
exit(0);
};
void Reverse(P1,P2)
char *P1;
char *P2;
{
char Tmp;
while(P1<P2)
{
Tmp=*P2; *P2=*P1; *P1=Tmp;
++P1; --P2;
};
};
|
| « Last Edit: Jul 30th, 2002, 3:25am by ChOas » |
IP Logged |
|
|
|
-D-
Guest
|
Reversing the entire string then reversing each character takes essentially 2 passes through the string. Walking backwards through a string + stoping and copying all bytes from that point forward also takes 2 passes through the string. However, if the results are to be placed back in the original string, my method would result in a third pass through the string to copy it back. So technically reversing the string than each word is faster. If the results are to be placed in a seperate string then either method is just as good. Actually my method might have a slight ASM advantage due to X86 processors having some built in string fuctions that help out here (REP, MOVSB).
-D-
|
|
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: CS: String reversal
« Reply #6 on: Jul 12th, 2004, 11:18am » |
Quote Modify
|
What if the string has punctuation? Say, "Lock, stock and barrel." when reversed should become, "barrel, and stock Lock." so that the punctuation marks don't leave their relative positions in the string, only the words get reversed. Using additional linear storage helps a lot but can it be done in linear time using constant extra space?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove