入门算法 - 句子逆序输出

内容同步于我的博客: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;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,464评论 0 5
  • 感赏今天儿子自己完成了作业,家教大哥哥有事没来,但还是自己做了。感赏儿子期中考试成绩有进步,虽然儿子自己不太满意,...
    糊兔兔阅读 187评论 1 1
  • 最近李敖特别的忙,他在和洪门等几位老大商量攻打欧阳家族的事宜,为了给欧阳家族以致命的打击,将其彻底的拔除,几大势力...
    热血谢少阅读 340评论 0 4
  • 风花雪月古城繁, 洱海湖水碧浪涟。 万壑苍山神韵在, 芳华烟雨等君观。
    耆女阅读 93评论 0 1
  • 红日山间坠,金光水中闪。 风筝空中飘,虹桥江中落。 行人走,鱼儿游。 灯光点点,晚风习习。 霞光闪闪 ,波光粼粼。...
    漳州荣妈阅读 290评论 0 0