再帰の結果を返す

Question

私はバイナリ式ツリーの値を評価する必要がある問題を解決しようとしています。

tree(LeftNode, Operator, RightNode) 

私は上記のフォームに従ってtree関数を作成した場合、どのように私は結果を渡すことになっています：Evalは、最終的な結果を保持しなければならないとTreeは形式でなければなりません

tree_calc(Tree, Eval) 

結果を格納する空の変数がない場合、計算は再帰をバックアップしますか？

私の理解では、余分な変数は常に、結果を格納するのに必要とされることである。事前に

謝罪、私は基本的に何かを誤解しています確信しているよう。

ありがとうございました。これに関連して

Answer 1

、treeあなたが機能を呼び出しているものではありません、またそれはプロローグが述語と呼ぶであろうものです。 tree(LeftNode, Operator, RightNode)は、木を表す構造として使用されるちょうどの用語です。したがって、たとえば、(2 + 3) * 4は、tree(tree(2,+,3), *, 4)で表されます。 述部をtree_calc(tree(tree(2,+,3),*,4), Eval)とし、その照会には、Eval = 20と入力します。この場合、tree/3という語は結果を持ちません。

tree_calc(tree(L, Op, R), E) :- 
    % Neither L or R are of the form `tree/3` 
    compute(Op, L, R, E). 

compute(+, L, R, E) :- E is L + R. 
compute(*, L, R, E) :- E is L * R. 
compute(-, L, R, E) :- E is L - R. 
compute(/, L, R, E) :- E is L/R. 

あなたはcompute/4を一般化することができます：

述語でtree/3にアクセスする方法の例を与えることが、ここで最も単純なツリーを評価して、単純な述語だ（そう木の葉への再帰はありません）

compute(Op, L, R, E) :- 
    Exp =.. [Op, L, R], 
    E is Exp. 

そして、あなたはそうのようにそれを呼び出すことができます。

| ?- tree_calc(tree(2,+,3), Eval). 

Eval = 5 

yes 

より一般的なケースでは、とRをチェックして、それらがtree/3構造体であるかどうかを確認し、そうであれば再帰的にtree_calcを呼び出します。

Prologは、用語パターンのマッチングに適しています。したがって、ユニファイドL = tree(LL, Op, LR)を確認して成功した場合は、Lが、左側ブランチがLL、操作がOp、右ブランチがLRであることを意味します。この動作をPrologのプロンプトで再生して、動作を確認することができます。

| ?- Tree = tree(2, +, 3), Tree = tree(L, Op, R). 

L = 2 
Op = (+) 
R = 3 
Tree = tree(2,+,3) 

yes 
| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R). 

L = 2 
Op = (+) 
R = tree(3,*,4) 
Tree = tree(2,+,tree(3,*,4)) 

yes 

| ?- Tree = tree(2,+,tree(3,*,4)), Tree = tree(L, Op, R), R = tree(LR, OpR, RR). 

L = 2 
LR = 3 
Op = (+) 
OpR = (*) 
R = tree(3,*,4) 
RR = 4 
Tree = tree(2,+,tree(3,*,4)) 

yes 
| ?-