回文

回文：正反读都一样的单词或者短语

Version 1

bool IsPalindrome(string input) {
for(int k = 0; k < input.size() / 2; ++k)
    if(input[k] != input[input.length() - 1 – k])
        return false;
    return true;
}    

Version 2 （使用STL）

bool IsPalindrome(string input) {
    string reversed = input;
    reverse(input.begin(), input.end());
    return reversed == input;
}

以上代码需要创建副本，所以效率会降低。

Version 3 （使用STL）

bool IsPalindrome(string input) {
　　return equal(input.begin(), input.begin() + input.size() / 2,
　　input.rbegin());
}

Version 3可以很好的完成任务，现在我们加上对字符的判断（是否为字母，并且转换字母的大小写）：

bool IsPalindrome(string input) {
    input.erase(remove_if(input.begin(), input.end(), IsNotAlpha), input.end());
    transform(input.begin(), input.end(), input.begin(), ::toupper);
    return equal(input.begin(), input.begin() + input.size() / 2, input.rbegin());
}

以上是基于字母的回文，下面我们队单词回文的情况进行分析，可以分为3步：

　　1. 把除去字母和空格的其他字符去掉，并转换成统一的大小写；

　　2. 把输入转化成一个word的list；

　　3. 判断这个list是否正反一致。

bool IsNotAlphaOrSpace(char ch) {
    return !isalpha(ch) && !isspace(ch);
}

bool IsWordPalindrome(string input) {
    input.erase(remove_if(input.begin(), input.end(), IsNotAlphaOrSpace), input.end());
    transform(input.begin(), input.end(), input.begin(), ::toupper);

    stringstream tokenizer(input);
    vector<string> tokens;

    tokens.insert(tokens.begin(), istream_iterator<string>(tokenizer), istream_iterator<string>());
    return equal(tokens.begin(), tokens.begin() + tokens.size() / 2, tokens.rbegin());
}

 (以上参考CS106L Course Reader Chapter 7:STL Algorithms)

下面是一个倒序输出英文句子单词的实现:

/**
 *  给定一个英文的句子，倒序输出其中的单词，字符串只包含字母和空格
 *  比如"My name is Han Meimei", 输出"Meimei Han is name My"
 */

#include <iostream>
#include <cctype>
#include <cstring>
using namespace std;

bool IsSpace(char ch) {
    return isspace(ch);
}

void revert(const char* source) {
    int length = strlen(source);
    int l = 0;

    for(int i = length - 1; i >= -1; --i) {
        if(IsSpace(*(source + i)) || i == -1){
            for(int j = 1; j <= l; ++j){
                cout<<*(source + i + j);
            }
            if(i != -1) cout<<' ';
            l = 0;
        }
        else ++l;
    }
    cout<<endl;
}

int main() {
    const char* source = "My name is Han Meimei";

    revert(source);

    return 0;
}

另一种思路：如果结果需要存储的话，把每个单词都逆序，再把整个句子逆序就可以（或者先逆序整个句子，再逆转每一个单词）