以編程方式查找字符串到正則表達式？

Question

給定一個正則表達式，是否可以通過編程找到與該表達式匹配的字符串？如果是這樣，請提及一個算法，假設一個字符串存在。

紅利問題：如果能夠，給出該算法的性能/複雜性。

---

PS：注意我不是問這個：Programmatically derive a regular expression from a string。更可能是我問保留區問題。

Answer 1

假設你像這樣定義的正則表達式：

R := 
    <literal string> 
    (RR) -- concatenation 
    (R*) -- kleene star 
    (R|R) -- choice 

然後，你可以定義一個遞歸函數S(r)它找到一個匹配的字符串：

S(<literal string>) = <literal string> 
S(rs) = S(r) + S(s) 
S(r*) = "" 
S(r|s) = S(r) 

例如：S(a*(b|c)) = S(a*) + S(b|c) = "" + S(b) = "" + "b" = "b"。

如果你有一個更復雜的正則表達式概念，你可以用基本原語重寫它，然後應用上面的。例如，R+ = RR*和[abc] = (a|b|c)。

請注意，如果你有一個經過解析的正則表達式（因此你知道它的語法樹），那麼上面的算法在正則表達式的大小中最多需要線性時間（假設你小心地執行字符串有效連接）。

Answer 2

可能是這個環節是幫助全給你： http://www.geeksforgeeks.org/wildcard-character-matching/

http://wiki.tcl.tk/989

Answer 3

Generex是一個Java庫從正則表達式生成的字符串。

檢查出來：https://github.com/mifmif/Generex

下面是Java代碼示例，演示庫的使用：

Generex generex = new Generex("[0-3]([a-c]|[e-g]{1,2})"); 

// Generate random String 
String randomStr = generex.random(); 
System.out.println(randomStr);// a random value from the previous String list 

// generate the second String in lexicographical order that match the given Regex. 
String secondString = generex.getMatchedString(2); 
System.out.println(secondString);// it print '0b' 

// Generate all String that matches the given Regex. 
List<String> matchedStrs = generex.getAllMatchedStrings(); 

// Using Generex iterator 
Iterator iterator = generex.iterator(); 
while (iterator.hasNext()) { 
    System.out.print(iterator.next() + " "); 
} 
// it prints: 
// 0a 0b 0c 0e 0ee 0ef 0eg 0f 0fe 0ff 0fg 0g 0ge 0gf 0gg 
// 1a 1b 1c 1e 1ee 1ef 1eg 1f 1fe 1ff 1fg 1g 1ge 1gf 1gg 
// 2a 2b 2c 2e 2ee 2ef 2eg 2f 2fe 2ff 2fg 2g 2ge 2gf 2gg 
// 3a 3b 3c 3e 3ee 3ef 3eg 3f 3fe 3ff 3fg 3g 3ge 3gf 3gg 

---

還有一句：https://code.google.com/archive/p/xeger/

下面是Java代碼示例，演示庫的使用：

String regex = "[ab]{4,6}c"; 
Xeger generator = new Xeger(regex); 
String result = generator.generate(); 
assert result.matches(regex); 

Answer 4

爲了找到符合該條件的字符串中的給定表達式，爲此我曾嘗試過下面的算法。

i) Create the array for all strings available in given source. 

ii) Create a function with parameters for array, expression and initial index count. 

iii) Call function recursively and increase the index with every move, until we match string has not found. 

iv) Return/break the function if String with desired expression is found. 

下面是相同的Java代碼：

public class ExpressionAlgo { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     String data = "A quantifier defines how often an element can occur. The symbols ?, *, + and {} define the quantity of the regular expressions"; 
     regCheck(data.split(" "), "sym", 0); 
    } 

    public static void regCheck(String[] ar, String expresion, int i) { 
       if(ar[i].contains(expresion)){ 
        System.out.println(ar[i]); 
        return; 
       } 

       if(i<ar.length-1){ 
        i=i+1; 
        regCheck(ar, expresion, i); 
       } 
    } 
} 

據我計算出的該代碼的複雜性爲N^3，因爲我有使用分裂，包含方法和遞歸調用regCheck方法。