平衡組/遞歸匹配

平衡組/遞歸匹配

有時我們需要匹配像( 100 * ( 50 + 15 ) )這樣的可嵌套的層次性結(jié)構(gòu)，這時簡單地使用\(.+\)則只會匹配到最左邊的左括號和最右邊的右括號之間的內(nèi)容(這里我們討論的是貪婪模式，懶惰模式也有下面的問題)。假如原來的字符串里的左括號和右括號出現(xiàn)的次數(shù)不相等，比如( 5 / ( 3 + 2 ) ) )，那我們的匹配結(jié)果里兩者的個數(shù)也不會相等。有沒有辦法在這樣的字符串里匹配到最長的，配對的括號之間的內(nèi)容呢？

為了避免(和\(把你的大腦徹底搞糊涂，我們還是用尖括號代替圓括號吧?，F(xiàn)在我們的問題變成了如何把xx <aa aa> yy這樣的字符串里，最長的配對的尖括號內(nèi)的內(nèi)容捕獲出來？

這里需要用到以下的語法構(gòu)造：

• (?'group') 把捕獲的內(nèi)容命名為 group,并壓入堆棧(Stack)
• (?'-group') 從堆棧上彈出最后壓入堆棧的名為 group 的捕獲內(nèi)容，如果堆棧本來為空，則本分組的匹配失敗
• (?(group)yes|no) 如果堆棧上存在以名為 group 的捕獲內(nèi)容的話，繼續(xù)匹配 yes 部分的表達(dá)式，否則繼續(xù)匹配no部分
• (?!) 零寬負(fù)向先行斷言，由于沒有后綴表達(dá)式，試圖匹配總是失敗

我們需要做的是每碰到了左括號，就在壓入一個"Open",每碰到一個右括號，就彈出一個，到了最后就看看堆棧是否為空－－如果不為空那就證明左括號比右括號多，那匹配就應(yīng)該失敗。正則表達(dá)式引擎會進(jìn)行回溯(放棄最前面或最后面的一些字符)，盡量使整個表達(dá)式得到匹配。

<                         #最外層的左括號
    [^<>]*                #最外層的左括號后面的不是括號的內(nèi)容
    (
        (
            (?'Open'<)    #碰到了左括號，在黑板上寫一個"Open"
            [^<>]*       #匹配左括號后面的不是括號的內(nèi)容
        )+
        (
            (?'-Open'>)   #碰到了右括號，擦掉一個"Open"
            [^<>]*        #匹配右括號后面不是括號的內(nèi)容
        )+
    )*
    (?(Open)(?!))         #在遇到最外層的右括號前面，判斷黑板上還有沒有沒擦掉的"Open"；如果還有，則匹配失敗

>                         #最外層的右括號

平衡組的一個最常見的應(yīng)用就是匹配 HTML,下面這個例子可以匹配嵌套的