内容同步于我的博客：https://blog.bigrats.net/archives/basic-alg-sentence-inverse.html
题目描述
将一个英文语句以单词为单位逆序排放。例如："I am a boy"逆序输出为"boy a am I"。所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符。
输入描述
输入一个不包含符号的英文语句
输出描述
输出单词逆置后的句子
示例
Input:
I am a boy
Output:
boy a am I
问题分析
对于这类倒置的问题，最容易想到的就是利用栈的先进后出的特性。只需将每个单词入栈，然后再依此出栈输出即可。
算法描述
- 将每个单词入栈，其具体方法为将单词后的空格替换为字符串结束符"\0"，同时返回单词第一个字符的指针，然后将句子的指针指向空格的下一个字符。
- 将每个单词的首字符指针入栈，待所有单词处理完毕后依此出栈输出结果。
代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
using namespace std;
char* getNextWord(char* &str) {
int pos_spc = 0;
char *p = NULL;
if(str == NULL) return NULL; //若句子字符串为空，说明已经处理了所有单词
while(pos_spc < strlen(str)) {
if(str[pos_spc] == ' ') {
break; //找到空格位置跳出循环
}
pos_spc++;
}
p = str; //返回单词第一个字符的指针
if(pos_spc == strlen(str)) { //遍历到字符串的结束符而结束循环
str = NULL;
} else {
str[pos_spc] = '\0'; //将原空格字符改置为结束符
str = str + pos_spc + 1;
}
return p;
}
int main() {
char *str = (char*)malloc(5000*sizeof(char));
char *p;
stack<char*> s;
while(gets(str) != NULL) {
int i = 0;
while(!s.empty()) s.pop();
while((p = getNextWord(str)) != NULL) {
s.push(p); //将每个单词的首字母指针入栈
}
while(!s.empty()) {
printf("%s", s.top());
s.pop();
if(s.size() != 0) printf(" ");
}
}
return 0;
}
