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

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

問題

昨天看到一篇博文，文中談到一道 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**" 為例：

 

 

這裡有一點要注意：在正則表達式中，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分鐘入門教程 （強烈推薦）