內(nèi)容同步于我的博客：https://blog.bigrats.net/archives/basic-alg-sentence-inverse.html

題目描述

將一個(gè)英文語(yǔ)句以單詞為單位逆序排放。例如："I am a boy"逆序輸出為"boy a am I"。所有單詞之間用一個(gè)空格隔開(kāi)，語(yǔ)句中除了英文字母外，不再包含其他字符。

輸入描述

輸入一個(gè)不包含符號(hào)的英文語(yǔ)句

輸出描述

輸出單詞逆置后的句子

示例

Input:

I am a boy

Output:

boy a am I

問(wèn)題分析

對(duì)于這類(lèi)倒置的問(wèn)題，最容易想到的就是利用棧的先進(jìn)后出的特性。只需將每個(gè)單詞入棧，然后再依此出棧輸出即可。

算法描述

1. 將每個(gè)單詞入棧，其具體方法為將單詞后的空格替換為字符串結(jié)束符"\0"，同時(shí)返回單詞第一個(gè)字符的指針，然后將句子的指針指向空格的下一個(gè)字符。
2. 將每個(gè)單詞的首字符指針入棧，待所有單詞處理完畢后依此出棧輸出結(jié)果。

代碼

#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;  //若句子字符串為空，說(shuō)明已經(jīng)處理了所有單詞
    while(pos_spc < strlen(str)) {
        if(str[pos_spc] == ' ') {
            break; //找到空格位置跳出循環(huán)
        }
        pos_spc++;
    }
    p = str; //返回單詞第一個(gè)字符的指針
    if(pos_spc == strlen(str)) { //遍歷到字符串的結(jié)束符而結(jié)束循環(huán)
        str = NULL;
    } else {
        str[pos_spc] = '\0'; //將原空格字符改置為結(jié)束符
        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); //將每個(gè)單詞的首字母指針入棧
        }
        while(!s.empty()) {
            printf("%s", s.top());
            s.pop();
            if(s.size() != 0) printf(" ");
        }
    } 
    
    return 0;
}