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)是所有你只需要使用固定运算符运算符来评估有效的后缀算术表达式。