Prologuer toutes les expressions possibles de x donné

Question

J'ai un programme prologue avec une grammaire donnée :

sum --> [+], mult, sum | mult | num.
mult --> [*], num, xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] ... etc

J'ai une représentation arborescente abstraite de mes expressions.Par exemple: mul(num(2),var(x)) ce qui équivaut [*,2,x] est valable.Je veux pouvoir créer toutes les expressions qui satisfont un x et une solution donnés.En utilisant

allExpressions(Tree, X, Solution).

Par exemple:

?- allExpressions(Tree, 2, 6)
Tree = mul(num(3),x)
Tree = sum(num(2),mul(num(2),var(x))
etc.

En raison de ma grammaire, il ne s'agira évidemment pas d'un ensemble illimité d'équations pour cela.J'ai déjà programmé un evaluation(Tree, X, Solution) qui calcule la réponse étant donné la variable X.J'ai donc besoin d'aide pour générer l'ensemble possible d'équations pour une variable x et une solution données.

Avez-vous des idées sur la façon dont j'aborde cela ?Merci

Answer 1

C'est facile:Puisque toutes vos opérations arithmétiques ne peuvent augmenter la valeur des expressions, il est simple de limiter la profondeur lors de la recherche de solutions.Décrivez simplement de manière inductive à quoi peut ressembler une solution.Vous pouvez le faire par exemple avec les contraintes de domaine fini de SWI-Prolog pour l'addition et la multiplication comme ceci :

:- use_module(library(clpfd)).

expression(var(x), X, X).
expression(num(N), _, N) :- phrase(num, [N]).
expression(mul(A,B), X, N) :-
        N1 * N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).
expression(sum(A,B), X, N) :-
        N1 + N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).

Je laisse les autres opérations en exercice.

Exemple de requête et quelques résultats :

?- expression(Tree, 2, 6).
Tree = mul(var(x), num(3)) ;
Tree = mul(num(2), num(3)) ;
    [...solutions omitted...]
Tree = sum(num(2), mul(num(2), var(x))) ;
Tree = sum(num(2), mul(num(2), num(2))) ;
    [...solutions omitted...]
Tree = sum(sum(num(2), num(2)), num(2)) ;
false.

+1 pour utiliser une représentation propre et non par défaut pour les arbres d'expression (var(x), num(N) etc.), qui vous permet d'utiliser la correspondance de modèles lorsque vous raisonnez à ce sujet.