一、問題來源

今天做力克題目的時候看到了字符串轉(zhuǎn)換整數(shù)的一道算法題，其中又看到了題解中有自動機的概念，所以在這里對自動機做個筆記。題目鏈接

二、題目描述

請你來實現(xiàn)一個 myAtoi(string s) 函數(shù)，使其能將字符串轉(zhuǎn)換成一個 32 位有符號整數(shù)（類似 C/C++ 中的 atoi 函數(shù)）。函數(shù) myAtoi(string s) 的算法如下：

1. 讀入字符串并丟棄無用的前導(dǎo)空格
2. 檢查下一個字符（假設(shè)還未到字符末尾）為正還是負(fù)號，讀取該字符（如果有）。 確定最終結(jié)果是負(fù)數(shù)還是正數(shù)。 如果兩者都不存在，則假定結(jié)果為正。
3. 讀入下一個字符，直到到達下一個非數(shù)字字符或到達輸入的結(jié)尾。字符串的其余部分將被忽略。
4. 將前面步驟讀入的這些數(shù)字轉(zhuǎn)換為整數(shù)（即，“123” -> 123， “0032” -> 32）。如果沒有讀入數(shù)字，則整數(shù)為 0 。必要時更改符號（從步驟 2 開始）。
5. 如果整數(shù)數(shù)超過 32 位有符號整數(shù)范圍 [?231, 231 ? 1] ，需要截斷這個整數(shù)，使其保持在這個范圍內(nèi)。具體來說，小于 ?231 的整數(shù)應(yīng)該被固定為 ?231 ，大于 231 ? 1 的整數(shù)應(yīng)該被固定為 231 ? 1 。
6. 返回整數(shù)作為最終結(jié)果。

注意：

• 本題中的空白字符只包括空格字符 ’ ’ 。
• 除前導(dǎo)空格或數(shù)字后的其余字符串外，請勿忽略 任何其他字符。

示例 1：
輸入：s = “42”
輸出：42
解釋：加粗的字符串為已經(jīng)讀入的字符，插入符號是當(dāng)前讀取的字符。
第 1 步：“42”（當(dāng)前沒有讀入字符，因為沒有前導(dǎo)空格）
第 2 步：“42”（當(dāng)前沒有讀入字符，因為這里不存在 ‘-’ 或者 ‘+’）
第 3 步：“42”（讀入 “42”）
解析得到整數(shù) 42 。
由于 “42” 在范圍 [-231, 231 - 1] 內(nèi)，最終結(jié)果為 42 。

示例 2：
輸入：s = " -42"
輸出：-42
解釋：
第 1 步：" -42"（讀入前導(dǎo)空格，但忽視掉）
第 2 步：" -42"（讀入 ‘-’ 字符，所以結(jié)果應(yīng)該是負(fù)數(shù)）
第 3 步：" -42"（讀入 “42”）
解析得到整數(shù) -42 。
由于 “-42” 在范圍 [-231, 231 - 1] 內(nèi)，最終結(jié)果為 -42 。

示例 3：
輸入：s = “4193 with words”
輸出：4193
解釋：
第 1 步：“4193 with words”（當(dāng)前沒有讀入字符，因為沒有前導(dǎo)空格）
第 2 步：“4193 with words”（當(dāng)前沒有讀入字符，因為這里不存在 ‘-’ 或者 ‘+’）
解析得到整數(shù) 4193 。
由于 “4193” 在范圍 [-231, 231 - 1] 內(nèi)，最終結(jié)果為 4193 。

三、題解中的自動機

思路

字符串處理的題目往往涉及復(fù)雜的流程以及條件情況，如果直接上手寫程序，一不小心就會寫出極其臃腫的代碼。

因此，為了有條理地分析每個輸入字符的處理方法，我們可以使用自動機這個概念：

我們的程序在每個時刻有一個狀態(tài) s，每次從序列中輸入一個字符 c，并根據(jù)字符 c 轉(zhuǎn)移到下一個狀態(tài) s’。這樣，我們只需要建立一個覆蓋所有情況的從 s 與 c 映射到 s’ 的表格即可解決題目中的問題。

算法
本題可以建立如下圖所示的自動機：

接下來編程部分就非常簡單了：我們只需要把上面這個狀態(tài)轉(zhuǎn)換表抄進代碼即可

四、自動機學(xué)習(xí)

根據(jù)上述，我們大概對自動機有一個初步的了解，接下來就詳細(xì)地學(xué)習(xí)一下自動機
自動機是有限狀態(tài)機(FSM)的數(shù)學(xué)模型。

FSM 是給定符號輸入，依據(jù)(可表達為一個表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過一系列狀態(tài)的一種機器。在常見的 FSM 的“Mealy”變體中，這個轉(zhuǎn)移函數(shù)告訴自動機給定當(dāng)前狀態(tài)和當(dāng)前字符的時候下一個狀態(tài)是什么。

逐個讀取輸入中的符號，直到被完全耗盡(把它當(dāng)作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。一旦輸入被耗盡，自動機被稱為“停止”了。

依賴自動機停止時的狀態(tài)，稱呼這個自動機要么是“接受”要么“拒絕”這個輸入。如果停止于“接受狀態(tài)”，則自動機“接受”了這個字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個字被“拒絕”。自動機接受的所有字的集合被稱為“這個自動機接受的語言”。

自動機 automaton 原來是模仿人和動物的行動而做成的機器人的意思。但是現(xiàn)已被抽象化為如下的機器。時間是離散的（t=0，1，2……），在每一個時刻它處于所存在的有限個內(nèi)部狀態(tài)中的一個。對每一個時刻給予有限個輸入中的一個。那么下一個時刻的內(nèi)部狀態(tài)就由現(xiàn)在的輸入和現(xiàn)在的內(nèi)部狀態(tài)所決定。每個時刻的輸出只由那個時刻的內(nèi)部狀態(tài)所決定。

五、有限狀態(tài)機的使用場景

有限狀態(tài)機的寫法，邏輯清晰，表達力強，有利于封裝事件。一個對象的狀態(tài)越多、發(fā)生的事件越多，就越適合采用有限狀態(tài)機的寫法。