代码之家 › 专栏 › 技术社区 › Josh

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

swi-prolog prolog list string

Josh · 技术社区 · 8 年前

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

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

例如:

输入:

["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的新手,所以思维方式有点不同。我一直在想办法解决这个问题,但我解决不了。

2 回复 | 直到 8 年前

CapelliC 8 年前

我建议使用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建立列表。

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

willeM_ Van Onsem 8 年前

我们最好先解决单个字符串的问题,而不是解决列表的问题。为了计算最深的子串,如果我正确理解了规范,我们可以计算最后一个左括号的位置。我们将假设您已经使用例如将字符串转换为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 .