Рекурсивно изменяющие слова в строке

Question

Рекурсивно изменяющие слова в строке

Мой друг получил задание, и я не могу ему помочь. В основном, используя рекурсию, он должен печатать слова предложения в обратном порядке. Например:
Вход — это предложение
Вывод — предложение а это

Вот пример, который я написал ему для обычного шрифта, и я мог бы без проблем выполнить все предложение полностью, но я не могу ни получить представление о начальной точке рекурсивного изменения только слов без линейного подхода и использования Библиотека строк или связанные списки или любой другой способ:

#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;
}

Дело в том, что это, вероятно, что-то очень простое, потому что он делает быстрый курс только с основами, поэтому они не использовали ничего, кроме библиотеки iostream, поэтому это должно быть что-то простое или, по крайней мере, не слишком сложное. Поэтому я прошу хотя бы идею подхода или решения. У меня такое чувство, что я скучаю по чему-то очень простому здесь, но просто не вижу этого.

заранее спасибо

0

c++recursion reverse sentence words

Решение

Другие решения

Я не могу сказать, разрешено ли вам использовать std :: string и его методы … но если это так …

В следующем подходе я подчеркиваю нахождение первого и последнего слов во входном предложении, затем используем рекурсию на остатке (здесь он называется sMiddle).

Дополнительный стек stl не используется.

Входная строка дублируется в автоматических переменных, поэтому она использует немного больше стека, чем некоторые другие варианты (не проблема в Linux).

Предполагается — нет дополнения до 1-го слова или после последнего слова.

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);
}

1

Источник

Accepted Answer

Это не так просто, как вы думаете.
Вам нужно изменить место, где вызывается команда печати, и разместить ее ниже. revSentence() рекурсивный вызов, это называется post-order traversalв то время как тот, который вы делаете, называется pre-order traversal,
Вам также нужен стек, чтобы выдвинуть обратные слова.

#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;
}

3