Recursively reversing words in a string

Question

My friend got an assignment and I can't help him. Basically, using recursion he needs to print the words of a sentence in the reverse order. For example: Input - This is a sentence Output - sentence a is This

Here is an example I wrote him for a normal print, and I could do the whole sentence reversal with no problem, but I can't get neither an idea of a starting point for reversing only the words recursively without a linear approach and using the string library or linked lists or any other way:

#include <iostream>

using namespace std;

void revSentence(char sentence[], int i)
{
  if (sentence[i] == 0)
    return;
  cout<<sentence[i];
  i++;
  revSentence (sentence, i);
}

int main()
{
  char sentence[100];

  cin.getline (sentence, 100);
  int i = 0;

  revSentence(sentence, i);

  return 0;
}

Thing is it probably is something very simple because he is doing a fast course with only the basics, so they didn't use anything but the iostream library, so it must be something simple or at least not too complicated. So I'm asking for at least an idea of approach, or a solution. I've got a feeling I'm missing something very simple here but just can't see it.

Thanks in advance

BTW this isn't a duplicate. The duplicate question reverses all characters, while this one only wants one that reverses words. — yizzlez, Jun 07 '14 at 02:22
It is not the same question. To reverse the whole string wouldn't be a problem at all. — Sif, Jun 07 '14 at 10:45

101010 · Accepted Answer · 2014-06-07T01:06:49.617

It's not as easy as you might think.
You need to change the location where the printing command is called and place it below revSentence() recursive call, this is called post-order traversal, while the one you are doing is called pre-order traversal.
You also need a stack to push the reversed words.

#include <iostream>
#include <string>
#include <stack>

void revSentence(std::string const &str, std::stack<char> &stk, int i) { 
  if(i == str.size()) return;
  revSentence (str, stk, i + 1);
  if((!stk.empty() && stk.top() != ' '  && str[i] == ' ') || i == 0) {
    if(!i) std::cout << str[i];
    while(!stk.empty()) { 
        std::cout << stk.top();
        stk.pop();
    }
    if(i) std::cout << str[i];
  }
  stk.push(str[i]);
  if(!i) std::cout << std::endl;
}

int main() {
  std::string sentence;
  std::stack<char> stk;
  std::getline (std::cin, sentence);
  int i = 0;
  revSentence(sentence, stk, i);

  return 0;
}

Thank you very much, this one should do. Even if I'll need to make an code implementation of the stack through a linked list because that is the only stack they've done. But that should not be a problem. — Sif, Jun 07 '14 at 10:57

score 1 · Answer 2 · answered Jun 12 '14 at 19:48

I can not tell if you are allowed to use std::string and it's methods ... but if so...

In the following approach, I emphasize the finding of the first and last words in the input sentence, then using recursion on the leftover (here called sMiddle).

No additional stack of stl used.

The input string is duplicated in automatic variables, so it uses a bit more stack than some other choices (not a problem on Linux).

Assumes - no padding before 1st word, or after last word.

std::string revSentence(std::string s)
{
   std::string retVal;

   do
   {
      size_t posEndW1 = s.find(' ');
      if(posEndW1 == std::string::npos) break;

      // from line start to end of 1st word
      std::string wFirst = s.substr(0, (posEndW1)); 

      size_t posBeginW2 = s.rfind(' '); // from end of line
      if(posBeginW2 == std::string::npos) break;

      std::string wLast = s.substr(posBeginW2+1, std::string::npos); // to line end

      std::string sMiddle = s.substr(posEndW1+1, (posBeginW2-posEndW1-1));

      retVal = wLast + " " + revSentence(sMiddle) + " " + wFirst;
   }while(0);

   return(retVal);
}

Recursively reversing words in a string

2 Answers2

Linked