如何使用 Prolog 查找两个字符之间的子字符串？

Question

我有一个变量被传递给一个字符串列表的谓词。

我想从列表中的每个字符串中提取最深的一组括号之间的子字符串，并创建所有这些子字符串的列表。

例如：

输入：

["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"]

（我以生物分类排名为例，因为它们在结构上与我的实际数据相似）

最后，每组括号的深度是未知的，最深的子字符串始终是左括号和右括号之间的唯一子字符串。

感谢您对此的帮助，我是 Prolog 的新手，所以思维方式有点不同。一段时间以来，我一直在努力解决这个问题，但我无法解决。

Answer 1

我们最好先解决单个字符串的问题，而不是解决列表的问题。为了计算最深的子串，我们可以——如果我理解正确的话——计算最后一个左括号的位置。我们假设您已经使用 string_codes/2 将字符串转换为 ASCII 代码列表。这里左括号有代码 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。

Answer 2

我建议使用 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].

注意 _ 作为 phrase/3 的最后一个参数。它支持 findall/3.

列表构建

您可以使用任何字符串作为 left/right 括号。

如何使用 Prolog 查找两个字符之间的子字符串？

How do I find a substring between two characters using Prolog?

string

list

prolog

swi-prolog