這個(gè)編程題，讓人欲罷不能

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"、"-.1"、".1"、"3."、"46.e3"、" 1 "(有空格)都表示數(shù)值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"、" "、"1 2"等都不是。注意首尾可以有空格。

如果你學(xué)過 Python，你也許說這很簡(jiǎn)單，執(zhí)行下 float(str) 如果沒有拋出異常就說明是數(shù)值，否則就不是數(shù)值。

def?isNumber(x?:str)?->bool:
????try:
????????float(x)
????????return?True
????except:
????????return?False

自己用沒問題，但這顯然并不是正確的答案，如果你這樣回答面試官，那很可能是讓你回去等通知，然后再也沒有通知。

那該怎么做呢？我自己最初也是滿腦子的 if else，嘗試了幾次之后，發(fā)現(xiàn)情況太多，不是這錯(cuò)，就是那種情況沒考慮到，腦細(xì)胞已經(jīng)明顯不夠用，花了整整一晚上，最終繳械投降，直接看看答案，原來自己還不會(huì)用「有限狀態(tài)自動(dòng)機(jī)」，雖然編譯原理課上講過，當(dāng)時(shí)覺得太枯燥，學(xué)完就忘了。這正是應(yīng)了那句話：學(xué)了不用，等于沒學(xué)。

接下來，我們需要弄明白什么是有限狀態(tài)自動(dòng)機(jī)，如何用它來解決問題？你不必去別處搜索本題答案，看完本文就夠了。

百科這樣介紹：有限狀態(tài)自動(dòng)機(jī)（FSM "finite state machine" 或者FSA "finite state automaton"， ）也叫有限狀態(tài)機(jī)，是為研究有限內(nèi)存的計(jì)算過程和某些語言類而抽象出的一種計(jì)算模型。

從字面意思，有限狀態(tài)自動(dòng)機(jī)擁有有限數(shù)量的狀態(tài)，每個(gè)狀態(tài)可以遷移到零個(gè)或多個(gè)狀態(tài)，有限狀態(tài)自動(dòng)機(jī)可以表示為一個(gè)有向圖，其作用主要是描述對(duì)象在它的生命周期內(nèi)所經(jīng)歷的狀態(tài)序列，以及如何響應(yīng)來自外界的各種事件，下圖是 TCP 協(xié)議狀態(tài)機(jī)，可以給你一個(gè)直觀的感受：

這些狀態(tài)中有一個(gè)特殊的狀態(tài)，被稱作「初始狀態(tài)」。還有一系列狀態(tài)被稱為「接受狀態(tài)」，它們組成了一個(gè)特殊的集合。其中，一個(gè)狀態(tài)可能既是「初始狀態(tài)」，也是「接受狀態(tài)」。

起初，這個(gè)自動(dòng)機(jī)處于「初始狀態(tài)」。隨后，它接受外部的輸入，按照某個(gè)事先約定好的「轉(zhuǎn)移規(guī)則」，從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)；當(dāng)狀態(tài)轉(zhuǎn)移完成后，它再次接受外部的輸入，再次進(jìn)行轉(zhuǎn)移。如果某個(gè)輸入無法找到對(duì)應(yīng)的轉(zhuǎn)移規(guī)則，那么計(jì)算終止，判斷該輸入為無效輸入。

類比到本題中，程序順序的讀取字符串中的每一個(gè)字符，按照某個(gè)事先約定好的「轉(zhuǎn)移規(guī)則」，從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)，如果找到對(duì)應(yīng)的「轉(zhuǎn)移規(guī)則」，那么繼續(xù)直到最后一個(gè)字符，如果都存在對(duì)應(yīng)的「轉(zhuǎn)移規(guī)則」，那么就能表示數(shù)值；如果某一字符不滿足事先約定好的「轉(zhuǎn)移規(guī)則」，那么就不能表示數(shù)值。

舉個(gè)例子，假如我們只定義一條「轉(zhuǎn)移規(guī)則」，即從符號(hào)位->整數(shù)，那么字符串“+5”就能表示數(shù)字，因?yàn)榈谝粋€(gè)字符為符號(hào)，第二個(gè)是整數(shù)，程序從左到右遍歷到5時(shí)，發(fā)現(xiàn)是從+號(hào)轉(zhuǎn)移到整數(shù)，于是找到「轉(zhuǎn)移規(guī)則」，因此可以表示整數(shù)，而“5+”，“+-”不能表示數(shù)字，因?yàn)槎疾粷M足「轉(zhuǎn)移規(guī)則」。

現(xiàn)在問題來了，如何找到所有的狀態(tài)轉(zhuǎn)移規(guī)則？

要想找到所有的狀態(tài)轉(zhuǎn)移規(guī)則，我們先找到所有的狀態(tài)，再確定哪些是表示數(shù)字的合法轉(zhuǎn)移狀態(tài)。根據(jù)一個(gè)數(shù)據(jù)的表示，不難找出所有狀態(tài)：

1. 起始的空格

2. 符號(hào)位

3. 整數(shù)部分

4. 左側(cè)有整數(shù)的小數(shù)點(diǎn)

5. 左側(cè)無整數(shù)的小數(shù)點(diǎn)

6. 小數(shù)部分

7. 字符 e

8. 指數(shù)部分的符號(hào)位

9. 指數(shù)部分的整數(shù)部分

10. 末尾的空格

下一步是找出「初始狀態(tài)」和「接受狀態(tài)」的集合。根據(jù)題意，「初始狀態(tài)」應(yīng)當(dāng)為狀態(tài) 1，而「接受狀態(tài)」的集合則為狀態(tài) 3、狀態(tài) 4、狀態(tài) 6、狀態(tài) 9 以及狀態(tài) 10。換言之，字符串的末尾要么是空格，要么是數(shù)字，要么是小數(shù)點(diǎn)，但前提是小數(shù)點(diǎn)的前面有數(shù)字。

最后，需要定義「轉(zhuǎn)移規(guī)則」。結(jié)合數(shù)值字符串應(yīng)當(dāng)具備的格式，將自動(dòng)機(jī)轉(zhuǎn)移的過程以圖解的方式表示出來：

在實(shí)際代碼中，我們需要處理轉(zhuǎn)移失敗的情況。例如當(dāng)位于狀態(tài) 1（起始空格）時(shí)，沒有對(duì)應(yīng)字符 e 的狀態(tài)。為了處理這種情況，我們可以創(chuàng)建一個(gè)特殊的拒絕狀態(tài)。如果當(dāng)前狀態(tài)下沒有對(duì)應(yīng)讀入字符的「轉(zhuǎn)移規(guī)則」，我們就轉(zhuǎn)移到這個(gè)特殊的拒絕狀態(tài)。一旦自動(dòng)機(jī)轉(zhuǎn)移到這個(gè)特殊狀態(tài)，我們就可以立即判定該字符串不「被接受」。以上翻譯成代碼就是：

from?enum?import?Enum

def?isNumber(s:?str)?->?bool:
????State?=?Enum("State",?[
????????"STATE_INITIAL",
????????"STATE_INT_SIGN",
????????"STATE_INTEGER",
????????"STATE_POINT",
????????"STATE_POINT_WITHOUT_INT",
????????"STATE_FRACTION",
????????"STATE_EXP",
????????"STATE_EXP_SIGN",
????????"STATE_EXP_NUMBER",
????????"STATE_END",
????])
????Chartype?=?Enum("Chartype",?[
????????"CHAR_NUMBER",
????????"CHAR_EXP",
????????"CHAR_POINT",
????????"CHAR_SIGN",
????????"CHAR_SPACE",
????????"CHAR_ILLEGAL",#拒絕狀態(tài)
????])

????def?toChartype(ch:?str)?->?Chartype:
????????if?ch.isdigit():
????????????return?Chartype.CHAR_NUMBER
????????elif?ch.lower()?==?"e":
????????????return?Chartype.CHAR_EXP
????????elif?ch?==?".":
????????????return?Chartype.CHAR_POINT
????????elif?ch?==?"+"?or?ch?==?"-":
????????????return?Chartype.CHAR_SIGN
????????elif?ch?==?"?":
????????????return?Chartype.CHAR_SPACE
????????else:
????????????return?Chartype.CHAR_ILLEGAL  #拒絕狀態(tài)

????transfer?=?{
????????State.STATE_INITIAL:?{
????????????Chartype.CHAR_SPACE:?State.STATE_INITIAL,
????????????Chartype.CHAR_NUMBER:?State.STATE_INTEGER,
????????????Chartype.CHAR_POINT:?State.STATE_POINT_WITHOUT_INT,
????????????Chartype.CHAR_SIGN:?State.STATE_INT_SIGN,
????????},
????????State.STATE_INT_SIGN:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_INTEGER,
????????????Chartype.CHAR_POINT:?State.STATE_POINT_WITHOUT_INT,
????????},
????????State.STATE_INTEGER:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_INTEGER,
????????????Chartype.CHAR_EXP:?State.STATE_EXP,
????????????Chartype.CHAR_POINT:?State.STATE_POINT,
????????????Chartype.CHAR_SPACE:?State.STATE_END,
????????},
????????State.STATE_POINT:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_FRACTION,
????????????Chartype.CHAR_EXP:?State.STATE_EXP,
????????????Chartype.CHAR_SPACE:?State.STATE_END,
????????},
????????State.STATE_POINT_WITHOUT_INT:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_FRACTION,
????????},
????????State.STATE_FRACTION:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_FRACTION,
????????????Chartype.CHAR_EXP:?State.STATE_EXP,
????????????Chartype.CHAR_SPACE:?State.STATE_END,
????????},
????????State.STATE_EXP:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_EXP_NUMBER,
????????????Chartype.CHAR_SIGN:?State.STATE_EXP_SIGN,
????????},
????????State.STATE_EXP_SIGN:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_EXP_NUMBER,
????????},
????????State.STATE_EXP_NUMBER:?{
????????????Chartype.CHAR_NUMBER:?State.STATE_EXP_NUMBER,
????????????Chartype.CHAR_SPACE:?State.STATE_END,
????????},
????????State.STATE_END:?{
????????????Chartype.CHAR_SPACE:?State.STATE_END,
????????},
????}

????st?=?State.STATE_INITIAL
????for?ch?in?s:
????????typ?=?toChartype(ch)
????????if?typ?not?in?transfer[st]:
????????????return?False
????????st?=?transfer[st][typ]

????return?st?in?[State.STATE_INTEGER,?State.STATE_POINT,?State.STATE_FRACTION,?State.STATE_EXP_NUMBER,?State.STATE_END]


x?=?isNumber("?12.?")

print(x)

上述代碼使用了標(biāo)準(zhǔn)庫中的枚舉類，如果想知道更具體的用法參考官方文檔: https://docs.python.org/zh-cn/3.7/library/enum.html

上述算法的時(shí)間復(fù)雜度：O(N)，其中 N 為字符串的長度。我們需要遍歷字符串的每個(gè)字符，其中狀態(tài)轉(zhuǎn)移所需的時(shí)間復(fù)雜度為 O(1)。空間復(fù)雜度：O(1)。只需要?jiǎng)?chuàng)建固定大小的狀態(tài)轉(zhuǎn)移表。

一個(gè)有限狀態(tài)自動(dòng)機(jī)，總能夠回答某種形式的「對(duì)于給定的輸入字符串 S，判斷其是否滿足條件 P」的問題。在本題中，條件 P 即為「構(gòu)成合法的表示數(shù)值的字符串」。

有限狀態(tài)自動(dòng)機(jī)驅(qū)動(dòng)的編程，可以被看做一種暴力枚舉方法的延伸：它窮盡了在任何一種情況下，對(duì)應(yīng)任何的輸入，需要做的事情。

有限狀態(tài)自動(dòng)機(jī)在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用。在算法領(lǐng)域，它與大名鼎鼎的字符串查找算法「KMP」算法有著密切的關(guān)聯(lián)；在工程領(lǐng)域，它是實(shí)現(xiàn)「正則表達(dá)式」的基礎(chǔ)。

以上如果對(duì)你有所啟發(fā)，請(qǐng)記得給小編點(diǎn)個(gè)贊哦，感謝有你。