狀態機編程思想（1）：括弧內外字元串統計

這是曾經的一個面試題，正好引出狀態機編程思想。挺不錯的一個例子。

題目描述

給定一個字元串，它由以下字元組成：

• 左括弧“(”
• 右括弧“）”
• 下劃線“_” 
• 大小寫字母構成的字元串（單字母也算作字元串）

該字元串組成有以下規則限定：

• 括弧成對出現且不會嵌套，保證語法正確
• 字元串可以出現在括弧內，也可以出現在括弧外
• 各個字元串之間必須用下劃線“_”隔開
• 括弧外的字元串必須以下劃線“_”為邊界；括弧內字元串的邊界可以是下劃線“_”，也可以是括弧“（”、“）”

請解決問題：

• 括弧內字元串個數
• 統計括弧外最長字元串的長度

 傳統思路

我們拿到這個問題時，第一感覺往往是順序遍歷字元串，並檢測左右相鄰字元是否滿足邊界條件，從而進行分支處理。但是這樣做有以下棘手之處：

• 判定括弧邊界時需要保存之前的狀態，而處理程式和判定狀態邏輯往往混亂成一鍋粥，難解難分
• 不同狀態下的處理邏輯不同，這樣對於大型問題，邏輯之間有可能產生耦合，甚至在不同狀態間跳來跳去
• 還有效率問題，每次處理當前字元時還有同時處理左右相鄰字元，工作量有冗餘，效率降低

嗯，不信的話，可以自己按照上述最簡單的思路實現一下，你就明白了。

有人說，複雜邏輯我不怕啊，細心就好。So...是時候請出我們的大俠--“狀態機”了。

狀態機思路

狀態機是編譯原理中的一種技術，學過電學的讀者應該也在《數字電子技術》中用過它，歸根結底，就是把複雜的問題邏輯化為一個一個的狀態，我們處理問題的過程就是在各個狀態之間不斷遷移（包含自遷移），這樣畫出來的圖就叫做狀態遷移圖，幫助我們把一鍋難纏的粥轉化為一張清晰的網。當然，這裡不會深究狀態機的概念，詳情請自查（比如還有狀態遷移表等等）。

讓我們用狀態遷移圖表示上面的問題（若看不清圖，可以右鍵在新的標簽頁看，或者下載下來看）：

我設置了兩個狀態，一個用來區分括弧內外，一個用來區分是否是字母，從而進行不同的處理。

括弧內外分成了兩個子狀態，這兩個子狀態是互斥的，因此他們內部的狀態變數可以共用。

至於狀態之間轉移條件，直接看代碼即可理解：

 1 public class CountWords {
 2 
 3     final static int InBracket = 0;// 括弧內
 4     final static int OutBracket = 1;// 括弧外
 5 
 6     final static int IsLetter = 0;// 是字母
 7     final static int NotLetter = 1;// 不是字母
 8 
 9     public static void main(String[] args) {
10         test("_yy_()()_(_apple_welcome)_ssjjjs_");//2,6
11         test("__()()_(_)__()_");//0,0
12         test("_ya_");//0,2
13         test("_yy_(_)(r)_(_wel_c_ome_k)_");//5,2
14         test("_yy_aa_");//0,2
15         test("_yy_(aaa_bb_c)()__yyyyy_");//3,5
16         test("(u)_()_(__)()_yy_()");//1,2
17         test("__(a_wwwww)");//2,0
18         test("__(_a_wwwww_)_____ddd____()()()()()()");//2,3
19     }
20 
21     public static void test(String str) {
22         // 狀態初始化
23         int state_INOUT = OutBracket;
24         int state_letter = NotLetter;
25         // 統計結果初始化
26         int outLengthOfLongestWord = 0;
27         int outLengthOfCurrentWord = 0;
28         int inNumsOfWord = 0;
29         // 開始處理
30         for (int i = 0; i < str.length(); ++i) {
31             // 取出當前字元
32             char c = str.charAt(i);
33             // 根據括弧設置狀態：括弧內、括弧外
34             if (c == '(') {
35                 state_INOUT = InBracket;
36             }
37             if (c == ')') {
38                 state_INOUT = OutBracket;
39             }
40             // 括弧內狀態
41             if (state_INOUT == InBracket) {
42                 if (state_letter == IsLetter) {
43                     if (c == '_' || c == ')') {
44                         state_letter = NotLetter;
45                     }
46                 } else if (state_letter == NotLetter) {
47                     if (Character.isLetter(c)) {
48                         state_letter = IsLetter;
49                         ++inNumsOfWord;
50                     }
51                 }
52             }
53             // 括弧外狀態
54             else if (state_INOUT == OutBracket) {
55                 if (state_letter == IsLetter) {
56                     // System.out.println(c);
57                     if (c == '_' || c == '(') {
58                         if (outLengthOfLongestWord < outLengthOfCurrentWord) {
59                             outLengthOfLongestWord = outLengthOfCurrentWord;
60                         }
61                         outLengthOfCurrentWord = 0;
62                         state_letter = NotLetter;
63                     } else if (Character.isLetter(c)) {
64                         ++outLengthOfCurrentWord;
65                     }
66                 }
67                 if (state_letter == NotLetter) {
68                     if (Character.isLetter(c)) {
69                         state_letter = IsLetter;
70                         ++outLengthOfCurrentWord;
71                     }
72                 }
73             }
74         }
75         System.out.println("括弧內的字元串數：" + inNumsOfWord);
76         System.out.println("括弧外的最長字元串長度：" + outLengthOfLongestWord);
77         System.out.println();
78 
79     }
80 
81 }

有沒有感覺到很方便？思路更清晰了，效率也上去了。

註：狀態機不同於設計模式中常說的狀態模式。

就這麼多吧，歡迎提出測試樣例找bug，共同進步。