3

在一次编码面试中，我被问到下一个问题：

编写一个程序，计算输入流中的字数和行数。
假设您有一个使用 nextChar() 方法的阅读器。

乍一看，它看起来很简单。但后来你意识到，你需要处理很多状态，比如：

  • 连续的字/行分隔符
  • 不同的词尾条件 - 单词分隔符或行分隔符或 EOF
  • 以单词分隔符开头的新字符串
  • ETC

在面试中，我想出了一种带有许多 if-else 和标志的意大利面条代码。

但是我认为对于这类问题应该有一个正式的方法，它可以让你保证你处理了所有可能的情况，并且可以给出一个结构化的解决方案。

我认为这可能来自自动机理论或编译器理论（我以前从未深入研究过这两个领域中的任何一个）。

因此，如果您在上述问题中识别出某种类型的问题，或者您知道哪种理论涵盖了此类问题，请告诉我。

4

1 回答 1

4

有限状态机。

这本质上是一个小的词法分析任务。解决方案永远不会很漂亮，但是如果您以以下方式编写代码，您可以对正确性充满信心：

curState <- NONE
while(c <- getChar)
    switch(curState) {
       case NONE:
           switch(c) {
               // ....
           }
           break;
       // .....
    }
}

您还可以使用数据结构来存储转换函数（给定一个状态和一个字符，下一个状态是什么？）但对于您的情况，只编写代码可能是最好的选择。

...不要忘记您的文本编码！UTF-16，对吧？:)

您可能想查看 Unixwc实用程序的实现：

这些将比你在面试中所做的更精致和更有特色，但无论如何都很高兴看到。

于 2013-03-15T17:26:27.110 回答