Generate all expressions from list of numbers equal to a number [PROLOG]

Question

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

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

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

Position of numbers in resulting expression have to be fixed, i.e. only insertion of operators and parentheses between or around numbers

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

[ 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?

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.

EDIT: This is prolog question.

Answer 1

I think trying to directly build the result list with parentheses while traversing the input is a bad idea. It's easier to build up the syntax tree of an expression whose leaves are labeled with the elements of the given list, then process that in a separate step.

For example:

?- leaves_expr([A,B,C,D], Expr).
Expr = leaf(A)+ (leaf(B)+ (leaf(C)+leaf(D))) ;
Expr = leaf(A)+ (leaf(B)+leaf(C)*leaf(D)) ;
Expr = leaf(A)+ (leaf(B)+leaf(C)+leaf(D)) ;
Expr = leaf(A)+ (leaf(B)*leaf(C)+leaf(D)) ;
Expr = leaf(A)+leaf(B)* (leaf(C)+leaf(D)) ;
Expr = leaf(A)+leaf(B)* (leaf(C)*leaf(D)) ;

This can be implemented as follows:

leaves_expr([X], leaf(X)).
leaves_expr(Leaves, X + Y) :-
    append([L|Left], [R|Right], Leaves),
    leaves_expr([L|Left], X),
    leaves_expr([R|Right], Y).
leaves_expr(Leaves, X * Y) :-
    append([L|Left], [R|Right], Leaves),
    leaves_expr([L|Left], X),
    leaves_expr([R|Right], Y).

The append/3 calls are used to decompose the list of leaves into non-empty parts to avoid nontermination problems. I would be interested in an elegant way of doing this with DCGs.

Then, given an expression tree like this, we can "output" it again in a fully parenthesized form:

expr_parenthesized(leaf(X)) -->
    [X].
expr_parenthesized(X + Y) -->
    ['('],
    expr_parenthesized(X),
    [+],
    expr_parenthesized(Y),
    [')'].
expr_parenthesized(X * Y) -->
    ['('],
    expr_parenthesized(X),
    [*],
    expr_parenthesized(Y),
    [')'].

Composing these two parts, we get:

?- leaves_expr([A,B,C], Expr), expr_parenthesized(Expr, Parenthesized).
Expr = leaf(A)+ (leaf(B)+leaf(C)),
Parenthesized = ['(', A, +, '(', B, +, C, ')', ')'] ;
Expr = leaf(A)+leaf(B)*leaf(C),
Parenthesized = ['(', A, +, '(', B, *, C, ')', ')'] ;
Expr = leaf(A)+leaf(B)+leaf(C),
Parenthesized = ['(', '(', A, +, B, ')', +, C, ')'] ;
Expr = leaf(A)*leaf(B)+leaf(C),
Parenthesized = ['(', '(', A, *, B, ')', +, C, ')'] ;
Expr = leaf(A)* (leaf(B)+leaf(C)),
Parenthesized = ['(', A, *, '(', B, +, C, ')', ')'] ;
Expr = leaf(A)* (leaf(B)*leaf(C)),
Parenthesized = ['(', A, *, '(', B, *, C, ')', ')'] ;

and so on. If you write the easy predicate expr_value/2 to evaluate such expressions (constructed from numbers at the leaves), you're done.