1

我想在以下考试问题中获得一些帮助，我不知道该怎么做：

输入：一个数字列表，例如：[1,2,3,4] 输出：所有可能的正确括号。例如：（在输入的情况下[1,2,3,4]）：

((1 2) (3 4))
((1 (2 3)) 4)
(1 ((2 3) 4))
(1 (2 (3 4)))
(((1 2) 3) 4)

这里的括号就像一个带有两个参数的方法，例如乘法 - 然后输出是可能的乘法顺序。

4

2 回答 2

2

您的分配可以看作是“计算二叉树的产量”的逆过程。yield您可以使用 2 个递归调用和 append/3进行编码：

yield((L, R), Y) :-
    yield(L, Ly),
    yield(R, Ry),
    append(Ly, Ry, Y).
yield(T, [T]).

测试：

?- yield(((1,2),(3,4)),Y).
Y = [1, 2, 3, 4] ;
Y = [1, 2, (3, 4)] ;
Y = [ (1, 2), 3, 4] ;
Y = [ (1, 2), (3, 4)] ;
Y = [ ((1, 2), 3, 4)].

因此抽象yield/2地说，当以这种方式调用时，应该解决您的分配：

?- yield(BinTree, [1,2,3,4]).

但是，当然，这不会终止。显然，SLD 解析（Prolog 计算算法）在没有帮助的情况下无法解决这个问题。

但是，如果您还记得 append/3 可以生成构成附加项的所有替代左右列表：

?- append(L,R,[1,2,3,4]).
L = [],
R = [1, 2, 3, 4] ;
L = [1],
R = [2, 3, 4] ;
L = [1, 2],
R = [3, 4] ;
L = [1, 2, 3],
R = [4] ;
L = [1, 2, 3, 4],
R = [] ;
false.

您可以尝试更改调用顺序以获得解决方案。

请注意，在递归之前您需要充分实例化的参数，因此请检查 append 的“输出”。你可以用

...
    Yr = [_|_],
...

为了清楚起见，我还建议重命名谓词并更改参数的顺序：

?- brackets([1,2,3,4],B).
B = 1* (2* (3*4)) ;
B = 1* (2*3*4) ;
B = 1*2* (3*4) ;
B = 1* (2*3)*4 ;
B = 1*2*3*4 ;
false.
于 2012-05-31T08:25:50.087 回答
0

此代码适用于 SWI-Prolog (nextto/3)。

你可以向 Prolog 解释你想要什么，然后问他所有的解决方案：

bracket([A,B], [A,B]).

bracket(In, Out) :-
    member(X, In),
    nextto(X,Y, In),
    append_3(A, [X,Y], B, In),
    append_3(A, [[X,Y]], B, Temp),
    bracket(Temp, Out).



append_3(A,B,C, Out) :-
    append(A, B, Temp),
    append(Temp, C, Out), !.

all_brackets(R) :-
    setof(L, bracket([1,2,3,4], L), R).

你得到

?- all_brackets(R), maplist(writeln, R).
[[[1,2],3],4]
[[1,2],[3,4]]
[[1,[2,3]],4]
[1,[[2,3],4]]
[1,[2,[3,4]]]
R = [[[[1,2],3],4],[[1,2],[3,4]],[[1,[2,3]],4],[1,[[2,3],4]],[[1,2],[3,4]],[1,[2,[3,4]]]].
于 2012-05-31T21:23:58.180 回答