Advertisement

07.18.2005 at 07:34AM PDT, ID: 21495195
[x]
Attachment Details
[x]
The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

  • The Grade of the Solution
  • The Zone Rank of the Expert Providing the Solution
  • The Number of Author and Expert Comments
  • The Number of Experts Contributing
  • The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

Reverse words in sentence while keeping position of white space
Tags: reverse, words, sentence
Hi guys, something i couldn't figure out....

Write a function to reverse the order of words

Given a sentence of words in a character array, write a C function to reverse the order of words.

char* reverse_word (char* str);

The function gets a character array as its sole argument, reverses the order of words in it, and puts back the result into it. It returns the pointer to the argument on termination for convenience sake.

See the following example.
char str[] = "this     is very beautiful   ";
printf ("[%s]\n", reverse_word(str));   /* print [beautiful     very is this   ] */

Be ware that the position of space characters has not moved; the result of the example above is [beautiful     very is this   ], not [beautiful very is     this   ].

The following constraints apply:
No external function calls. (strlen, strcpy, etc).
No explicit memory allocation. (malloc, realloc, dynamic arrays, etc)

I managed only managed to reverse the order of words which results in [beautiful very is     this   ], however I didn't know how to maintain the position of space characters [beautiful     very is this   ].

this is the code that i wrote:

#include <stdio.h>
char* reverse_word(char* s)
{
    char *str = s;
    int len = string_len(s);
    int i=0;
    int count=0;
   
    reverse_substring(str,0,pos_lastChar(str));
    while(i<=len){
        if(str[i] ==' ' || i==len){
            reverse_substring(str,i-count,i-1);
            count=0;    
        }  
        if(str[i]!=' '){
            count++;
        }
        i++;
    }
    return str;
}

int pos_lastChar(char* s)
{
    int i;
    for(i=string_len(s); i>0;i--){
        if (s[i]!=' ' && s[i]!='\0'){
            return i;            
        }
    }
}

reverse_substring(char* s, int start, int end)
{
    char temp;
    int i,j;
    for(i=start, j=end; i<j; i++,j--)
    {
        temp = s[i];
        s[i]=s[j];
        s[j]=temp;
    }
}    
int string_len(char* str)
{
    int x=0;
    while(*str++){
        x++;
    }
    return (x);
}

int main(int argc, char **argv)
{
    char str[] = "this is   very beautiful   ";
    printf("Length of string: %d\n",string_len(str));
    printf("[%s]\n", reverse_word(str));
}
Start your free trial to view this solution
Question Stats
Zone: Programming
Question Asked By: maximteo
Solution Provided By: slyong
Participating Experts: 6
Solution Grade: A
Views: 358
Translate:
Loading Advertisement...
07.18.2005 at 08:19AM PDT, ID: 14466967

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.18.2005 at 08:39AM PDT, ID: 14467206

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.18.2005 at 08:50AM PDT, ID: 14467345

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.18.2005 at 08:00PM PDT, ID: 14472181

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.18.2005 at 08:54PM PDT, ID: 14472321

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 08:33AM PDT, ID: 14476077

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 08:54AM PDT, ID: 14476367

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 11:13AM PDT, ID: 14477928

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 01:55PM PDT, ID: 14479498

Rank: Sage

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 05:39PM PDT, ID: 14480760

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 06:21PM PDT, ID: 14480923

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.19.2005 at 07:55PM PDT, ID: 14481259

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.20.2005 at 01:00AM PDT, ID: 14482207

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.20.2005 at 03:16AM PDT, ID: 14482883

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.20.2005 at 03:18AM PDT, ID: 14482893

Rank: Master

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.20.2005 at 04:35AM PDT, ID: 14483283

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
07.28.2005 at 12:22PM PDT, ID: 14549114

Rank: Master

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
 
Loading Advertisement...
Microsoft
  • Internet Protocols
  • Applications
  • Development
  • OS
  • Hardware
  • Windows Security
Apple
  • Operating Systems
  • Hardware
  • Programming
  • Networking
  • Software
Internet
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Spy / Ad Blockers
  • Web Browsers
  • New Net Users
  • Web Development
  • Chat / IM
  • Anti Spam
  • Web Servers
  • Anti-Virus
  • Email Clients
Gamers
  • Tips
  • Online / MMORPG
  • Puzzle
  • Emulators
  • Action / Adventure
  • Role Playing
  • Consoles
  • Game Programming
  • Strategy
  • Sports
  • Misc
  • Computer Games
Digital Living
  • Hardware
  • New Net Users
  • New Users
  • Software
  • Digital Music
  • Gaming World
  • Home Security
  • Apple
  • Networking Hardware
Virus & Spyware
  • Vulnerabilities
  • IDS
  • Encryption
  • Anti-Virus
  • Operating Systems Security
  • Software Firewalls
  • WebApplications
  • Cell Phones
  • Operating Systems
  • Internet
  • Hardware Firewalls
Hardware
  • Handhelds / PDAs
  • Displays / Monitors
  • Components
  • Networking Hardware
  • Peripherals
  • Laptops/Notebooks
  • Storage
  • Servers
  • Desktops
  • New Users
  • Misc
  • Apple
Software
  • System Utilities
  • Industry Specific
  • Network Management
  • Photos / Graphics
  • Page Layout
  • VMWare
  • Misc
  • Web Development
  • OS
  • CYGWIN
  • Voice Recognition
  • Message Queue
  • Quality Assurance
  • Security
  • Firewalls
  • MultiMedia Applications
  • Development
  • Database
  • Office / Productivity
  • Business Management
  • OS/2 Apps
  • Server Software
  • Internet / Email
ITPro
  • OS
  • Storage
  • Encryption
  • Operating Systems Security
  • Apple Hardware
  • Laptops & Notebooks
  • Servers
  • Networking Hardware
  • Peripherals
  • Devices
  • Displays / Monitors
  • WebTrends / Stats
  • Search Engines
  • Firewalls
  • WebApplications
  • IDS
  • Vulnerabilities
  • Email Clients
  • File Sharing
  • Spy / Ad Blockers
  • Web Browsers
  • Web Servers
  • Networking
  • Anti-Virus
  • Chat / IM
  • Anti Spam
Developer
  • Web Servers
  • Web Browsers
  • Game Programming
  • Dev Tools
  • Industry Specific
  • Office / Productivity
  • Database
  • CYGWIN
  • Web Development
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Programming
  • Content Management
  • Application Servers
  • Protocols
Storage
  • Removable Backup Media
  • Storage Technology
  • Servers
  • Grid
  • Remote Access
  • Backup / Restore
  • Misc
  • Hard Drives
OS
  • Miscellaneous
  • Security
  • Development
  • Linux
  • VMWare
  • MainFrame OS
  • Unix
  • Apple
  • OS / 2
  • AS / 400
  • BeOS
  • Microsoft
  • VMS / OpenVMS
Database
  • Oracle
  • Miscellaneous
  • MySQL
  • Software
  • Sybase
  • Contact Management
  • PostgreSQL
  • Data Manipulation
  • Clarion
  • InterSystems Cache
  • Siebel
  • MUMPS
  • OLAP
  • SQLBase
  • SAS
  • GIS & GPS
  • 4GL
  • Berkeley DB
  • DB2
  • Informix
  • Interbase / Firebird
  • FoxPro
  • Reporting
  • LDAP
  • Filemaker Pro
  • MS SQL Server
  • dBase
  • MS Access
Security
  • Misc
  • Web Browsers
  • Software Firewalls
  • Operating Systems Security
  • File Sharing
  • Spy / Ad Blockers
  • Vulnerabilities
  • WebApplications
  • IDS
  • Anti-Virus
  • Encryption
  • Anti Spam
  • Email Clients
  • VPN
  • Chat / IM
Programming
  • Editors IDEs
  • Installation
  • Handhelds / PDAs
  • Multimedia Programming
  • System / Kernel
  • Algorithms
  • Game
  • Signal Processing
  • Project Management
  • Open Source
  • Database
  • Misc
  • Languages
  • Processor Platforms
  • Theory
Web Development
  • Scripting
  • Blogs
  • Web Servers
  • Software
  • Search Engines
  • Web Graphics
  • Images
  • Internet Marketing
  • Images and Photos
  • Components
  • Document Imaging
  • Web Languages/Standards
  • Illustration
  • WebApplications
  • Fonts
  • WebTrends / Stats
  • Authoring
  • Digital Camera Software
  • Miscellaneous
Networking
  • Protocols
  • Apple Networking
  • Network Management
  • Message Queue
  • Application Servers
  • Content Management
  • File Servers
  • Email Servers
  • Misc
  • Java Editors & IDEs
  • Wireless
  • Networking Hardware
  • Backup / Restore
  • System Utilities
  • ISPs & Hosting
  • Web Servers
  • Storage Technology
  • Removable Backup Media
  • Servers
  • Broadband
  • Grid
  • OS / 2
  • Novell Netware
  • Unix Networking
  • Windows Networking
  • Security
  • Telecommunications
  • Operating Systems
  • Linux Networking
Other
  • Community Advisor
  • Lounge
  • Community Support
  • New Net Users
  • Philosophy / Religion
  • Math / Science
  • Miscellaneous
  • URLs
  • Expert Lounge
  • Politics
  • Puzzles / Riddles
Community Support
  • Suggestions
  • New to EE
  • New Topics
  • Community Advisor
  • CleanUp
  • Announcements
  • General
  • Feedback
  • Input
  • EE Bugs
 
07.18.2005 at 08:19AM PDT, ID: 14466967

Rank: Guru

maximteo,

Nice to see this old homework chestnut. Thankyou for showing it to us again!

This seems to me like a rather complicated way to achieve the required result. You are taking every space-delimited string in the string and reversing it, i.e. steps look like:

0. "this     is very beautiful   "
1. "lufituaeb yrev si     siht   "
2. "beautiful yrev si     siht   "
...

I would have thought you should follow the plan:

1. Find the starts of all the words in the string.
2. Swap all the words in the string.

Paul
 
07.18.2005 at 08:39AM PDT, ID: 14467206
Hi paul,

Could u provide me with a code snipplet based on ur plan ?

maximteo
 
07.18.2005 at 08:50AM PDT, ID: 14467345

Rank: Guru

maximteo,

This would be very difficult at this stage. You must do the work and we will correct it. Start with trying to find the start of the next word in the string given a place to start:

int findStartOfNextWord ( char * s, int start )
{
  // Step to the end of this word.
  ...

  // Skip spaces
  ...
}

Paul
 
07.18.2005 at 08:00PM PDT, ID: 14472181
hi maximteo,

I just like to show you some strategies...  I think with your understanding of C you should be able to implement it quite easily...

[this   is very beautiful ] <-- find begin of left first word & right first word
[bhis   is very teautiful ] <-- swap the characters while not ' '
[beis   is very thautiful ]
[beas   is very thiutiful ]
[beau   is very thistiful ]
[beaut   is very thisiful ] <-- space detected on left word, start shifting right
[beauti   is very thisful ]
[beautif   is very thisul ]
[beautifu   is very thisl ]
[beautiful   is very this ] <-- find begin and end of next left word & right word
[beautiful   vs iery this ] <-- swap the characters while not ' '
[beautiful   ve isry this ]
[beautiful   ver isy this ] <-- space detected on left word start shifting right
[beautiful   very is this ] <-- end

Another example...
[beautiful   is very this ] <-- find begin of left first word & right first word
[teautiful   is very bhis ] <-- swap the characters while not ' '
...
[thistiful   is very beau ] <-- space detected on right word, start shifting left
[thisiful   is very beaut ]
...
[this   is very beautiful ] <-- find begin and end of next left word & right word
[this   vs iery beautiful ] <-- swap the characters while not ' '
[this   ve isry beautiful ] <-- space detected on left word, start shifting right
[this   ver isy beautiful ]
[this   very is beautiful ] <-- end

Cheers,
slyong
 
07.18.2005 at 08:54PM PDT, ID: 14472321
hey, pressed the submit by mistake. Writing again :)

Just a two step process:

This<space><space>is<space><space><space>good

1. Reverse the line
      - the usual, use to counters (use pointers :)), one start of line, one end of line.
      - start loop
             - swap
             - increment counter 1 and decrement counter 2 inside the loop.
             - increment or decrement only if the character is not a <space>.

Step 1 would result in

doog<space><space>si<space><space><space>sihT

2. Now reverse the individual words.

Step 2 would result in

good<space><space>is<space><space><space>This


Shweta
     
 
07.19.2005 at 08:33AM PDT, ID: 14476077
thanx guys i'm still trying to work it out based on the example slyong has explained...will update with a working code ..
anymore advice would be helpful too :)
 
07.19.2005 at 08:54AM PDT, ID: 14476367

Rank: Guru

I think the idea slyong suggests will produce an unnecessarily complicated result.

Break the problem down into parts! You will need to perform the following functions.

1. Find a complete word, starting at a specific position in a particular direction.
2. Swap two words.

Once you've achieved each of these, you're most of the way there.

Finding words is a sequence of loops which move a pointer back or forward (depending on the direction specified) until its passed a sequence of non-spaces then a sequence of spaces, stopping at the end or start of the string.

Swapping two words is just a matter of:

a. Copy the largest one out.
b. Copy the smallest into the gap left by the largest.
c. Shuffle the data so that the gap is now at the end of the smallest and is therefore big enough to take the largest.
d. Copy the largest in.

...short....muchlonger...

after a. and b.

...short....shortonger...

after c.

...short....s....short...

after d.

...muchlonger....short...

You will learn much more about programming by doing it the grown-up way of breaking the problem into smaller parts untill each is do-able than just achieving the output the customer(teacher) requested.

Paul
 
07.19.2005 at 11:13AM PDT, ID: 14477928
You can also do it by finding the length of the source string, using a for loop counting down and pushing characters into the destination string.
 
07.19.2005 at 01:55PM PDT, ID: 14479498

Rank: Sage


Yep.  There are lots of ways to do this.

I'd use a recursive algorithm.
Kent
 
07.19.2005 at 05:39PM PDT, ID: 14480760
I think the major problem that the thing get a bit complicated is the restriction on dynamic memory allocation which I supposed, it also means that one is not allow to cheat by allocating a char myString[INT_MAX] or do something like char myString[string_len(str)].

This leave ones the only choice of allocating char and swapping and shiftting those characters around the original array.  May be maximteo can englighten us on that part.  If things like myString[INT_MAX] is allowed then Paul's idea of finding the words and swapping them word by word would be much simpler then implementing something like my idea.

 
07.19.2005 at 06:21PM PDT, ID: 14480923
Hi Slyong,

this was an interview question which i failed to answer =(
unfortunately myString[string_len(str)]  is explictly allocating memory which is the restriction here too.

Slyong, I'm wondering when u mentioned "[beaut   is very thisiful ] <-- space detected on left word, start shifting right"
wat do u mean by start shifting right ?

My understanding from what u said is to shift the index position of the rest of the chars ?
e.g {before shift} [beau   is very thistiful ] current position of 'i' in 'is' = 7
      {after shift}   [beaut   is very thisiful ] position of 'i' in 'is' = 8

so every character after 'beaut' gets shifted/pushed to the right shifting one index ?

if my understanding is correct, could u give a code sniplet to demonstrate how u'd do this ? (i'm just wondering if this is similar to insertion sort)

       
 
07.19.2005 at 07:55PM PDT, ID: 14481259
Hi maximteo,

just hack up something.. may not work properly.. but you can have a look.  But sorry this is the maximum I would go for code sniplet.  If you could understand shift_right, you could hack up shift_left quite easily... also I have not really done a proper testing on this.. so bugs here and there..

#define SWAP 0
#define SH_L 1
#define SH_R 2

int swap_string(char *str, int *l_pos, int *r_pos) {
  char tmp;

  while (str[*l_pos] != ' ' && str[*r_pos] != ' ') {
    tmp = str[*l_pos];
    str[*l_pos] = str[*r_pos];
    str[*r_pos] = tmp;
    (*l_pos)++; (*r_pos)++;
  }

  if (str[*l_pos] == ' ')
    return SH_R;  /* return what to do next */
  else
    return SH_L;
}

int shift_right(char *str, int *l_pos, int *r_pos) {
  char tmp;
  int i;

  while (str[*r_pos] != ' ') {
    tmp = str[*r_pos];
    for (i = *r_pos; i > *l_pos; --i) {
      str[i] = str[i - 1];
    }
    str[*l_pos] = tmp;
    (*l_pos)++; (*r_pos)++;
  }
  return SWAP;
}

int main(int argc, char *argv[])
{
  char str[] = "this   is very beautiful ";
  int cur_l_pos = 0, cur_r_pos = 24; /* I cheat a bit here... */
  int next_op;

  next_op = swap_string(str, &cur_l_pos, &cur_r_pos); /* next_op should tell me what to do next */
  printf("SWAP %d:%d [%s]\n", cur_l_pos, cur_r_pos, str);

  shift_right(str, &cur_l_pos, &cur_r_pos);
  printf("SH_L %d:%d [%s]\n", cur_l_pos, cur_r_pos, str);

  return EXIT_SUCCESS;
}
Accepted Solution
 
07.20.2005 at 01:00AM PDT, ID: 14482207

Rank: Guru

slyong,

That was very nearly too much code to post for a homework/coursework question. The only reason I havent deleted it is because it demonstrates techniques and does not do the work so it is almost OK. Much of it COULD be used in an answer so I really SHOULD delete it.

No more code please.

Paul
 
07.20.2005 at 03:16AM PDT, ID: 14482883
Paul,

Sorry bout that.  My bad.  I won't mind if it is removed.

slyong
 
07.20.2005 at 03:18AM PDT, ID: 14482893

Rank: Master

Hi maximteo,
Basically, you need to split up the input string into two different things:
1. The words themselves
2. The spacings

To reassemble the string in inverse order is relatively simple. Assuming your original string is consisting of W/S sequences (word/space):

original:
W1 S1 W2 S2 ... Sn-1 Wn

Split up:
Spaces: S1 S2 ... Sn-1 (there's always one spacing less)
Words: W1 W2 ... Wn

Reassemble:
Wn S1 Wn-1 S2 ... Sn-1 W1

...finished.

Start with the spacings. Since a space is a space, an array of space sizes is sufficient. Hint: check the isspace() function.
Then divide up the string words. Hint: check the strtok() function.

That should be enough to get you going.

Cheers!

Stefan
 
07.20.2005 at 04:35AM PDT, ID: 14483283

Rank: Guru

Stefan,

All good points but one heads up:

>>(there's always one spacing less)
" there could be spaces at the start and the end so I think its the other way around " ;)
There could be one MORE space-run that words.

Paul
 
07.28.2005 at 12:22PM PDT, ID: 14549114

Rank: Master

Paul, you're right ;-)

Hmm, in this case you could simply use a lambda-word "".

Stefan
 
 
20080236-EE-VQP-29