入门算法 - 句子逆序输出

内容同步于我的博客：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

问题分析

对于这类倒置的问题，最容易想到的就是利用栈的先进后出的特性。只需将每个单词入栈，然后再依此出栈输出即可。

算法描述

1. 将每个单词入栈，其具体方法为将单词后的空格替换为字符串结束符"\0"，同时返回单词第一个字符的指针，然后将句子的指针指向空格的下一个字符。
2. 将每个单词的首字符指针入栈，待所有单词处理完毕后依此出栈输出结果。

代码

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