返回遞歸結果

Question

我想解決一個問題，我需要評估二進制表達式樹的值。

tree_calc(Tree, Eval) 

其中Eval應持有的最終結果和Tree必須是形式：

tree(LeftNode, Operator, RightNode) 

如果我創建tree功能根據上面的表格，我怎麼傳遞的結果如果沒有一個空變量來存儲結果，計算會返回遞歸嗎？

我的理解是，一個額外的變量總是需要存儲的結果。提前

道歉，因爲我相信我誤解基本的東西。

感謝您的幫助。

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/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：

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

而且你可以調用它像這樣：

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

Eval = 5 

yes 

對於更一般的情況，您需要檢查L和R以查看它們本身是否爲tree/3結構，如果是，則遞歸調用tree_calc。

Prolog擅長匹配術語模式。因此，如果您檢查統一L = tree(LL, Op, LR)並且成功，則表示L是tree，其左分支LL，操作Op和右分支LR。您可以在序言提示這種行爲發揮，看看它是如何工作的：

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