Thread: Help with hw problem: counting characters in a string

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    15

    Help with hw problem: counting characters in a string

    ok, I've got a homework assignment I need help with. We have to write a program to take a user-inputted (is inputted a word) string, display it in reverse order, and then count the occurrences of the characters in the string, and display the results (just for characters that actually occur in the string, i.e. we don't have to output x=0, y=0, z=o for any that don't occur). It has to be able to handle all normal Latin capital & lower-case letters, numbers and common punctuations and symbols (i.e. those physically on a normal desktop keyboard). Obviously we have to then output the I know to use string manipulators to display it in reverse order, but is there an easier way to do this character counting thing than the obvious (but long and tedious) way of declaring count variables for every character, initially defining them each as equal to 0, and then doing
    Code:
    char_count++
    for each occurrence of the character? Something with loops or something?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Use a std::map<char,int> container to count the occurrences, real easy. Nuff' said.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    15
    oh thanks dude, I hadn't seen that

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    15
    hokay, so...

    we haven't learned about arrays or maps yet, so he said we can't use them. However, he did tell me this...For the counting of each character he said to use a FOR loop that takes the character in index 0, declares a count variable of 1 for it, and compare it to the rest of the characters in the string, and if it finds matches, increment its count variable, and then have the loop restart for the next space in the index and continue as long as there are more values. I'm stil not sure exactly how to do this though, I think it's some kind of string class processing method? or a character library function?

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Your teacher is an idiot. This algorithm doesn't work unless you make it destructive, in which case it's incredibly inefficient.

    But since I hate idiot assignment, I'll give you the code of the faulty version of the algorithm.
    Code:
    std::string data = whatever;
    
    for(std::string::iterator wit = data.begin(); wit != data.end(); ++wit) {
      char c = *wit;
      int count = 0;
      for(std::string::iterator cit = wit; cit != data.end(); ++cit) {
        if(c == *cit) ++count;
      }
      std::cout << "'" << c << "' appears " << count << " times.\n";
    }
    The problem is simple: for the string "voodoo" it will print:
    Code:
    'v' appears 1 times.
    'o' appears 4 times.
    'o' appears 3 times.
    'd' appears 1 times.
    'o' appears 2 times.
    'o' appears 1 times.
    The way to solve this is, as I said, to make the algorithm destructive, i.e. remove the characters you find from the string. But that leaves you exposed to iterator invalidation problems. Things get rather tricky there.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    15
    Quote Originally Posted by CornedBee View Post
    Your teacher is an idiot. This algorithm doesn't work unless you make it destructive, in which case it's incredibly inefficient.

    But since I hate idiot assignment, I'll give you the code of the faulty version of the algorithm.
    Code:
    std::string data = whatever;
    
    for(std::string::iterator wit = data.begin(); wit != data.end(); ++wit) {
      char c = *wit;
      int count = 0;
      for(std::string::iterator cit = wit; cit != data.end(); ++cit) {
        if(c == *cit) ++count;
      }
      std::cout << "'" << c << "' appears " << count << " times.\n";
    }
    The problem is simple: for the string "voodoo" it will print:
    Code:
    'v' appears 1 times.
    'o' appears 4 times.
    'o' appears 3 times.
    'd' appears 1 times.
    'o' appears 2 times.
    'o' appears 1 times.
    The way to solve this is, as I said, to make the algorithm destructive, i.e. remove the characters you find from the string. But that leaves you exposed to iterator invalidation problems. Things get rather tricky there.
    huh? umm my teacher definitely is not an idiot-he used to work for Autodesk and the Dept of Defense and he's the sh!t
    Last edited by pinkfloyd4ever; 11-04-2007 at 12:28 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    huh? umm my teacher definitely is not an idiot-he used to work for Autodesk and the Dept of Defense and he's the sh!t
    In mathematics, you can argue and win against a Fields medalist if you can provide a proof or counterexample that shows he/she is incorrect. Programming, at least the computer science aspect of it, is like (or rather, is) mathematics.

    Efficiency issues aside, do you understand why not making the algorithm destructive will provide incorrect output? CornedBee provided a pretty clear example.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    Quote Originally Posted by CornedBee View Post
    The way to solve this is, as I said, to make the algorithm destructive, i.e. remove the characters you find from the string. But that leaves you exposed to iterator invalidation problems. Things get rather tricky there.
    Or, he could use a kind of bitmask (that could be a copy of given string, since he said he cannot use arrays), and while iterating for matches in original string, set 0,1 (or some other value you won't get from keyboard that easy) on matched indexes.
    Just to fix his teacher's algorithm and to keep original string fine.

    eg:
    Code:
    // loop looking for matches
    for (int j = i+1; j < original.length; j++)
        if ( original[i] == original[j] && maskString[j] != /* some fixed marker value */)
           counter++;
    Last edited by jimzy; 11-04-2007 at 03:40 AM.

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Isn't that just like using arrays again? If he can misuse a string as an array, he can do it the proper way, to count characters.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    15
    errr, anyhooters, I got the reversal part working, and I've commented out what I think is how to start the character counting part..
    Code:
     
    #include<iostream>
    #include<iomanip>
    #include<cctype>
    #include<string>
    using namespace std;
    
    
    int main()
    {
    	string str;
    	int count1, count2=0;
    	
    	cout << "Type a character string" << endl;
    	cin >> str;
    
    	count1=int(str.size()-1);
    	
    	
    	while (count1 >= 0)
    	{
    	cout << str.at(count1);
    	count1--;
    	}
    	cout << endl;
    
    /*	for (_____)
    {
    	int str.at(count2)++;
    }*/
    		return 0;
    }
    is this close to being on the right track? I'm not sure what to put inside of for(____) or how to create a new count variable for each new character found in the string

    Again, this is basically how he said to do this: For the counting of each character he said to use a FOR loop that takes the character in index 0, declares a count variable of 1 for it, and compare it to the rest of the characters in the string, and if it finds matches, increment its count variable, and then have the loop restart for the next space in the index and continue as long as there are more values.

    forgive me if I'm just asking something that's already been answered, I don't understand some of the code corned_bee wrote. What's with all the pairs of colons? And what about the asterisks?

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It's pointers.
    For what your teacher seems to ask you to do, it to use two loops.
    I'll show you how a for loop is made:
    Code:
    for (initializtion_area; condition_area; maintence_area)
    {
    	// Code here...
    }
    declaration_area or initializtion_area is where you perform things that is to be done prior to the loop. Commonly used to create and initialize a counter variable.
    The second part, condition_area, must be a bool expression. Each time the loop begins, this condition will be tested and the loop will continue as long as that expression is true.
    The last area is maintence where the code will be executed after each loop. Usually used to increase your counter variable. Here's an example of a typical for loop:
    Code:
    for (int i = 0; i < 100; i++);
    This loop loops 100 times before quitting.

    What your teacher asks is very inconvienient and silly also, in terms of counting. It makes it more complex and trivial that needs be.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 03-03-2006, 02:11 AM
  2. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 12:56 PM
  3. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 11:06 PM
  4. Counting all characters in a string
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 06-15-2002, 09:24 PM