如何使用Prolog在兩個字符之間找到子字符串？

我有一個變量被傳遞給一個謂詞，它是一個字符串列表。如何使用Prolog在兩個字符之間找到子字符串？

從列表中的每個字符串我想提取最深的一組括號之間的子字符串，並創建所有這些子字符串的列表。

例如：

輸入：

["Canidae(Canis(C. lupus(C. l. familiaris)))", "Felidae(Felinae(Felis(F. catus)))", "Equidae(Equus(E. ferus(E. f. caballus)))"]

輸出繼電器：

["C. l. familiaris", "F. catus", "E. f. caballus"]

（我已經使用生物分類位列作爲一個例子，因爲它們是相似在結構上我的實際數據a）

最後，每組圓括號的深度是未知的，最深的子字符串始終是開括號和閉括號之間唯一的子字符串。

感謝您的幫助，我對Prolog很陌生，所以思維方式有些不同。我一直試圖解決這個問題一段時間，但我無法解決這個問題。

來源

2016-04-27 Josh

這功課嗎？你允許使用內建的謂詞嗎？ –

這不是家庭作業，我開始在大學學習Prolog，並且在一個我不知道如何解決的演講中提出了類似的問題。我可以使用內置的謂詞。我假設它涉及通過每個字符串遞歸，找到最深圓括號的索引並使用內置子字符串謂詞來查找最深圓括號之間的子字符串。我只是不知道如何通過每個字符串遞歸來查找括號，然後建立一個新的列表。謝謝。 – Josh

而不是解決列表的問題，我們最好先解決單個字符串的問題。爲了計算最深的子字符串，我們可以 - 如果我正確理解了規範 - 計算最後一個左括號的位置。我們將假設您已將字符串轉換爲ASCII碼列表，例如使用string_codes/2。在這裏，開括號有代碼40：

last_opening(L,X) :- 
    last_opening(L,0,0,X). 

last_opening([],J,_,J). 
last_opening([40|T],_,I,X) :- 
    !, 
    I1 is I+1, 
    last_opening(T,I1,I1,X). 
last_opening([_|T],J,I,X) :- 
    I1 is I+1, 
    last_opening(T,J,I1,X).

例如，對於您的第一個例子：

?- string_codes("Canidae(Canis(C. lupus(C. l. familiaris)))",L),last_opening(L,X). 
L = [67, 97, 110, 105, 100, 97, 101, 40, 67|...], 
X = 23.

它說，我們要開始從23位置提取：

Canidae(Canis(C. lupus(C. l. familiaris))) 
        ^here

一旦我們知道最深的子字符串開始的位置，我們可以簡單地提取字符串：我們必須停止在列表的末尾，或者在代碼41，無論是第一位的：

extract_substring(L,0,S) :- 
    !, 
    extract_substring2(L,S). 
extract_substring([_|T],N,S) :- 
    N1 is N-1, 
    extract_substring(T,N1,S). 

extract_substring2([],[]). 
extract_substring2([41|_],[]) :- 
    !. 
extract_substring2([L|T],[L|U]) :- 
    extract_substring2(T,U).

例如：

?- string_codes("Canidae(Canis(C. lupus(C. l. familiaris)))",L),last_opening(L,X),extract_substring(L,X,T),string_codes(St,T). 
L = [67, 97, 110, 105, 100, 97, 101, 40, 67|...], 
X = 23, 
T = [67, 46, 32, 108, 46, 32, 102, 97, 109|...], 
St = "C. l. familiaris".

現在我們可以寫一個謂語，做的string_codes調用自動：

deepest_string(S,T) :- 
    string_codes(S,CS), 
    last_opening(CS,X), 
    extract_substring(CS,X,CT), 
    string_codes(T,CT).

例如：

?- deepest_string("Canidae(Canis(C. lupus(C. l. familiaris)))",L). 
L = "C. l. familiaris".

總之，我們只有實現了列表功能：

deepest_string_list([],[]). 
deepest_string_list([S|ST],[T|TT]) :- 
    deepest_string(S,T), 
    deepest_string_list(ST,TT).

導致：

?- deepest_string_list(["Canidae(Canis(C. lupus(C. l. familiaris)))", "Felidae(Felinae(Felis(F. catus)))", "Equidae(Equus(E. ferus(E. f. caballus)))"],T). 
T = ["C. l. familiaris", "F. catus", "E. f. caballus"].

如果你想改變的字符，你可以簡單地查找它們的ASCII等價物，並將其替換爲40和41。

來源

2016-04-27 18:14:09

這正是我想要的。感謝您的解決方案，並再次感謝您及時徹底解釋每一步。謝謝！ – Josh

我建議一個DCG和的findAll/3：

par(L, Content, R) --> 
    left(L), inner(L, Content, R). 

left(P) --> P. 
left(P) --> [_], left(P). 

inner(_, [], R) --> R. 
inner(L, [C|Cs], R) --> 
    \+ L, \+ R, [C], inner(L, Cs, R). 

?- findall(A,(phrase(par("[",C,"]"),`[a[b][cd]]e`,_),atom_codes(A,C)),L). 
L = [b, cd].

注意短語/ 3的_作爲最後一個參數。它通過findall/3啓用列表構建。

您可以使用任何字符串作爲左/右括號。

來源

2016-04-27 21:38:16 CapelliC

構建語法並使用它的解析器確實是解決此問題的好方法。 +1 :) –

我還沒有在Prolog中使用過DCG。我會在今天晚些時候看看它們，然後嘗試這個解決方案。感謝您的貢獻:) – Josh

如何使用Prolog在兩個字符之間找到子字符串？

回答

相關問題