在编码面试中，我被问到下一个问题:
Write a program which counts the number of words and lines in the input stream.
Assume you have a reader with method nextChar().
乍一看很简单。但是后来您意识到，您需要处理很多状态，例如:
- 一个连续的单词/行分隔符
- 不同的词尾条件 - 词分隔符或行分隔符或 EOF
- 以单词分隔符开头的新字符串
- 等等
在采访中，我想到了一种带有许多 if-else 和标志的意大利面条代码。
但我认为对于这类问题应该有一个正式的方法，它可以让你保证你处理了所有可能的情况，并且可以给出一个结构化的解决方案。
我认为这可能来自自动机理论或编译器理论(我以前从未深入研究过这两个领域中的任何一个)。
因此，如果您认识到上述问题中的某种类型的问题，或者您知道哪种理论涵盖了此类问题，请告诉我。
最佳答案
这本质上是一个小的 lexing任务。解决方案永远不会很漂亮，但如果您按照以下方式编写代码，您可以对正确性充满信心:
curState <- NONE
while(c <- getChar)
switch(curState) {
case NONE:
switch(c) {
// ....
}
break;
// .....
}
}
您还可以使用数据结构来存储转换函数(给定一个状态和一个字符，下一个状态是什么？)但是对于您的情况，编写代码可能是最好的选择。
...不要忘记您的文本编码! UTF-16，对吧？ :)
您可能想查看 Unix wc 实用程序的实现:
这些将比您在面试中所做的更加精致和有特色，但无论如何都很高兴看到。
关于algorithm - 文本处理的形式化方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15438520/