Run Length Encoding

Question

Given an input string, write a function that returns the Run Length Encoded string for the input string.

For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6″.

The following is my implementation:

string length_encoding(const string& s)
{
    char c = ' ';
    int num = 0;
    string result;
    string::const_iterator it = s.begin();
    for(; it != s.end(); ++it)
    {
        if(*it!=c)
        {
            if(num!=0)
            {
                stringstream ss;
                ss << num;
                string num_s(ss.str());
                result += num_s;
            }

            c = *it;
            result.push_back(c);

            num = 1;
        }
        else
        {
            num++;
        }       
    }

    stringstream ss;
    ss << num;
    string num_s(ss.str()); 
    result += num_s;

    return result;
}

Answer 1

There is a bug. If your input string begins with a space then you don't prefix the number with a space.

Input:           "    AAAA"
Output:          "4A4"
Expected Output: " 4A4"

This is easily fixed by outputting the character and count at the same time.

Problems: Magic values

char c = ' ';

Magic values cause all sorts of problems you should really use a value that can never be a character. In this case convert to an int and make it -1

int c = -1; // This is guaranteed to be a value that will never be a character.

Use the ability to declare variables inside the for(;;) statement unless you really need the iterator after the loop.

string::const_iterator it = s.begin();
for(; it != s.end(); ++it)

// easier to write and read as:

for(string::const_iterator it = s.begin(); it != s.end(); ++it) 
{
    // Also because `it` is scopped is does not pollute the
    // code with a variable that is not used after the loop.
}

This piece of code:

            stringstream ss;
            ss << num;
            string num_s(ss.str());
            result += num_s;

Is repeated in two places. Refactor it into its own function.
You will also find that such a function already exists in boost std::lexical_cast

Answer 2

I'm not a C++ guru, but for what they are worth, I have some comments:

• it would be better to evaluate s.end() just once (outside the loop). Correction: this won't help.
• the function fails if s starts with a space

• you have duplicate code turning an int into a string. Perhaps use C++11 to_string or write your own a function, such as:

  template <typename T>
  static std::string to_string(T num)
  {
      std::stringstream ss;
      ss << num;
      return ss.str();
  }