Java String.replaceAll() 與後向引用(backreference)

問題

昨天看到一篇博文，文中談到一道 Java 面試題：

給定一字元串，若該字元串中間包含 "*"，則刪除該 "*"；若該字元串首字元或尾字元為 "*"，則保留該 "*"。

舉幾個例子（箭頭左邊為輸入，箭頭右邊為輸出）：

* --> *

** --> **

**** --> **

*ab**de** --> *abde*

我覺得應該用正則表達式來處理，但想不出正則表達式該怎麼寫。

第一種解答

該博文的回覆中有人給出下麵的答案：

str.replaceAll("(^\\*)|(\\*$)|\\*", "$1$2");

上機驗證一下，答案是對的，但不懂為什麼正則表達式要這麼寫。到 stackoverflow 上發帖問了一下，才大概明白是怎麼回事兒。當時問的時候， 對這個問題想得不清楚，所以問的問題也是糊裡糊塗。

下麵是我的理解，不對之處請多拍磚：

replaceAll() 是 Java String 類的一個方法：

public String replaceAll(String regex, String replacement)

Replaces each substring of this string that matches the given regular expression with the given replacement.

（特別要註意的是，這個方法的第一個參數是一個正則表達式。我過去在第一個參數上栽過跟頭。不過，這回我栽在第二個參數上。）

"(^\\*)|(\\*$)|\\*" 解釋： 

(^\\*) ：capturing group 1, 匹配字元串開始處的 *
(\\*$) ：capturing group 2, 匹配字元串結尾處的 *
\\* ： 匹配任意位置的 *

• 因為 "*" 在正則表達式中是特殊字元，所以需要使用轉義字元 "\"。但在Java中 "\" 也是特殊字元，所以需要再一次使用 "\"，這樣就造成 "*" 前面有兩個 "\"。
• 圓括弧 "()" 把括弧內的內容作為一個 capturing group，為後面的 backreference 做準備。關於 capturing group 請看這裡。
• "|" 表明左右的表達式是 "或" 的關係。
• "\\*" 單獨使用的話可以匹配字元串中任意位置的 "*"。但在上述的表達式中，開始和結尾處的 "*" 優先被 "(^\\*)" 或 "(\\*$)" 匹配了。

"$1$2" 解釋：

$1 ：backreference 第一個 capturing group
$2 ：backreference 第二個 capturing group

這個參數中 "$1" 和 "$2" 的內容被用來替換前一個參數中匹配的字元串。

以字元串 "*ab**de**" 為例： 

1. 第一個 "*" 匹配，使用 "$1$2" 來替換。這時 "$1" 的內容為 "*"，"$2" 的內容為空，所以第一個 "*"  被它自己替換。

2. 接下來 "a" 和 "b" 都不匹配，略過，繼續往後走。

3. 第二個 "*" 匹配，使用 "$1$2" 來替換。這時 "$1" 的內容為空，"$2" 的內容為空，所以這個 "*" 被替換為空。

4. 第三個 "*" 跟第二個 "*" 一樣，也被替換為空。

5. 接下來的 "d" 和 "e" 不匹配，繼續往後走。

6. 第四個 "*" 匹配，跟第二個、第三個 "*" 一樣，被替換為空。

7. 最後一個 "*" 匹配，使用 "$1$2" 來替換。這時 "$1" 的內容為空，"$2" 的內容為 "*"，所以最後一個 "*" 被它自己替換。

8. 最後的結果是："*abde*" 

這裡有一點要註意：在正則表達式中，backreference 是用 "反斜杠 + 數字" 來表示的，比如：\1, \2 。但是，當 backreference 出現在替換字元串中時，Java 的 backreference 使用 "美元符號 + 數字" 來表示，比如：$1, $2 。據說這是跟 Perl 學的。不嫌累的話看看這個帖子吧。

第二種解答

String repl = str.replaceAll("(?<!^)\\*+(?!$)", "");

正則表達式解釋：

(?<!^)   # 如果前一個位置不是行首
\\*+     # 匹配一個或多個 *
(?!$)    # 如果下一個位置不是行尾

"?<!" 表示 Negative Lookahead，"?!" 表示 Negative Lookbehind 。詳細說明請參考這裡和這裡。

第三種解答

String repl = str.replaceAll("(^\\*)|(\\*$)|\\*+", "$1$2");

這個跟上面的第二種解答都是由同一個人回覆的，但這個解答有點問題：如果結尾處有兩個或兩個以上的 "*" 時，這些 "*" 都被替換為空。

例如，若輸入為 "*ab**de**"，則輸出為"*abde"，最後的那個 "*" 不見了。

這是因為預設情況下，正則匹配處於 Greediness(貪婪) 匹配模式，會匹配儘量多的字元。"\*+" 可以匹配一個或多個 "*" 。在倒數第二個 "*" 的時候，匹配一個 "*" 或兩個 "*" 都可以。但它比較貪婪，所以把最後兩個 "*" 都匹配上了，然後被 "$1$2" 替換為空。

把正則匹配改為 Laziness(偷懶)匹配可以解決這個問題。在表達式後面加一個 "?" 就變成 Laziness 匹配了："\*+?" 。

String repl = str.replaceAll("(^\\*)|(\\*$)|\\*+?", "$1$2");

關於 Greediness 和 Laziness 請看這裡。

正則表達式效率

該網站可以測試正則表達式，並給出詳細的解釋。它還給出匹配所需的步數，你可以用這個步數來比較表達式的效率。從這個網站上看，第二種方法效率最高。

參考鏈接

• 華為機試題——該警醒了，騷年
• Lookahead and Lookbehind Zero-Length Assertions
• Java String.replaceAll() with back reference
• Backreferences Syntax in Replacement Strings (Why Dollar Sign?)
• Java Docs on java.lang.String.replaceAll()
• Regular Expressions 101
• Capturing Groups

• 正則表達式30分鐘入門教程 （強烈推薦）