1

我编写了一个程序来从表达式列表递归地评估 prolog 中的后修复表达式。例如，给定以下列表：

[+,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.

我不明白为什么我的价值观会消失，或者是否有更好的方法来评估列表。

4

1 回答 1

6

关于您的编程技术的一些建议。您应该在谓词定义和 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.

我认为您不需要使用这种过于复杂的方法。

如果您希望能够评估任意复杂的表达式，用 post-fix 编写，具有固定的运算符 arity（所以您可以说2, 3, +，但不是2, 4, 1, +，总和为 7）：

  • 从输入中读取一个元素
    • 将元素压入栈顶
    • 尝试减少堆栈：
      • 弹出运算符和操作数，如果在堆栈顶部
      • 评估
      • 将结果推回栈顶
  • 当输入为空时，您的堆栈就是您的结果

您可以像这样显式定义不同运算符的效果（这里，只有+and -）：

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)是您只需要使用固定数量运算符评估有效的后缀算术表达式所需的全部内容。

于 2013-04-11T11:38:06.930 回答