這是曾經的一個面試題,正好引出狀态機程式設計思想。挺不錯的一個例子。
題目描述
給定一個字元串,它由以下字元組成:
- 左括号“(”
- 右括号“)”
- 下劃線“_”
- 大小寫字母構成的字元串(單字母也算作字元串)
該字元串組成有以下規則限定:
- 括号成對出現且不會嵌套,保證文法正确
- 字元串可以出現在括号内,也可以出現在括号外
- 各個字元串之間必須用下劃線“_”隔開
- 括号外的字元串必須以下劃線“_”為邊界;括号内字元串的邊界可以是下劃線“_”,也可以是括号“(”、“)”
請解決問題:
- 括号内字元串個數
- 統計括号外最長字元串的長度
傳統思路
我們拿到這個問題時,第一感覺往往是順序周遊字元串,并檢測左右相鄰字元是否滿足邊界條件,進而進行分支處理。但是這樣做有以下棘手之處:
- 判定括号邊界時需要儲存之前的狀态,而處理程式和判定狀态邏輯往往混亂成一鍋粥,難解難分
- 不同狀态下的處理邏輯不同,這樣對于大型問題,邏輯之間有可能産生耦合,甚至在不同狀态間跳來跳去
- 還有效率問題,每次處理目前字元時還有同時處理左右相鄰字元,工作量有備援,效率降低
嗯,不信的話,可以自己按照上述最簡單的思路實作一下,你就明白了。
有人說,複雜邏輯我不怕啊,細心就好。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,共同進步。
『注:本文來自部落格園“小溪的部落格”,若非聲明均為原創内容,請勿用于商業用途,轉載請注明出處http://www.cnblogs.com/xiaoxi666/』