5
\$\begingroup\$

I was tasked with using C++ to turn this

"Hello Jarryd, do you like socks?"

into:

"socks? like you do Jarryd, Hello";

Edit: The condition was to reverse this in place.

Here's what I came up with, knocked up in Visual Studio using the TestExplorer to run it. Criticism is much appreciated!

.h

namespace SentenceFlipNamespace
{
    class SentenceFlip
    {
    public:
        SentenceFlip();
        ~SentenceFlip();

        int FlipSentenceInPlace(char* in_Sentence);
        void SentenceFlip::Move(int in_StartIndex, char in_String[]);

    };
}

.cpp

namespace SentenceFlipNamespace
{
    SentenceFlip::SentenceFlip()
    {
    }


    SentenceFlip::~SentenceFlip()
    {
    }

    int SentenceFlip::FlipSentenceInPlace(char in_Sentence[])
    {
        int index = 0;
        int length = strlen(in_Sentence);

        while (index < length)
        {
            int dist = 0;
            int wordSize = 0;

            //Get the characters to the first word
            for (int i = length - 1; i > 0; i--)
            {
                if (in_Sentence[i] == ' ' && i != length - 1)
                {
                    dist = i - index;
                    wordSize = length - i - 1; //exclude the space
                    break;
                }
            }

            //Push everything forwards
            for (int i = 0; i <= dist; i++)
                Move(index, in_Sentence);

            //This leaves a space at the end, push it forward
            if (index + wordSize >= length)
                return 0;

            for (size_t i = 0; i < length - wordSize - index - 1; i++)
                Move(index + wordSize, in_Sentence);

            index += wordSize + 1; //include the space          
        }

        return -1;
    }

    void SentenceFlip::Move(int in_StartIndex, char in_String[])
    {
        char temp = in_String[in_StartIndex];
        int length = strlen(in_String);
        for (int j = length - 1; j >= in_StartIndex; j--)
        {
            char temp2 = in_String[j];
            in_String[j] = temp;
            temp = temp2;
        }       
    }
}

Test Method, since I don't invoke it in main.

namespace CodeChallengesTests
{
    TEST_CLASS(TextFlip)
    {
    public:
        TEST_METHOD(SentenceFlipInPlace)
        {
            SentenceFlipNamespace::SentenceFlip *testFlip = new SentenceFlipNamespace::SentenceFlip();
            char input[] = "Hello Jarryd, do you like socks?";
            char expectedResult[] = "socks? like you do Jarryd, Hello";
            testFlip->FlipSentenceInPlace(input);

            Assert::AreEqual(expectedResult, input, "Results do not match");
        }
    };

}
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to code review. We can do a better job of reviewing your code if you provide the entire SentenceFlip class and the main program. \$\endgroup\$ – pacmaninbw Jul 12 at 14:24
  • 1
    \$\begingroup\$ I've added the .h, .cpp and my test method. Thank you, and I'll add these to future questions. \$\endgroup\$ – Jarryd Jul 15 at 4:20
6
\$\begingroup\$

Your algorithm is supremely inefficient. Moving a word to the front moves all the other characters to the back, resulting in a quadratic algorithm. In addition to that, you repeatedly recalculate the length of the null terminated string.

As an aside, the standard library provides std::rotate() for moving part of a sequence from the end to the beginning, no need to write your own.

There is an alternative in-place algorithm which swaps every character at most twice, and traverses three times. Thus it is trivially proven linear:

  1. Reverse every word in isolation. Remember the end if needed.
  2. Reverse everything.

The standard library features std::reverse() for implementing this.

\$\endgroup\$
  • \$\begingroup\$ Oh damn, I am completely out of touch with the standard library, which I need to remedy. And what a great idea, to reverse the words like that. Thanks for taking the time to provide such a great answer, I've learned a lot! \$\endgroup\$ – Jarryd Jul 15 at 4:08
6
\$\begingroup\$

I would probably do this by reading the words into a vector of strings, then rather than reversing the order, just traverse the vector in reverse order:

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

int main() { 
    std::vector<std::string> words { std::istream_iterator<std::string>(std::cin), {} };

    std::copy(words.rbegin(), words.rend(), 
              std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << '\n';
}

So a couple obvious points:

  1. Avoiding work is good.
  2. Letting your code avoid work is good too.
  3. The standard library has lots of stuff that can make programming a lot easier.
\$\endgroup\$
  • \$\begingroup\$ Love that. Now if only if we had reverse ranges so we could use the range based for. \$\endgroup\$ – Martin York Jul 12 at 23:56
  • \$\begingroup\$ @MartinYork: Soon (C++20). Probably available already, if you use a reasonably new compiler. \$\endgroup\$ – Jerry Coffin Jul 13 at 0:51
1
\$\begingroup\$

This quite simple task.
Just find words in reverse order and put them in new string.

Code should be quite simple:

std::string reverse_words(std::string_view s)
{
    std::string result;
    result.reserve(s.size());
    while(!s.empty()) {
       auto i = s.rfind(' ');
       result.append(s.begin() + i + 1, s.end());
       if (i == std::string_view::npos) break;
       result += ' ';
       s = s.substr(0, i);
    }
    return result;
}

This code is fast since it does minimum allocations and minimum amount of coping.

https://wandbox.org/permlink/bYmojDyt0Z0xMJv0

\$\endgroup\$
  • \$\begingroup\$ Welcome to code review. We do things a little differently than stack overflow, good answers actually comment on the users code rather than provide alternate solutions. \$\endgroup\$ – pacmaninbw Jul 13 at 3:39
1
\$\begingroup\$

If it is important to execute the reversing in place, here is an example code (which implements the algorithm mentioned in https://codereview.stackexchange.com/a/224037):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


static void reverse_chars(char *s, int n)
{
  int n2 = n / 2;
  for (int i = 0; i < n2; i++)
  {
    char tmp = s[i];
    s[i] = s[n - i - 1];
    s[n - i - 1] = tmp;
  }
}

static char *get_next_word(char *s, int *wlen)
{
  while (*s && isspace(*s))
    s++;
  if (*s == '\0')
    return nullptr;
  char *p = s;  
  while (*p && !isspace(*p)) 
    p++;
  *wlen = (p - s);
  return s;
}

static void reverse_words(char *s, int n)
{
  reverse_chars(s, n);
  int wlen;
  char *w;
  while ((w = get_next_word(s, &wlen)) != nullptr)
  {
    reverse_chars(w, wlen);
    s += wlen;
  }
}

int main(int argc, char **argv)
{
  if (argc < 2)
  {
    fprintf(stderr, "Please, specify the string.\n");
    return 1;
  }
  printf("Original string: [%s]\n", argv[1]);
  reverse_words(argv[1], strlen(argv[1]));
  printf("Words reversed:  [%s]\n", argv[1]);
  return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.