程序員面試寶典2ppt課件

1、編譯原理.正則表達式右結合.正則表達式在編寫處理字符串的程序或網(wǎng)頁時，經(jīng)常會有查找符合某些復雜規(guī)則的字符串的需要。正則表達式就是用于描述這些規(guī)則的工具。換句話說，正則表達式就是記錄文本規(guī)則的代碼。很可能你使用過Windows/Dos下用于文件查找的通配符(wildcard)，也就是*和?。如果你想查找某個目錄下的所有的Word文檔的話，你會搜索*.doc。在這里，*會被解釋成任意的字符串。.和通配符類似，正則表達式也是用來進行文本匹配的工具只不過比起通配符，它能更精確地描述你的需求當然，代價就是更復雜比如你可以編寫一個正則表達式，用來查找所有以0開頭，后面跟著2-3個數(shù)字，然后是一個連字號“-

2、”，最后是7或8位數(shù)字的字符串(0376-7654321)。.學習正則表達式的最好方法是從例子開始，理解例子之后再自己對例子進行修改，實驗。下面給出了不少簡單的例子，并對它們作了詳細的說明。假設在一篇英文小說里查找hi，你可以使用正則表達式hi。這幾乎是最簡單的正則表達式了，它可以精確匹配這樣的字符串：由兩個字符組成，前一個字符是h,后一個是i。通常，處理正則表達式的工具會提供一個忽略大小寫的選項，如果選中了這個選項，它可以匹配hi,HI,Hi,hI這四種情況中的任意一種。.不幸的是，很多單詞里包含hi這兩個連續(xù)的字符，比如him,history,high等等。用h

3、i來查找的話，這里邊的hi也會被找出來。如果要精確地查找hi這個單詞的話，我們應該使用bhib。b是正則表達式規(guī)定的一個特殊代碼（好吧，某些人叫它元字符，metacharacter），代表著單詞的開頭或結尾，也就是單詞的分界處。雖然通常英文的單詞是由空格，標點符號或者換行來分隔的，但是b并不匹配這些單詞分隔字符中的任何一個，它只匹配一個位置。.如果需要更精確的說法，b匹配這樣的位置：它的前一個字符和后一個字符不全是(一個是,一個不是或不存在)w。假如你要找的是hi后面不遠處跟著一個Lucy，你應該用bhib.*bLucyb。這里，.是另一個元字符，匹配除了換行符以外的任意字符。*同樣是元字符，

4、不過它代表的不是字符，也不是位置，而是數(shù)量它指定*前邊的內容可以連續(xù)重復使用任意次以使整個表達式得到匹配。因此，.*連在一起就意味著任意數(shù)量的不包含換行的字符?，F(xiàn)在bhib.*bLucyb的意思就很明顯了：先是一個單詞hi,然后是任意個任意字符(但不能是換行)，最后是Lucy這個單詞。.換行符就是n,ASCII編碼為10(十六進制0 x0A)的字符。如果同時使用其它元字符，我們就能構造出功能更強大的正則表達式。比如下面這個例子：0dd-dddddddd匹配這樣的字符串：以0開頭，然后是兩個數(shù)字，然后是一個連字號“-”，最后是8個數(shù)字(也就是中國的電話號碼。當然，這個例子只能匹配區(qū)號為3位的情形

5、)。.這里的d是個新的元字符，匹配一位數(shù)字(0，或1，或2，或)。-不是元字符，只匹配它本身連字符(或者減號，或者中橫線，或者隨你怎么稱呼它)。為了避免那么多煩人的重復，我們也可以這樣寫這個表達式：0d2-d8。 這里d后面的2(8)的意思是前面d必須連續(xù)重復匹配2次(8次)。.元字符(I)現(xiàn)在你已經(jīng)知道幾個很有用的元字符了，如b,.,*，還有d.正則表達式里還有更多的元字符，比如s匹配任意的空白符，包括空格，制表符(Tab)，換行符，中文全角空格等。w匹配字母或數(shù)字或下劃線或漢字等。對中文/漢字的特殊處理是由.Net提供的正則表達式引擎支持的，其它環(huán)境下的具體情況請查看相關文檔。.下面來看看

6、更多的例子：baw*b匹配以字母a開頭的單詞先是某個單詞開始處(b)，然后是字母a,然后是任意數(shù)量的字母或數(shù)字(w*)，最后是單詞結束處(b)。好吧，現(xiàn)在我們說說正則表達式里的單詞是什么意思吧：就是不少于一個的連續(xù)的w。不錯，這與學習英文時要背的成千上萬個同名的東西的確關系不大 :)d+匹配1個或更多連續(xù)的數(shù)字。這里的+是和*類似的元字符，不同的是*匹配重復任意次(可能是0次)，而+則匹配重復1次或更多次。bw6b 匹配剛好6個字符的單詞。.元字符(II)表1.常用的元字符代碼說明.匹配除換行符以外的任意字符w匹配字母或數(shù)字或下劃線或漢字s匹配任意的空白符d匹配數(shù)字b匹配單詞的開始或結束匹配字

7、符串的開始$匹配字符串的結束 .元字符(III)元字符（和數(shù)字6在同一個鍵位上的符號）和$都匹配一個位置，這和b有點類似。匹配你要用來查找的字符串的開頭，$匹配結尾。這兩個代碼在驗證輸入的內容時非常有用，比如一個網(wǎng)站如果要求你填寫的QQ號必須為5位到12位數(shù)字時，可以使用：d5,12$。這里的5,12和前面介紹過的2是類似的，只不過2匹配只能不多不少重復2次，5,12則是重復的次數(shù)不能少于5次，不能多于12次，否則都不匹配。.因為使用了和$，所以輸入的整個字符串都要用來和d5,12來匹配，也就是說整個輸入必須是5到12個數(shù)字，因此如果輸入的QQ號能匹配這個正則表達式的話，那就符合要求了。和忽略

8、大小寫的選項類似，有些正則表達式處理工具還有一個處理多行的選項。如果選中了這個選項，和$的意義就變成了匹配行的開始處和結束處。.字符轉義如果你想查找元字符本身的話，比如你查找.,或者*,就出現(xiàn)了問題：你沒辦法指定它們，因為它們會被解釋成別的意思。這時你就得使用來取消這些字符的特殊意義。因此，你應該使用.和*。當然，要查找本身，你也得用.例如：匹配，C:Windows匹配C:Windows。.重復你已經(jīng)看過了前面的*,+,2,5,12這幾個匹配重復的方式了。下面是正則表達式中所有的限定符(指定數(shù)量的代碼，例如*,5,12等)：例子：Windowsd+匹配Windows后面跟1個或更多數(shù)字w+匹配

9、一行的第一個單詞(或整個字符串的第一個單詞，具體匹配哪個意思得看選項設置).表2.常用的限定符 代碼/語法說明*重復零次或更多次+重復一次或更多次?重復零次或一次n重復n次n,重復n次或更多次n,m重復n到m次 .字符類要想查找數(shù)字，字母或數(shù)字，空白是很簡單的，因為已經(jīng)有了對應這些字符集合的元字符，但是如果你想匹配沒有預定義元字符的字符集合(比如元音字母a,e,i,o,u),應該怎么辦？很簡單，你只需要在方括號里列出它們就行了，像aeiou就匹配任何一個英文元音字母，.?!匹配標點符號(.或?或!)。我們也可以輕松地指定一個字符范圍，像0-9代表的含意與d就是完全一致的：一位數(shù)字；同理a-z0

10、-9A-Z_也完全等同于w（如果只考慮英文的話）。.下面是一個更復雜的表達式：(?0d2) -?d8?！?”和“)”也是元字符，后面的分組節(jié)里會提到，所以在這里需要使用轉義。這個表達式可以匹配幾種格式的電話號碼，像(010)88886666，或02912345678等。我們對它進行一些分析吧：首先是一個轉義字符(,它能出現(xiàn)0次或1次(?),然后是一個0，后面跟著2個數(shù)字(d2)，然后是)或-或空格中的一個，它出現(xiàn)1次或不出現(xiàn)(?)，最后是8個數(shù)字(d8)。.分枝條件剛才那個表達式也能匹配010)12345678或樣的“不正確”的格式。要解

11、決這個問題，我們需要用到分枝條件。正則表達式里的分枝條件指的是有幾種規(guī)則，如果滿足其中任意一種規(guī)則都應該當成匹配，具體方法是用|把不同的規(guī)則分隔開。聽不明白？沒關系，看例子：0d2-d8|0d3-d7這個表達式能匹配兩種以連字號分隔的電話號碼：一種是三位區(qū)號，8位本地號(，一種是4位區(qū)號，7位本地號。.(?0d2)?- ?d8|0d2- ?d8這個表達式匹配3位區(qū)號的電話號碼，其中區(qū)號可以用小括號括起來，也可以不用，區(qū)號與本地號間可以用連字號或空格間隔，也可以沒有間隔。你可以試試用分枝條件把這個表達式擴展成也支持4位區(qū)號的。.d5-d4|

12、d5這個表達式用于匹配美國的郵政編碼。美國郵編的規(guī)則是5位數(shù)字，或者用連字號間隔的9位數(shù)字。之所以要給出這個例子是因為它能說明一個問題：使用分枝條件時，要注意各個條件的順序。如果你把它改成d5|d5-d4的話，那么就只會匹配5位的郵編(以及9位郵編的前5位)。原因是匹配分枝條件時，將會從左到右地測試每個條件，如果滿足了某個分枝的話，就不會去再管其它的條件了。.分組我們已經(jīng)提到了怎么重復單個字符（直接在字符后面加上限定符就行了）；但如果想要重復多個字符又該怎么辦？你可以用小括號來指定子表達式(也叫做分組)，然后你就可以指定這個子表達式的重復次數(shù)了，你也可以對子表達式進行其它一些操作(后面會有介紹

13、)。(d1,3.)3d1,3是一個簡單的IP地址匹配表達式。要理解這個表達式，請按下列順序分析它：d1,3匹配1到3位的數(shù)字，(d1,3.)3匹配三位數(shù)字加上一個英文句號(這個整體也就是這個分組)重復3次，最后再加上一個一到三位的數(shù)字(d1,3)。IP地址中每個數(shù)字都不能大于255，大家千萬不要被24第三季的編劇給忽悠了.不幸的是，它也將匹配256.300.888.999這種不可能存在的IP地址。如果能使用算術比較的話，或許能簡單地解決這個問題，但是正則表達式中并不提供關于數(shù)學的任何功能，所以只能使用冗長的分組，選擇，字符類來描述一個正確的IP地址：(20-4d|250-5|01?dd?).)

14、3(20-4d|250-5|01?dd?)。理解這個表達式的關鍵是理解20-4d|250-5|01?dd?，這里我就不細說了，你自己應該能分析得出來它的意義。.反義有時需要查找不屬于某個能簡單定義的字符類的字符。比如想查找除了數(shù)字以外，其它任意字符都行的情況，這時需要用到反義：例子：S+匹配不包含空白符的字符串。+匹配用尖括號括起來的以a開頭的字符串。.表3.常用的反義代碼代碼/語法說明W匹配任意不是字母，數(shù)字，下劃線，漢字的字符S匹配任意不是空白符的字符D匹配任意非數(shù)字的字符B匹配不是單詞開頭或結束的位置x匹配除了x以外的任意字符aeiou匹配除了aeiou這幾個字母以外的任意字符.后向引用

15、(I)使用小括號指定一個子表達式后，匹配這個子表達式的文本(也就是此分組捕獲的內容)可以在表達式或其它程序中作進一步的處理。默認情況下，每個分組會自動擁有一個組號，規(guī)則是：從左向右，以分組的左括號為標志，第一個出現(xiàn)的分組的組號為1，第二個為2，以此類推。呃其實,組號分配還不像我剛說得那么簡單：.分組0對應整個正則表達式 實際上組號分配過程是要從左向右掃描兩遍的：第一遍只給未命名組分配，第二遍只給命名組分配因此所有命名組的組號都大于未命名的組號 你可以使用(?:exp)這樣的語法來剝奪一個分組對組號分配的參與權 .后向引用用于重復搜索前面某個分組匹配的文本。例如，1代表分組1匹配的文本。難以理解

16、？請看示例：b(w+)bs+1b可以用來匹配重復的單詞，像go go, 或者kitty kitty。這個表達式首先是一個單詞，也就是單詞開始處和結束處之間的多于一個的字母或數(shù)字(b(w+)b)，這個單詞會被捕獲到編號為1的分組中，然后是1個或幾個空白符(s+)，最后是分組1中捕獲的內容（也就是前面匹配的那個單詞）(1)。.你也可以自己指定子表達式的組名。要指定一個子表達式的組名，請使用這樣的語法：(?w+)(或者把尖括號換成也行：(?Wordw+),這樣就把w+的組名指定為Word了。要反向引用這個分組捕獲的內容，你可以使用k,所以上一個例子也可以寫成這樣：b(?w+)bs+kb。使用小括號的

17、時候，還有很多特定用途的語法。下面列出了最常用的一些：.表4.常用分組語法 分類代碼/語法說明捕獲(exp)匹配exp,并捕獲文本到自動命名的組里(?exp)匹配exp,并捕獲文本到名稱為name的組里，也可以寫成(?nameexp)(?:exp)匹配exp,不捕獲匹配的文本，也不給此分組分配組號.零寬斷言(?=exp)匹配exp前面的位置(?=exp)匹配exp后面的位置(?!exp)匹配后面跟的不是exp的位置(?!exp)匹配前面不是exp的位置注釋(?#comment)這種類型的分組不對正則表達式的處理產(chǎn)生任何影響，用于提供注釋讓人閱讀 .零寬斷言接下來的四個用于查找在某些內容(但并不

18、包括這些內容)之前或之后的東西，也就是說它們像b,$那樣用于指定一個位置，這個位置應該滿足一定的條件(即斷言)，因此它們也被稱為零寬斷言。最好還是拿例子來說明吧：斷言用來聲明一個應該為真的事實。正則表達式中只有當斷言為真時才會繼續(xù)進行匹配。.(?=exp)也叫零寬度正預測先行斷言，它斷言自身出現(xiàn)的位置的后面能匹配表達式exp。比如bw+(?=ingb)，匹配以ing結尾的單詞的前面部分(除了ing以外的部分)，如查找Im singing while youre dancing.時，它會匹配sing和danc。(?=exp)也叫零寬度正回顧后發(fā)斷言，它斷言自身出現(xiàn)的位置的前面能匹配表達式exp。

19、比如(?=bre)w+b會匹配以re開頭的單詞的后半部分(除了re以外的部分)，例如在查找reading a book時，它匹配ading。.假如你想要給一個很長的數(shù)字中每三位間加一個逗號(當然是從右邊加起了)，你可以這樣查找需要在前面和里面添加逗號的部分：(?=d)d3)+b，用它對1234567890進行查找時結果是234567890。下面這個例子同時使用了這兩種斷言：(?=s)d+(?=s)匹配以空白符間隔的數(shù)字(再次強調，不包括這些空白符)。.負向零寬斷言前面我們提到過怎么查找不是某個字符或不在某個字符類里的字符的方法(反義)。但是如果我們只是想要確保某個字符沒有出現(xiàn)，但并不想去匹配它

20、時怎么辦？例如，如果我們想查找這樣的單詞-它里面出現(xiàn)了字母q,但是q后面跟的不是字母u,我們可以嘗試這樣：.bw*quw*b匹配包含后面不是字母u的字母q的單詞。但是如果多做測試(或者你思維足夠敏銳，直接就觀察出來了)，你會發(fā)現(xiàn)，如果q出現(xiàn)在單詞的結尾的話，像Iraq,Benq，這個表達式就會出錯。這是因為u總要匹配一個字符，所以如果q是單詞的最后一個字符的話，后面的u將會匹配q后面的單詞分隔符(可能是空格，或者是句號或其它的什么)，后面的w*b將會匹配下一個單詞，于是bw*quw*b就能匹配整個Iraq fighting。負向零寬斷言能解決這樣的問題，因為它只匹配一個位置，并不消費任何字符。

21、現(xiàn)在，我們可以這樣來解決這個問題：bw*q(?!u)w*b。.零寬度負預測先行斷言(?!exp)，斷言此位置的后面不能匹配表達式exp。例如：d3(?!d)匹配三位數(shù)字，而且這三位數(shù)字的后面不能是數(shù)字；b(?!abc)w)+b匹配不包含連續(xù)字符串a(chǎn)bc的單詞。同理，我們可以用(?!exp),零寬度負回顧后發(fā)斷言來斷言此位置的前面不能匹配表達式exp：(?!a-z)d7匹配前面不是小寫字母的七位數(shù)字。.請詳細分析表達式(?=).*(?=)，這個表達式最能表現(xiàn)零寬斷言的真正用途。一個更復雜的例子：(?=).*(?=)匹配不包含屬性的簡單HTML標簽內里的內容。(?=)指定了這樣的前綴：被尖括號括起

22、來的單詞(比如可能是)，然后是.*(任意的字符串),最后是一個后綴(?=)。注意后綴里的/，它用到了前面提過的字符轉義；1則是一個反向引用，引用的正是捕獲的第一組，前面的(w+)匹配的內容，這樣如果前綴實際上是的話，后綴就是了。整個表達式匹配的是和之間的內容(再次提醒，不包括前綴和后綴本身)。.注釋小括號的另一種用途是通過語法(?#comment)來包含注釋。例如：20-4d(?#200-249)|250-5(?#250-255)|01?dd?(?#0-199)。要包含注釋的話，最好是啟用“忽略模式里的空白符”選項，這樣在編寫表達式時能任意的添加空格，Tab，換行，而實際使用時這些都將被忽略。

23、啟用這個選項后，在#后面到這一行結束的所有文本都將被當成注釋忽略掉。例如，我們可以前面的一個表達式寫成這樣：.(?= # 斷言要匹配的文本的前綴 # 查找尖括號括起來的字母或數(shù)字(即HTML/XML標簽) ) # 前綴結束 .* # 匹配任意文本 (?= # 斷言要匹配的文本的后綴 # 查找尖括號括起來的內容：前面是一個/，后面是先前捕獲的標簽 ) # 后綴結束 .貪婪與懶惰當正則表達式中包含能接受重復的限定符時，通常的行為是（在使整個表達式能得到匹配的前提下）匹配盡可能多的字符。以這個表達式為例：a.*b，它將會匹配最長的以a開始，以b結束的字符串。如果用它來搜索aabab的話，它會匹配整個

24、字符串a(chǎn)abab。這被稱為貪婪匹配。有時，我們更需要懶惰匹配，也就是匹配盡可能少的字符。前面給出的限定符都可以被轉化為懶惰匹配模式，只要在它后面加上一個問號?。這樣.*?就意味著匹配任意數(shù)量的重復，但是在能使整個匹配成功的前提下使用最少的重復?，F(xiàn)在看看懶惰版的例子吧：.a.*?b匹配最短的，以a開始，以b結束的字符串。如果把它應用于aabab的話，它會匹配aab（第一到第三個字符）和ab（第四到第五個字符）。.表5.懶惰限定符 代碼/語法說明*?重復任意次，但盡可能少重復+?重復1次或更多次，但盡可能少重復?重復0次或1次，但盡可能少重復n,m?重復n到m次，但盡可能少重復n,?重復n次以上，

25、但盡可能少重復 .處理選項表常用的處理選項 名稱說明IgnoreCase(忽略大小寫)匹配時不區(qū)分大小寫。Multiline(多行模式)更改和$的含義，使它們分別在任意一行的行首和行尾匹配，而不僅僅在整個字符串的開頭和結尾匹配。(在此模式下,$的精確含意是:匹配n之前的位置以及字符串結束前的位置.).Singleline(單行模式)更改.的含義，使它與每一個字符匹配（包括換行符n）。IgnorePatternWhitespace(忽略空白)忽略表達式中的非轉義空白并啟用由#標記的注釋。ExplicitCapture(顯式捕獲)僅捕獲已被顯式命名的組。 .平衡組/遞歸匹配有時我們需要匹配像( 1

26、00 * ( 50 + 15 ) )這樣的可嵌套的層次性結構，這時簡單地使用(.+)則只會匹配到最左邊的左括號和最右邊的右括號之間的內容(這里我們討論的是貪婪模式，懶惰模式也有下面的問題)。假如原來的字符串里的左括號和右括號出現(xiàn)的次數(shù)不相等，比如( 5 / ( 3 + 2 ) ) )，那我們的匹配結果里兩者的個數(shù)也不會相等。有沒有辦法在這樣的字符串里匹配到最長的，配對的括號之間的內容呢？為了避免(和(把你的大腦徹底搞糊涂，我們還是用尖括號代替圓括號吧。現(xiàn)在我們的問題變成了如何把xx aa aa yy這樣的字符串里，最長的配對的尖括號內的內容捕獲出來？.這里需要用到以下的語法構造：(?group

27、) 把捕獲的內容命名為group,并壓入堆棧(Stack) (?-group) 從堆棧上彈出最后壓入堆棧的名為group的捕獲內容，如果堆棧本來為空，則本分組的匹配失敗 (?(group)yes|no) 如果堆棧上存在以名為group的捕獲內容的話，繼續(xù)匹配yes部分的表達式，否則繼續(xù)匹配no部分 (?!) 零寬負向先行斷言，由于沒有后綴表達式，試圖匹配總是失敗.我們需要做的是每碰到了左括號，就在壓入一個Open,每碰到一個右括號，就彈出一個，到了最后就看看堆棧是否為空如果不為空那就證明左括號比右括號多，那匹配就應該失敗。正則表達式引擎會進行回溯(放棄最前面或最后面的一些字符)，盡量使整個表達式得到匹配。. #最外層的左括號 * #最外層的左括號后面的不是括號的內容 ( ( (?Open) #碰到了左括號，在黑板上寫一個Open * #匹配左括號后面的不是括號的內容 )+ ( (?-Open) #碰到了右括號，擦