題目描述

驗證給定的字符串是否可以解釋為十進制數字.

示例:

<code>"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

數字: 0-9
小數點: .
符號: +, -
指數: e/<code>

解題思路

看過題解的同學應該發現了, 如果用Python, 很多人直接調用float函數, 如果轉換成功則返回True, 如果拋出異常, 則返回False. 不得不說, 還真是個小機靈鬼呢~. 但是這種方式求解, 對於提升自己沒什麼太大的幫助. 下面講一下如何用自動機理論去求解這道題, 已經忘了自動機為何物的同學先翻一下編譯原理教材, 或者參考維基百科.

我們的目標是構造出一個DFA, 模擬輸入字符串在DFA上的運行, 如果處理完輸入的最後一個字符, DFA處在接受狀態, 那麼該字符串可以解釋為十進制數, 否則不能. 但是很難直接構造出一個滿足條件的DFA, 需要經過一個曲線救國的過程, 首先, 構造出一個能匹配目標字符串的正則表達式, 根據正則表達式構造出對應的NFA, 最後將NFA轉換成等價的DFA, 有了這個DFA之後就可以構造出其對應的狀態轉換表, 並且在代碼中使用了.

如何構造能夠匹配十進制數的正則呢? 先說先我的思路, 一個十進制數可以劃分成3個部分, 即: 1) 符號位; 2) base; 3) 冪次; 比如"-123.32e+4", 其中符號位和冪次可以為空, 並且這兩部分的正則比較容易寫. base部分有"23.", "23.34", "23", ".34"四種形式, 寫一個匹配這4種形式的正則也比較容易, 各位看官可以自己實現一下, 各部分的正則寫完之後拼接起來即可.

有了正則之後可以構造對應的NFA了, but how? 先看下正則表達式, 主要包含連接, 或, 閉包三種基本操作, 再複雜的正則也是由這三種基本操作組合而成的, 只需要瞭解這三種基本操作的NFA如何構造, 就可以構造出上面得到的正則對應的NFA了, 具體實現參考Thompson算法.

有了NFA之後, 需要構造等價的DFA, 所謂等價是二者接受的字符串集合相同, 因為NFA的狀態轉移不確定, 轉成DFA之後方便模擬運行. 通常使用子集構造算法進行NFA到DFA的轉換, 為了得到DFA的狀態轉換表, 這裡根據之前計算出的NFA手動模擬了子集構造算法的運行, 得到的狀態轉換表如下:

DFA狀態轉換表

其中狀態2, 4, 5, 7, 8, 10是接受狀態

代碼實現

<code>class Solution:

    table = [
        [1, 2, 3, -1, -1],
        [-1, 2, 3, -1, -1],
        [-1, 4, 5, 6, -1],
        [-1, 7, -1, -1, -1],
        [-1, 4, 8, 6, -1],
        [-1, 7, -1, 6, -1],
        [9, 10, -1, -1, -1],
        [-1, 7, -1, 6, -1],
        [-1, 8, -1, 6, -1],
        [-1, 10, -1, -1, -1],
        [-1, 10, -1, -1, -1]
    ]

    finals = [0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1]

    def isNumber(self, s: str) -> bool:
        return Solution.dfa(s)

    @staticmethod
    def dfa(s: str) -> bool:
        s = s.strip()
        q = 0  # DFA的初始狀態
        for ch in s:
            q = Solution.move(q, ch)
            # 跟蹤狀態轉換
            # print("state: %d" % (q))
            if q == -1:
                return False
        return Solution.finals[q] == 1

    @staticmethod
    def move(q: int, ch):
        if ch in '+-':
            idx = 0
        elif ch in '0123456789':
            idx = 1
        elif ch in '.':
            idx = 2 

        elif ch in 'e':
            idx = 3
        else:
            idx = 4
        return Solution.table[q][idx]/<code>