Thread: homework help wanted: removing multiple spaces from array

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    37

    homework help wanted: removing multiple spaces from array

    I'm having some trouble with my problem in which I'm supposed to take a character array from the console and manipulate it to read correctly using cstrings and a class. Everything works as intended except for when I'm supposed to remove multiple spaces if they are entered and have only one space inbetween words.

    I take the user inputted sentence from the console and into an array through cin.get and then add '\0' to the end of it to make it a Cstring. The issue I am having is the syntax on how to test to see if there are multiple spaces entered.

    Here is what I have so far...

    Code:
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    class sentence
    {
      private:
        char userString[100];
    
      public:
        char getUserString();
        void setUserString(char userInput[], int& size);
        void readSentence(char userInput[], int& size);
        void correctSentence(int& size);
        void displayCorrectedSentence();
    };
    
    int main () 
    {
      sentence userSentence;
      char userInput[100];
      int size = 100;
    
      cout << "Please enter sentence less than 100 characters. " << endl;
      cout << "End the sentence with a period." << endl << endl;
      
      userSentence.readSentence(userInput, size);
    
      userSentence.correctSentence(size);
    
      userSentence.displayCorrectedSentence();
      
    }
    
    char sentence::getUserString()
    {
      return userString[100];
    }
    
    void sentence::setUserString(char userInput[], int& size)
    {
      userString[size] = userInput[size];
    }
    
    sentence::readSentence(char userInput[], int& size)
    {
      int i = 0;
    
      cin.get(userInput[i]);
      userString[i] = userInput[i];
      while (userInput[i] != '.')
      {
        i++;
        size = i - 1;
        cin.get(userInput[i]);
        userString[i] = userInput[i];
      }
      userString[i + 1] = '\0';
    }
    
    void sentence::correctSentence(int& size)
    {
      int i;
    	char tempString[100];
    
      for(i = 0; i < size; ++i)
      {
        if(userString[i] == '\n') //new lines become spaces
        userString[i] = ' ';
      }
    
      i = 1; //reset counter for new condition
      int i2 = 0;  //represents spaces
      tempString[0] = userString[0];
      for(i; i < size; ++i)
        {
    	if((userString[i] != ' ') && (userString[i-1] != ' '))
    	{
    	  tempString[i] = userString[i];
    	}
    	if((userString[i] == ' ') && (userString[i-1] == ' '))
    	{
    	  ++i2;
    	  tempString[i] = userString[i-i2];
    	}
        }	
    }	
    	tempString[i+1] = '\0';
    	cout << tempString;	
    
      userString[0] = toupper(userString[0]); //first char is uppercase
    	
      i = 1; //reset count to run through string again after first character
    	
      while(userString[i] != '\0')
      {
         userString[i] = tolower(userString[i]);
        ++i;
      }
    }
    
    
    void sentence::displayCorrectedSentence()
    {
      cout << "\nWith no multiple spaces and only the first letter " << endl;
      cout << "capitalized the sentence reads as follows..." << endl << endl;
      cout << userString << endl << endl;
    }
    The area I put in bold is the area I am having trouble with. I was attempting to check and see if the current array character was not a space and the previous one was not a space then to update tempString but if both were a space then to move everything in tempString back one character. But its not working : / The two final lines that are bolded I have in there just for debugging use. Thanks in advance for any advice.

  2. #2
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Your code in the loop
    Code:
     for(i; i < size; ++i)
        {
    	if((userString[i] != ' ') && (userString[i-1] != ' '))
    	{
    	  tempString[i] = userString[i];
    	}
    	if((userString[i] == ' ') && (userString[i-1] == ' '))
    	{
    	  ++i2;
    	  tempString[i] = userString[i-i2];
    	}
        }
    has a condition for two consecutive non-spaces, and two consecutive spaces, but no code for a space followed by a non-space and a non-space followed by a space. That is why nothing is being added to tempString in those cases. In such cases, you need to add both the character and the space.

    Actually, I don't have a lot of faith in the code. I would do it like this. Keep two separate index counters, iTmp, and iUser for the temp and user strings and keep a flag lastSpace set to true if the last character added to the temp string was a space. When lastSpace is true, further spaces are not to be added. As soon as a non-space is added, lastSpace becomes false. Whenever a character is added to the tempString, increment iTmp, and increment iUser for every character consumed from the userString. Actually, if you think about it, iTmp <= iUser at all times, so you actually don't need a tempString. You can do it all in userString memory, but I suggest you work with 2 strings to start. It may be less confusing to you.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    Good call on the missing conditions, saw that and felt like a dumb ass. We haven't went over flags yet and our book does a pretty vague job on the whole thing. I don't have a lot of faith in the code myself. I added the new conditions, still using seperate if statements, but still seem to be missing something, but I seem to making at least some headway. This is what I have in place of the bolded areas from before.

    Code:
    i = 1; //reset counter for new condition
    int i2 = 0;  //represents spaces
    tempString[0] = userString[0];
    	
    for(i; i <= size; ++i)
    {
      if((userString[i] != ' ') && (userString[i-1] != ' '))
      {
        tempString[i] = userString[i+i2];
      }
      if((userString[i] != ' ') && (userString[i-1] == ' '))
      {
        tempString[i] = userString[i+i2];
      }
      if((userString[i] == ' ') && (userString[i-1] != ' '))
      {
      tempString[i] = userString[i+i2];
      }
      if((userString[i] == ' ') && (userString[i-1] == ' '))
      {
      ++i2;
      tempString[i] = userString[i+i2];
      }
    }
      tempString[size] = '\0';
      cout << tempString;
    It starts to work but the more multiple spaces it runs into the more it starts to mess up and skip characters. It shortens the array the correct number of spaces, but it messes up somewhere within setting the characters in the corresponding place.

    For instance if I put in, "why doesn't this work right." with 1, 2, 3, and 4 spaces respectively I end up with "why doesn't this wrk ih." It is 6 characters shorter, as it should be but I'm missing several characters. Where is my logic error?

    *edit
    The website itself wont let me put in multiple spaces between my words even
    Last edited by DHart07; 10-26-2010 at 09:14 PM.

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    Another note, my logic is off when there is more than just 2 spaces as it doesn't know how many are going to be there so it can't just add whatever is next. If there is a group of 3 spaces then I end up losing the first character of the next word.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I don't like the way this was explained, maybe this is better.

    Basically you have two strings, one is the longer string that the user entered called string A, and the string with excess white space removed. Notice that you are either in a white space section or a character section when copying A to B. Find out what section you start out in, and control your logic, by testing each character to see if it is a white space character or not. While you are in the white space section, keep moving forward in A. While you are in the character section, you will copy stuff from A to B. If you need to switch from the character section to the white space section, put a space at the end of B. When you reach the end of A, end B.

    So, keep track of the current place in A and the current place in B with separate variables. In all likelihood they will be different.

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    That is what I was trying to do with my i2 variable as this notes how many spaces were skipped, at least that was my intention. I understand the shorter string is my tempString and my longer, and containing spaces, is userString. What you're suggesting is instead of REMOVING the spaces, to just ADD a space to tempString then fill in characters as needed?

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Yes. It's much easier to just add spaces when you need to and copy the stuff you want.

  8. #8
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    I think your logic of i2 needs to be abandoned. Notice that i2 is always incrementing when you have 2 consecutive spaces, and then tempString is being assigned userString[i+i2] as if you know that i+i2 now refers to a non-space character. Just because you are looking i2 spots past i does not mean that you've passed all spaces. The look ahead idea does not work. Also, i2 is never reset to 0, so after a run of spaces, you keep looking ahead based on runs you've seen much earlier in the string. Your i,i2 idea is almost like having two independent indexes into the two strings, but not quite.

    Sorry if I confused you with the idea of a flag. A flag is just a term for a variable that remembers a past condition. It's nothing special. In fact you don't need a flag. Just checking the last character of tempString will tell you if the last character added was a space.

    Step back and think about the algorithm. Think about all the different cases.

    case 1) If userString[i] is not a space, then you definitely want to add it to tempString.
    case 2) If userString[i] is a space, and the last character of tempString is not a space then you definitely want to add it to tempString.

    There is only one possibility left

    case 3) userString[i] is a space, but the last character of tempString is also a space. Then you do nothing. Just continue on with the next i of the loop.

    Since you do nothing in case 3, you don't even need to write an "if" condition for it.

    Keep a separate independent index into tempString and increment that whenever you add to tempString.

    Finally, your last line
    tempString[i] = '\0';
    is not right. You want tempString[tempIndex] = 0 because i is an index into userString and userString can be much longer then tempString because it has all the multiple spaces.

    The algorithm and coding is quite simple and actually shorter than what you posted. However, there is one small trap you can fall into if you follow the algorithm I recommend. Post your implementation and I'll tell you if you got it right.
    Last edited by Zlatko; 10-27-2010 at 03:21 AM.

  9. #9
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    Thanks again for the help guys. This is what I currently have, and it works, but I still want to clean it up a bit.
    Code:
    i = 1; //reset counter for new condition
    int j = 1;
    tempString[0] = userString[0];
    	
    for(i; i <= size;)
    	{
    		if((userString[i] != ' ') && (userString[i - 1] == ' '))
    		{
    			tempString[j] = ' ';
    			++j;
    			tempString[j] = userString[i];
    			++j;
    			++i;
    		}
    		
    		if(userString[i] == ' ')
    		{	//do nothing and skip to the next character
    		}
    
    		if(userString[i] != ' ')
    		{
    			tempString[j] = userString[i];
    			++j;
    		}
    		++i;
         }
    tempString[j] = '.';
    tempString[j+1] = '\0';
    I don't like how I am forcing the period and null terminator into my tempString either but it seemed that I couldn't get those to get placed in through my normal routine. Also, I would ultimately like to have only the userString exist and eliminate tempString all together since I would prefer to have userString be correct. What all would I have to change in order to do this without just having another for loop replacing the old userString with tempString?

  10. #10
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    You almost have it but it has trouble with leading spaces. Try stepping through with a debugger if you know how to do that. Otherwise, use pencil and paper to step through the code.

    Check your work against the following strings to make sure it does what you want.
    Code:
    "hello hello  hello   hello"
    " hello hello  hello   hello"
    "  hello hello  hello   hello"
    "   hello hello  hello   hello"
    "hello hello  hello   hello "
    "hello hello  hello   hello  "
    "hello hello  hello   hello   "
    " "
    "  "
    "   "
    " h h h "
    "  h  h  h  "
    Don't forget to test the empty string: ("")

    You did not fall into the trap of using a -1 for an index because you start your loop at 1.

    Removing extra spaces without using tempString (in-place removal) is possible only if the userString is in writable memory. If you pass a quoted string to the space removal function and the function tries to overwrite characters in the string, you may get a program crash because the compiler may put quoted strings into read-only memory. That would confuse you during testing, but during normal running of a program, your userString would be in writable memory because it came as input from a user.

    In other words, if you are testing in-place removal, test it like this:
    test(strdup("hello hello"));
    not like this
    test("hello hello");

    Of course you don't need to worry about the memory leak from strdup. It's only a test.
    Last edited by Zlatko; 10-27-2010 at 07:56 AM.

  11. #11
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    If I were you, I would take a nice hard look at strtok() and what it could do to help you
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  12. #12
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    Code:
    i = 0; //reset counter for new condition
    int j = 0; //counter for corrected tempString
    	
    	
    for(i; i < size + 2;)
    {
      if((userString[i] != ' ') && (userString[i - 1] == ' '))
    {
      if(j == 0)
        tempString[0] = userString[i];
      else
      {
         tempString[j] = ' '; //inserts a space when one is needed
         ++j; 
         tempString[j] = userString[i];
        ++j;
        ++i;
      }
    }
    		
      if(userString[i] == ' ')
      {	//do nothing and skip to the next character
      }
    
      if(userString[i] != ' ')
      {
        tempString[j] = userString[i];
        ++j;
      }
    		
      ++i;
    }
    
      size = j;
    
      for(i = 0; i < size; ++i)
      {
         userString[i] = tempString[i];
      }
    Everything seems to be working a-okay with all conditions, leading spaces included. Thanks again man, I really appreciate the help. And thanks for helping me think my way through it, not just fixing my mistakes.
    Last edited by DHart07; 10-27-2010 at 10:31 AM.

  13. #13
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Yes it does seem to do the job but it replaces multiple spaces at the end with one space, and removes all spaces at the beginning. Its a little asymmetrical. Is that what you wanted?

    I see you started your i counter at 0, instead of 1. That's good. I thought starting at 1 was a bit awkward. There is a problem though, with starting at 0 when you check userString[i-1] you are going into invalid memory.

    You can patch it with a check if i > 0
    if((i > 0) && (userString[i] != ' ') && (userString[i - 1] == ' '))
    This still seems to work.


    It is possible to do the space removal in place. Just consider that you're moving characters from a source to a destination in the same string. The destination will always be at the same location as the source or behind the source so writing to the destination will never interfere with the source. If a string does not have any multiple spaces, then what will happen is that source is equal to destination and a character just overwrites itself, so there is no damage. Imagine the source and destination indexes as pointers and try to visualize the destination pointer lagging the source pointer as multiple spaces are dropped.


    I appreciate your desire to do the code on your own, but it can be instructive to see how others would do it. I don't know if you want this advice, but this is how I would do it.


    Code:
    void compressSpaces(char* userString)
    {
        cout << "---------------------------------------------------\n";
        cout << "<" << userString << ">\n";
    
        int srcIx = 0; // the source index
        int destIx = 0; // the destination index
        while(userString[srcIx]) // while we are not at the end of the input string
        {
            if (userString[srcIx] != ' ') // if not a space, just copy from source to destination
            {
                userString[destIx] = userString[srcIx];
                ++destIx; // increment dest whenever a character is added to the destination end
            }
            else
            {
                /*
                in this else branch the character at the source is a space
                if this is the first character (destIx == 0) or if the last
                character at the dest is not a space then add the character to the dest.
    
                So if the last character at dest is a space, nothing is done
    
                Remember that when destIx is 0, the 
                userString[destIx-1] != ' ' is not even evaluated.
                because the left side of the logical-or makes the whole 
                expression true.
                */
                if (destIx == 0 || userString[destIx-1] != ' ')
                {
                    userString[destIx] = userString[srcIx];
                    ++destIx;
                }
            }
    
            ++srcIx; // always increment the source
        }
        userString[destIx] = 0; // nothing wrong with forcing a null terminator
    
        cout << "<" << userString << ">\n";
    }
    
    int main(void)
    {
        compressSpaces(strdup("hello hello  hello   hello"));
        compressSpaces(strdup(" hello hello  hello   hello"));
        compressSpaces(strdup("  hello hello  hello   hello"));
        compressSpaces(strdup("   hello hello  hello   hello"));
        compressSpaces(strdup("hello hello  hello   hello "));
        compressSpaces(strdup("hello hello  hello   hello  "));
        compressSpaces(strdup("hello hello  hello   hello   "));
        compressSpaces(strdup(" "));
        compressSpaces(strdup("  "));
        compressSpaces(strdup("   "));
        compressSpaces(strdup(" h h h "));
        compressSpaces(strdup("  h  h  h  "));
        compressSpaces(strdup(""));
    }
    Last edited by Zlatko; 10-27-2010 at 05:10 PM.

  14. #14
    Registered User
    Join Date
    Apr 2010
    Posts
    37
    No, I always like to look at other people's code to see how their logic deciphered it. I added the i > 0 check before I read your post so my above code is more or less my final code with the added check. It runs as planned with no funky outputs or conditions.

    Thanks for helping, and extra thanks for showing me how you would have went at it, and especially for the comments added in. Its greatly appreciated.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 08-16-2010, 10:00 AM
  2. Removing elements from an array
    By monki000 in forum C++ Programming
    Replies: 3
    Last Post: 03-30-2010, 12:23 PM
  3. Code review
    By bennywhere in forum C Programming
    Replies: 16
    Last Post: 10-20-2009, 09:00 PM
  4. Sort array with multiple keys
    By Fab in forum C Programming
    Replies: 3
    Last Post: 10-26-2005, 12:57 AM
  5. Writing multiple values to an array
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 03-06-2002, 03:27 PM