从等于数字的数字列表中生成所有表达式[PROLOG] [英] Generate all expressions from list of numbers equal to a number [PROLOG]

问题描述

我得到了一个数字列表，例如[22,45,2,6,7,...].

I am given a list of numbers, for example [22,45,2,6,7,...].

现在我必须插入二进制运算符:数字之间的+，-，/，*和括号(，)，以便表达式等于给定编号 k .

Now I have to insert binary operators: +, -, /, * and parentheses (, ) between numbers so that expression is equal to given number k.

列出所有可能的表达式，这些表达式是通过插入运算符和括号而创建的，它们将得出 k 的总和.

List all possible expressions created by insertions of operators and parentheses that will give sum of k.

结果表达式中数字的位置必须固定，即仅在数字之间或周围插入运算符和括号

例如:给定数字k=9和列表[1,2,3]，一种解决方案是[(,(,1,+,2,),*,3,)]. 我该怎么办?

For example: given number k=9 and list [1,2,3], one solution would be [(,(,1,+,2,),*,3,)]. How would I do that?

[我当前的错误解决方案]: 现在，我知道如何通过从左到右并吃掉Operand1，Operator，Operand2直到没有东西进食来评估像[1,+,3,*,5]这样的表达式.

[ my current wrong solution ]: Right now I know how to evaluate expression like [1,+,3,*,5] by going from left to right and eating Operand1,Operator,Operand2 until there is nothing to eat.

但是我也必须插入括号.

But I have to insert parentheses too..

任何人都可以草拟解决方案或给出提示吗?

Can anybody sketch a solution or give a hint?

这是一个古老的考试问题，我正准备在3个月内进行考试，因此我试图解决这些问题，但是我被卡住了.

This was an old exam question, and I'm preparing for exam which will be in 3 months, so I'm trying to solve these, but I'm stuck.

这是序言问题.

推荐答案

在不带括号的情况下考虑括号问题的一种方法是使用后缀表示法.换句话说:

One way to think about the parenthesis problem without actually putting any parentheses is to use postfix notation. In other words:

(a + b) * c

变成:

a b + c *

这是标准Prolog表示法中的以下树:

which is the following tree in canonical Prolog notation:

*(+(a, b), c)

类似地:

a + (b * c) ---> a b c * + ---> +(a, *(b, c))

对于一个完整的示例，使用三个操作数1、2和3，并且仅以+和*作为运算符，为简短起见，您将获得:

For a complete example, with three operands, 1, 2, and 3, and only + and * as operators, to keep it short, you get:

1 2 + 3 + ---> (1 + 2) + 3 = 6
1 2 + 3 * ---> (1 + 2) * 3 = 9
1 2 * 3 + ---> (1 * 2) + 3 = 6
1 2 * 3 * ---> (1 * 2) * 3 = 6
1 2 3 + + ---> 1 + (2 + 3) = 6
1 2 3 + * ---> 1 * (2 + 3) = 5
1 2 3 * + ---> 1 + (2 * 3) = 7
1 2 3 * * ---> 1 * (2 * 3) = 6

看第一列，我得到以下一般想法:您从 n 操作数和 n -1二进制运算符开始.您将前两个操作数压入堆栈，并需要再执行2 * n -3个步骤.在每一步，您都可以推操作数或应用运算符.如果还剩下任何操作数，则始终可以推入操作数.仅当堆栈上有两个或更多操作数时，才可以应用运算符.您将不得不减少此时的堆栈.

Looking at the first column, I get the following general idea: you start with n operands and n-1 binary operators. You push the first two operands on the stack, and need to perform 2*n-3 more steps. At each step, you either push an operand or apply an operator. You can always push an operand if you still have any left. You can apply an operator only if you have two or more operands on the stack; you will have to reduce the stack at that point.

回溯将考虑所有可能性(因此，这是对解决方案空间的典型蛮力穷举搜索).您将有两个选择点来源:选择一个运算符；并推动或减少.

Backtracking will take care of enumerating all possibilities (so this is a typical brute-force exhaustive search of the solution space). You will have two sources of choicepoints: picking one of the operators; and either pushing or reducing.

考虑到这一点，我实现了谓词的以下实现，该谓词采用一个操作数列表，一个二进制运算符列表，并为您提供括号化"表达式:

With this in mind, I arrive at the following implementation of a predicate that takes a list of operands, a list of binary operators, and gives you a "parenthesized" expression:

expr(Operands, Operators, E) :-
    Operands = [A, B|Rest],
    length(Operands, N),
    Steps is 2*N - 3,
    expr(Steps, Rest, [B, A], Operators, E).

这会将前两个操作数推入堆栈，并计算了剩余的步数.

This pushed the first two operands to the stack and calculated the number of steps left.

expr(Steps, Operands, Stack, Operators, E) :-
    (   succ(Steps0, Steps) ->
        next(Steps0, Operands, Stack, Operators, E)
    ;   Stack = [E]
    ).

在这里，我使用succ/2倒数至0，然后停止；最后，堆栈中唯一的元素是您的表达式.

Here I used succ/2 to count down to 0 and then stop; at the end, the only element on the stack is your expression.

next(Steps, Operands, Stack, Operators, E) :-
    push(Operands, Stack, Operands_next, Stack_next),
    expr(Steps, Operands_next, Stack_next, Operators, E).
next(Steps, Operands, Stack, Operators, E) :-
    member(Op, Operators),
    reduce(Stack, Op, Stack_next),
    expr(Steps, Operands, Stack_next, Operators, E).

这是您推动或减少的地方.两个单独的子句是选择点的第一个来源.使用member/2从列表中选择一个运算符是另一个.

This is where you either push or reduce. The two separate clauses is the first source of choice points; using member/2 to take one operator from the list is the other.

push([X|Xs], S0, Xs, [X|S0]).

reduce([A,B|Stack], Op, [X|Stack]) :-
    X =.. [Op, B, A].

实施推动和减少是微不足道的.我使用"univ"运算符=..从类似[+, 1, 2]的列表中创建了类似+(1, 2)的术语.

Implementing pushing and reducing is trivial. I used the "univ" operator =.. to make terms like +(1, 2) from a list like [+, 1, 2].

有了这个，您已经可以问如何用+，*和括号从[1,2,3]中减去7":

With this, you can already ask "how can I use +, *, and parenthesis to make 7 out of [1,2,3]":

?- expr([1,2,3], [+,*], E), E =:= 7.
E = 1+2*3 ;
false.

这是最基本的生成和测试":生成算术表达式，然后测试它们的计算结果是否为值.如果省略测试，则可以看到所有表达式:

This is the most basic "generate and test": you generate arithmetic expressions, then test if they evaluate to a value. If you leave out the test, you can see all expressions:

?- expr([1,2,3], [+,*], E).
E = 1+(2+3) ;
E = 1*(2+3) ;
E = 1+2*3 ;
E = 1*(2*3) ;
E = 1+2+3 ;
E =  (1+2)*3 ;
E = 1*2+3 ;
E = 1*2*3 ;
false.

一个令人好奇的细节是，因为+和*已经被定义为中缀运算符，所以Prolog会编写它们，甚至为您加上括号.我不知道像E = (1+2)*3这样的解决方案对您来说是否足够好，还是您真的需要['(', 1, +, 2, ')', *, 3]吗? 另一个答案似乎已经对此有一个可行的解决方案.由于此处的表达式已经是有效的算术表达式，因此您必须对其进行一些调整.我可能会这样写:

One curious detail is that because + and * are already defined as infix operators, Prolog writes them and even parenthesizes them for you. I don't know if a solution like E = (1+2)*3 is good enough for you or do you really need ['(', 1, +, 2, ')', *, 3]. The other answer seems to have a working solution for this already. Since here the expression is already a valid arithmetic expression, you would have to adjust it slightly. I would probably write it like this:

infix(N) -->
    {   number(N)
    }, !,
    [N].
infix(E) -->
    {   compound(E),
        E =.. [Op, A, B]
    }, !,
    ['('], infix(A), [Op], infix(B), [')'].

我也不知道1 + 2 + 3 = 3 + 3 = 6是否等于1+(2 + 3)= 1 + 5 = 6:您是否需要考虑关联性?

I also don't know if 1+2+3 = 3+3 = 6 is the same as 1+(2+3) = 1+5 = 6: do you need to consider associativity?

无论哪种方式，您都可以将expr/3包裹在这样的谓词中:

Either way, you can wrap expr/3 in a predicate like this:

equals_k(Numbers, K, E) :-
    expr(Numbers, [+,-,*,/], E0),
    K =:= E0,
    phrase(infix(E0), E).

PS:很容易得到除以零的异常，例如:

PS: it is quite easy to get a division by zero exception, try for example:

?- expr([1,0], [/], E), R is E.

这篇关于从等于数字的数字列表中生成所有表达式[PROLOG]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！