這次“趣味編程”的目的是解析字符串，從一個(gè)指定模式的字符串中提取信息。對(duì)于目前這個(gè)問題，解決方案有很多種，例如直接拆分，使用正則表達(dá)式，或是如現(xiàn)在本文這般按照順序解析。總結(jié)果上來說，這些做法都是可取的，不過現(xiàn)在我打算舉出的做法是我認(rèn)為最為“典型”也最有“學(xué)習(xí)”和“展現(xiàn)”價(jià)值的解決方案：基于狀態(tài)機(jī)的順序字符解析。也歡迎您對(duì)此其他的做法進(jìn)行深入分析。

您可能需要重新閱讀上一篇文章來回憶字符串解析的具體規(guī)則，起始?xì)w納起來，它只有以下三點(diǎn)：

一個(gè)text由一至多個(gè)token group組成；一個(gè)token group由一至多個(gè)token組成。

token group的token之間使用單條橫線“-”進(jìn)行分割；text的token group之間使用兩條橫線“--”進(jìn)行分割。

token可以使用單引號(hào)包裹，單引號(hào)包裹內(nèi)的橫線作為普通字符處理，單引號(hào)包裹內(nèi)使用兩個(gè)單引號(hào)表示單個(gè)單引號(hào)。

至于最終結(jié)果，便是將一個(gè)text字符串，拆分成一個(gè)token group列表：

static List<List<string>> Parse(string text) { ... }

在這里，我們使用List<string>來表示一個(gè)token group（即token列表）。自然，表現(xiàn)方式可以有所不同。例如您的Parse方法如果返回“列表的數(shù)組”、“數(shù)組的列表”或是“數(shù)組的數(shù)組”都是沒有任何問題的。

下面的做法基于winter-cn在上一篇文章后面的回復(fù)，再加以簡(jiǎn)單的修改和注釋后得到的結(jié)果。這個(gè)做法的思路和我在“出題”時(shí)已經(jīng)準(zhǔn)備的“參考答案”不謀而合，但是winter-cn的實(shí)現(xiàn)要比我的更為簡(jiǎn)單、因此我的代碼就不拿出來獻(xiàn)丑了，我們現(xiàn)在一起來欣賞高手的勞動(dòng)成果。

winter-cn的做法，是將“解析”工作拆分為5種狀態(tài)，每種狀態(tài)對(duì)應(yīng)一種解析邏輯，而每種解析邏輯除了處理當(dāng)前字符（改變一些公共狀態(tài)）以外，還會(huì)返回處理下一個(gè)字符所使用的“解析邏輯”——這就是狀態(tài)的遷移。winter-cn原有的做法是使用Func<char, object>來表示解析邏輯的類型，這樣在每次得到新狀態(tài)之后，還需要將其轉(zhuǎn)化為Func<char, object>。不過為了更清晰地表達(dá)這樣一種邏輯，我們也可以定義一個(gè)返回自身類型的“遞歸”的委托類型：

delegate StateParser StateParser(char ch);

在現(xiàn)在的實(shí)現(xiàn)中，我們把它解析過程分解為5個(gè)狀態(tài)，分別對(duì)應(yīng)不同“時(shí)刻”下的解析邏輯：

static List<List<string>> Parse(string text) {StateParser p1 = null; // 用于解析token的起始字符StateParser p2 = null; // 用于解析作為分隔符的“-”的下一個(gè)字符StateParser p3 = null; // 用于解析token中或結(jié)尾的單引號(hào)的下一個(gè)字符StateParser p4 = null; // 用于解析單引號(hào)外的token字符StateParser p5 = null; // 用于解析單引號(hào)內(nèi)的token字符var currentToken = new StringBuilder(); // 用于構(gòu)建當(dāng)前的token（即收集字符）var currentTokenGroup = new List<string>(); // 用于構(gòu)建當(dāng)前的token group（即收集token）var result = new List<List<string>>(); // 用于保存結(jié)果（即收集token group）...return result; }

p1至p5便是所謂的“狀態(tài)”，也就是“解析邏輯”，它們都會(huì)操作currentToken，currentTokenGroup和result三個(gè)數(shù)據(jù)，并返回下一個(gè)狀態(tài)。狀態(tài)的劃分并非只有一種，不同的狀態(tài)劃分方式會(huì)形成不同的邏輯。我們接下來便要根據(jù)這樣的劃分方式，為每個(gè)狀態(tài)指定實(shí)現(xiàn)了。在實(shí)現(xiàn)的過程中，我們需要時(shí)刻遵守“當(dāng)前”狀態(tài)的邏輯細(xì)節(jié)，以及其他狀態(tài)的職責(zé)，這樣實(shí)現(xiàn)狀態(tài)的遷移似乎也并不是一件困難的事情。

首先是p1，它的作用是解析token的第一個(gè)字符：

// 解析token的起始字符 p1 = ch => {if (ch == '-'){// 如果token中需要包含單引號(hào)或“-”，// 那么這個(gè)token在表示的時(shí)候一定需要用一對(duì)單引號(hào)包裹起來throw new ArgumentException();}if (ch == '\''){// 如果起始字符是單引號(hào)，// 則開始解析單引號(hào)內(nèi)的token字符return p5;}else{// 如果是普通字符，則作為當(dāng)前token的字符，// 并開始解析單引號(hào)外的token字符currentToken.Append(ch);return p4;}};

接著是p2：它的作用是解析分隔符“-”（不包括單引號(hào)包裹內(nèi)的“-”）后的下一個(gè)字符：

// 解析作為分隔符的“-”的下一個(gè)字符 p2 = ch => {if (ch == '-'){// 如果當(dāng)前字符為“-”，說明一個(gè)token group結(jié)束了（因?yàn)榍耙粋€(gè)字符也是“-”），// 則將當(dāng)前的token group加入結(jié)果集，并且準(zhǔn)備新的token groupresult.Add(currentTokenGroup);currentTokenGroup = new List<string>();return p1;}else if (ch == '\''){// 如果當(dāng)前字符為單引號(hào)，則說明新的token以單引號(hào)包裹// 則開始解析單引號(hào)內(nèi)的token字符return p5;}else{// 如果是普通字符，則算作當(dāng)前token的字符，// 并繼續(xù)解析單引號(hào)外的token字符currentToken.Append(ch);return p4;} };

接著是p3：解析token內(nèi)部或結(jié)尾的單引號(hào)的下一個(gè)字符：

// 解析token內(nèi)部或結(jié)尾的單引號(hào)的下一個(gè)字符 p3 = ch => {if (ch == '\''){// 如果當(dāng)前字符為單引號(hào)，則說明連續(xù)兩個(gè)單引號(hào)，// 所以表明token中出現(xiàn)了“單個(gè)”單引號(hào)，并且當(dāng)前token一定包裹在單引號(hào)內(nèi)，// 因此繼續(xù)解析單引號(hào)內(nèi)的token字符currentToken.Append('\'');return p5;}else if (ch == '-'){// 如果當(dāng)前字符為一個(gè)分隔符，則說明上一個(gè)token已經(jīng)結(jié)束了// 于是將當(dāng)前token加入當(dāng)前token group，準(zhǔn)備新的token，// 并解析分隔符后的下一個(gè)字符currentTokenGroup.Add(currentToken.ToString());currentToken = new StringBuilder();return p2;}else{// 單引號(hào)后面只可能是另一個(gè)單引號(hào)或者一個(gè)分隔符，// 否則說明輸入錯(cuò)誤，則拋出異常throw new ArgumentException();} };

最后則是p4和p5，分別用于處理普通的token以及被單引號(hào)包裹的token字符：

// 用于解析單引號(hào)外的token字符， // 即一個(gè)沒有特殊字符（分隔符或單引號(hào)）的token p4 = ch => {if (ch == '\''){// 如果token中出現(xiàn)了單引號(hào)，則拋出異常throw new ArgumentException();}if (ch == '-'){// 如果出現(xiàn)了分隔符，則表明當(dāng)前token結(jié)束了，// 于是將當(dāng)前token加入當(dāng)前token group，準(zhǔn)備新的token，// 并解析分隔符的下一個(gè)字符currentTokenGroup.Add(currentToken.ToString());currentToken = new StringBuilder();return p2;}else{// 對(duì)于其他字符，則當(dāng)作token中的普通字符處理// 繼續(xù)解析單引號(hào)外的token字符currentToken.Append(ch);return p4;} };// 用于解析單引號(hào)內(nèi)的token字符 p5 = ch => {if (ch == '\''){// 對(duì)于被單引號(hào)包裹的token內(nèi)的第一個(gè)單引號(hào)，// 需要解析其下一個(gè)字符，才能得到其真實(shí)含義return p3;}else{// 對(duì)于普通字符，則添加到當(dāng)前token內(nèi)currentToken.Append(ch);return p5;} };

這些狀態(tài)中的邏輯都有一個(gè)特點(diǎn)，它們都會(huì)通過C#編譯器形成的閉包來操作“外部”狀態(tài)——不過這個(gè)“外部”是指這些匿名函數(shù)的外部，但是它們統(tǒng)統(tǒng)屬于Parse方法本身！這意味著，雖然我們的狀態(tài)并非“純函數(shù)”，但是Parse方法是沒有任何副作用（Side Effect，即除了返回值外不會(huì)影響其他外部狀態(tài)，以及相同的返回值永遠(yuǎn)相同的結(jié)果）。這個(gè)特點(diǎn)確保了Parse方法可以被任意多個(gè)線程同時(shí)調(diào)用。winter-cn的做法巧妙地使用了C#編譯器的特性，簡(jiǎn)化了Parse方法的實(shí)現(xiàn)。

在定義完5種狀態(tài)之后，我們便要從p1開始依次處理字符串中的每個(gè)字符，并且隨著狀態(tài)的遷移改變處理每個(gè)字符的邏輯。當(dāng)然，最后的“收尾”工作也是必不可少的：

static List<List<string>> Parse(string text) {...text.Aggregate(p1, (sp, ch) => sp(ch));currentTokenGroup.Add(currentToken.ToString());result.Add(currentTokenGroup);return result; }

可以看出，這種做法的優(yōu)勢(shì)之一是完全的“順序處理”，只遍歷一次。如果您使用字符串的分割或者正則表達(dá)式進(jìn)行解析的話，一般總是會(huì)有“回溯”，以及拆分出更多的字符串。因此，根據(jù)推測(cè)，這個(gè)做法從性能上來講應(yīng)該也有一定優(yōu)勢(shì)，不過還是需要真實(shí)的性能比較才能得出確切的結(jié)果。本文全部代碼已經(jīng)存放在http://gist.github.com/214427中，您可以復(fù)制、執(zhí)行，調(diào)試等等。

這次的“趣味編程”是到目前為止最為熱鬧的一次，在上一篇文章的回復(fù)里您還可以發(fā)現(xiàn)許多朋友給出的大量解決方案，不過由于時(shí)間精力有限，我無法一一瀏覽了。此外，由于winter-cn已經(jīng)給出了與我思路接近但實(shí)現(xiàn)更好的做法，后來我又用F#實(shí)現(xiàn)了另外一個(gè)思路不同的版本，您會(huì)發(fā)現(xiàn)F#有一些語言特性似乎非常適合進(jìn)行字符串解析工作，它對(duì)于我們編寫C#代碼也有一定的借鑒意義。

from:?http://blog.zhaojie.me/2009/10/code-for-fun-tokenizer-answer-1.html

總結(jié)

以上是生活随笔為你收集整理的趣味编程：从字符串中提取信息（参考答案 - 上）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。