Fifnmar edited 4 年，9 月前
解决问题的基本思路，是从抽象到具体、从整体到局部。现在，我们先思考：为了解决这个问题，可以大致把它分成几步：
Morse -> Plaintext 字典，把切段翻译成明文。这样看上去，只有中间两步需要我们细细考虑。
功能实现起来往往没有一开始想象得那么简单，因为我们可能遇到各种特殊要求。我们还应该对「边界情况」(Corner Cases) 有足够的敏感。而这种敏感来源于对问题的细致理解。
本题中，一个易于想到的想法是，把 '/' 看作「定界符」(Delimiter)，凡遇到它就切段。这是很普遍的做法，只不过一般情况下，定界符是空白。
现在有一个特殊要求：三个 '/' 代表一个 ' '，五个 '/' 代表一个 '.'。这是本题唯一的小难点。这说明「有的 '/' 并不是定界符」。虽然我们应该避免设计出功能杂糅的标记，但有时不得不处理它们。为此，可以提出两种解决方案：
'/' 时，都「窥视」(Peek) 一下后面的那个字符是不是 '/'，只有这样才能确定该不该在此切段。'/' 当作单纯的定界符，凡是遇到 '/' 就切段，这样会出现一些空段。翻译时，如果发现四个空段，就翻译成 '.'；不然，如果发现两个空段，就翻译成 ' '。如果采用第一种方案，那么不得不对 '/' 做出复杂的判断才能找对分界的位置。而如果采用第二种方案，虽然引入了空段，但处理起来相对简单。我认为，不应该把翻译相关的任务（ '/' 涉及到的翻译细节）交给 split() 函数。所以，我们采用第二种方案。感兴趣的同学们可以试试第一种。
在切割模块中，需要注意最后一段的切割问题——它之后可能没有 '/'，也就是说一个切段既可能以 '/' 结尾，也可能以 '\0' 结尾。这将复杂化我们的判断逻辑。为此，可以使用「哨兵」(Sentinel) 思想。哨兵是用来简化逻辑的元素。如果我们在最后一段以 '\0' 结尾的情况下给 str 结尾添加一个 '/'，就可以简化逻辑。下面是一份直观的实现：
vector<string> split(string str) {
if (str.empty() || str.back() != '/')
str.push_back('/'); // 哨兵，简化逻辑。
vector<string> ret; // 本书中要返回的对象一般都命名为 ret。
auto i = str.begin(), ed = str.end(); // i 标记切段的开头
for (auto iter = i; iter != ed; ++iter) {
if (*iter == '/') {
ret.push_back({i, iter});
i = iter + 1;
} // 确认了一个切段。现在把这个切段装进 ret 中，并重新设置 i。
}
return ret;
}
然后是是解析模块。有前一个模块的帮助，现在思路可以很明确了。如果是普通的切段，就翻译得到一个字符。特别地，如果有连续两个空段，就是一个 ' '；如果有连续四个空段，就是一个 '.'。这个模块同样有「处理最后一组切段」的特殊问题。因为出现两个空白切段时还不能确定是空格还是句号，所以我采用的方法是先记下目前遇到的空白切段数量，等遇到一个普通切段时再做决定（延迟决策，Lazy Policy）。但如果切段数组的末尾有空段，那么循环退出时记录将得不到更新。所以我不得不再加一次检验。如果你使用的是别的方法，比如加哨兵，或许不需要这样做。
string translate(vector<string> vec) {
// 下面是我们的字典。map 类型可以把一种「键」(Key) 和一个「值」(Value) 对应起来。
// 没有必要在每次调用 translate() 时都创建一个字典，不如设为 static。(￣▽￣)"
const static unordered_map<string, char> dic{
{".-", 'A'}, {"-...", 'B'}, {"-.-.", 'C'}, {"-..", 'D'}, {".", 'E'},
{"..-.", 'F'}, {"--.", 'G'}, {"....", 'H'}, {"..", 'I'}, {".---", 'J'},
{"-.-", 'K'}, {".-..", 'L'}, {"--", 'M'}, {"-.", 'N'}, {"---", 'O'},
{".--.", 'P'}, {"--.-", 'Q'}, {".-.", 'R'}, {"...", 'S'}, {"-", 'T'},
{"..-", 'U'}, {"...-", 'V'}, {".--", 'W'}, {"-..-", 'X'}, {"-.--", 'Y'},
{"--..", 'Z'}, {"-----", '0'}, {".----", '1'}, {"..---", '2'}, {"...--", '3'},
{"....-", '4'}, {".....", '5'}, {"-....", '6'}, {"--...", '7'}, {"---..", '8'},
{"----.", '9'}}; // map 的使用方法可以查阅 cppreference.com
string ret;
uint32_t blank_cnt = 0;
for (auto const &i : vec) {
if (i == "") {
++blank_cnt;
} else {
if (blank_cnt) {
ret.push_back(blank_cnt == 2 ? ' ' : '.');
blank_cnt = 0;
}
ret.push_back(dic.at(i));
}
}
if (blank_cnt) // Do not forget trailing blanks.
ret.push_back(blank_cnt == 2 ? ' ' : '.');
return ret;
}
注意我使用一个独立的词典来记录「莫尔斯电码
->明文」的对应关系。这种思想是「数据与逻辑分离」。不应该把相关数据都写成逻辑判断（比如if-else），那样会使数据和处理的逻辑杂糅在一起，不但不能使代码清晰易读，还难以修改。
很好，有了这两个模块，主逻辑就极为清晰了。
int main() {
uint32_t t; cin >> t;
for (uint32_t query = 0; query < t; ++query) {
string morse; cin >> morse;
printf("case #%u:\n%s\n", query, translate(split(morse)).data());
}
}
很多语言标准库的
string自带切分函数。如果你使用的是这样的语言，可以直接调用它。尽管如此，自己实现一个类似功能的函数也是非常好的锻炼——相信如果没有看过本答案的话，你可能会在不少地方犹豫、踩坑。这样考虑各种细节的过程都是很好的思维训练。
我的注释中似乎暴露了什么 Orz。
这是我正在写的东西的一个摘录。