天天看點

狀态機程式設計思想(1):括号内外字元串統計

這是曾經的一個面試題,正好引出狀态機程式設計思想。挺不錯的一個例子。

題目描述

給定一個字元串,它由以下字元組成:

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

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

  • 括号成對出現且不會嵌套,保證文法正确
  • 字元串可以出現在括号内,也可以出現在括号外
  • 各個字元串之間必須用下劃線“_”隔開
  • 括号外的字元串必須以下劃線“_”為邊界;括号内字元串的邊界可以是下劃線“_”,也可以是括号“(”、“)”

請解決問題:

  • 括号内字元串個數
  • 統計括号外最長字元串的長度

 傳統思路

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

  • 判定括号邊界時需要儲存之前的狀态,而處理程式和判定狀态邏輯往往混亂成一鍋粥,難解難分
  • 不同狀态下的處理邏輯不同,這樣對于大型問題,邏輯之間有可能産生耦合,甚至在不同狀态間跳來跳去
  • 還有效率問題,每次處理目前字元時還有同時處理左右相鄰字元,工作量有備援,效率降低

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

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

狀态機思路

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

讓我們用狀态遷移圖表示上面的問題(若看不清圖,可以右鍵在新的标簽頁看,或者下載下傳下來看):

狀态機程式設計思想(1):括号内外字元串統計

我設定了兩個狀态,一個用來區分括号内外,一個用來區分是否是字母,進而進行不同的處理。

括号内外分成了兩個子狀态,這兩個子狀态是互斥的,是以他們内部的狀态變量可以共用。

至于狀态之間轉移條件,直接看代碼即可了解:

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/』

上一篇: 程序
下一篇: pikachu靶場