Postfix表達式列表評估

Question

我已經編寫了一個程序，用於從表達式列表中遞歸地評估prolog中的post-fix表達式。例如，假設下面的列表：

[+,1,2] 

它應該返回3.他們的方式我構建我的斷言是，直到它到達列表的末尾，以便它讀取值向後遞歸調用自身。 （與從左至右閱讀該列表相同：[2,1，+]）。

我的問題是，當我嘗試通過遞歸調用返回多個值時，所有值突然消失。

下面的代碼：

eval_list([Head|Tail],_,Result):- 
    Tail==[], % last element of list 
    Result=Head, 
    write(Head), 
    write(' was stored in Result!\n'). 

eval_list([Head|Tail],Store1,Result):- 
     eval_list(Tail,Store2, NewResult), 
     (\+integer(Store2)) 
    -> 
     % if no integer is bound to Store2, bind Store1 to Head 
     Store1=Head, 
     Result is NewResult, 
     write(Head), 
     write(' is stored value!\n') 
    ; (integer(Store2)) -> 
    % if an integer is bound to store2, we perform operation specified by the Head with the stored number 
     X is Store2+NewResult, 
     Result is X, 
     write('performed operation!\n') 
    ; 
     % if doesnt catch either of these states the program is broken 
     ( print('something broke\n'), 
     print(Store1), 
     nl, 
     print(Store2), 
     nl, 
     print(Head), 
     nl, 
     print(Result), 
     nl 
    ). 

我得到以下輸出：

?- eval_list([+,1,2],X,Result). 
2 was stored in Result! 
1 is stored value! 
something broke 
_G1162 
_L147 
+ 
_G1163 
true. 

我不明白爲什麼我的價值觀消失，或是否有更好的方法來評估名單。

Answer 1

關於您的編程技術的一些建議。您應該在謂詞定義的主體中使用頭匹配和統一而不是顯式的統一，if-else結構。你也應該避免不使用尾遞歸遞歸，除非你的算法本身是遞歸的（例如按順序遍歷樹）。這將使代碼更易於編寫，閱讀和理解。現在，我甚至不想調試你的代碼，但它看起來像你的Store2永遠不會被綁定到一個整數，並且無論你的程序有什麼輸入，總是會成爲一個未綁定的變量。

現在到您的程序。目前還不清楚你試圖達到什麼目的。如果你只想評估形式[Arithmetic_operator, Operand1, Operand2]的名單，這將是更容易編寫：

arith_eval(Expression_list, Result) :- 
    Arithmetic_expr =.. Expression_list, % look up what =.. stands for! 
    Result is Arithmetic_expr. 

我沒有看到你正在使用這種過於複雜的方法的需要。

如果你希望能夠評估任意複雜的表達式，寫在修復後，固定運營商元數（所以你可以說2, 3, +，但不2, 4, 1, +，爲7總和）：

• 從輸入讀取一個元素
  • 推元素堆棧的頂部
  • 儘量減少堆棧：
    • 彈出操作和操作數，如果頂部堆棧
    • 評估
    • 推結果返回堆棧的頂部
• 當輸入爲空，你的籌碼是你的結果

你可以明確地定義效果不同的運營商（這裏只有+和-）如下：

eval_stack([+,A,B|Tail],[Result|Tail]) :- 
    number(A), number(B), 
    !, 
    Result is B + A. 
eval_stack([-,A,B|Tail],[Result|Tail]) :- 
    number(A), number(B), 
    !, 
    Result is B - A. 
eval_stack(Stack,Stack). 

請注意操作符如何匹配堆棧的頂部，並在其下有操作數時應用，將結果推回到堆棧上，或堆棧保持不變。

而且你可以從你的輸入推送到你的籌碼：

evaluate([Next|Rest], Stack, Result) :- 
    eval_stack([Next|Stack],NewStack), 
    evaluate(Rest,NewStack,Result). 
evaluate([],Result,Result). % end of input 

所以，現在你可以用稱之爲：

?- evaluate([2,3,+,3,6,-,+],[],Result). 
Result = [2]. 

?- evaluate([2,3,4,-,-,5,+],[],Result). 
Result = [8]. 

?- evaluate([2,3,4,-,-,5,+,1,3,2,-],[],Result). 
Result = [1,1,8]. 

所以這兩個謂詞，evaluate(Input,Stack,Result)和eval_stack(Stack,NewStack)是所有你只需要使用固定運算符運算符來評估有效的後綴算術表達式。