0

我的朋友有一个任务，我无法帮助他。基本上，使用递归，他需要以相反的顺序打印句子中的单词。例如： 输入 - 这是一个句子 输出 - 句子 a 是这个

这是我为正常打印而写的一个示例，我可以毫无问题地进行整个句子反转，但是我不知道在没有线性方法的情况下仅递归地反转单词的起点并使用字符串库或链表或任何其他方式：

#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 库之外没有使用任何东西，所以它必须是简单的，或者至少不是太复杂。因此，我要求至少提供一种方法或解决方案的想法。我有一种感觉，我在这里错过了一些非常简单的东西，但就是看不到它。

提前致谢

4

2 回答 2

3

  • 这并不像你想象的那么容易。

  • 您需要更改调用打印命令的位置并将其放在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;
}
于 2014-06-07T00:25:22.603 回答
1

我不知道你是否被允许使用 std::string 和它的方法......但如果是这样......

在下面的方法中，我强调在输入句子中找到第一个和最后一个词，然后对剩余的词使用递归（这里称为 sMiddle）。

没有使用额外的 stl 堆栈。

输入字符串在自动变量中重复，因此它使用的堆栈比其他一些选择多一点（在 Linux 上不是问题）。

假设 - 在第一个单词之前或最后一个单词之后没有填充。 

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);
}
于 2014-06-12T19:48:25.697 回答