如何匹配正則表達式與包含通配符的字符串？

正則表達式：如何匹配正則表達式與包含通配符的字符串？

/Hello .*, what's up?/i

字符串，可以包含任意數量的通配符（％）：

"% world, what's up?" (matches) 
"Hello world, %?"  (matches) 
"Hello %, what's up?" (matches) 
"Hey world, what's up?" (no match) 
"Hello %, blabla."  (no match)

我以爲解決我自己的，但我想看看你是什麼能夠拿出（考慮到性能是一個高優先級）。的要求是使用任何正則表達式的能力;在這個例子中，我只使用.*，但任何有效的正則表達式都可以使用。

來源

2014-01-10 Yeti

如果有偏見，你可能不會想到出來的箱子了。我希望你想出一個完全不同的東西，而不是改進我的解決方案。最重要的是，解決方案遠非最佳，如果我對它感到滿意，我就不會問你了。 – Yeti

目前，第一和第二個字符串不應該匹配您的正則表達式。 – zessx

@zessx當然他們不是，訣竅是用「Hello」替換第一個字符串中的％。但是，這樣的算法會是怎樣的呢？或者另一種方法是編輯正則表達式本身，然後嘗試匹配它。 – Yeti

有點自動機理論可以幫助你在這裏。你說

這是用正則表達式匹配^{正則表達式的簡化版本[1]}

事實上，這似乎並不如此。您不希望匹配正則表達式的文本，而是希望找到可以與給定的正則表達式匹配相同字符串的正則表達式。

幸運的是，這個問題是可以解決的:-)要查看這樣的字符串是否存在，您需要計算union of the two regular languages並測試結果是否不是空語言。這可能是一個不平凡的問題，並且有效地解決這個問題可能很困難，但是對此的標準算法已經存在。基本上你將需要翻譯的表達成NFA，一個into一個DFA然後你可以union。

_{[1]：事實上，你正在使用中的問題通配符字符串建立某種正規的語言，並且可以轉化爲相應的正則表達式}

來源

2014-01-10 15:03:25 Bergi

所以基本上你建議我應該試着找出一個字符串X，它是由'Hello。*，怎麼了'和'％world匹配的，這是怎麼回事？如果我無法找到這樣的字符串，那麼它是不匹配的。如果我找到這樣的字符串，那麼它是一個匹配。有趣的一點，我會考慮它:) :) – Yeti

是的，這就是你的匹配標準聽起來像 - 你想從列表中找到匹配你的正則表達式的通配符字符串。 – Bergi

不知道我完全理解你的問題，但如果你正在尋找的性能，避免正則表達式。相反，您可以將字符串拆分爲%。然後，看看第一個和最後一個比賽：

// Anything before % should match at start of the string 
targetString.indexOf(splits[0]) === 0; 

// Anything after % should match at the end of the string 
targetString.indexOf(splits[1]) + splits[1].length === targetString.length;

如果你可以在字符串中使用%多次，那麼第一個和最後一個splits應遵循上述規則。其他任何東西只需要在字符串中，.indexOf是你如何檢查。

來源

2014-01-10 13:47:30

對不起，但這個問題不是小事！實際上，這是將正則表達式與正則表達式匹配的簡化版本。問題的標題應該足夠清楚。 – Yeti

我意識到用普通語言來說這是不可能的，因此解決此問題的唯一方法是用通配符%替換.*，然後將兩個正則表達式相互匹配。這可以但不是由傳統的正則表達式完成，看this SO-question and it's answers for details.

或許你應該修改爲支持基於通配符字符串的基本正則表達式引擎。任何人都能夠通過擴展默認實現來回答這個問題會被接受爲這個問題的答案;-)

來源

2014-01-10 14:49:19 Yeti

如何匹配正則表達式與包含通配符的字符串？

回答

相關問題