后缀表达式列表评估

Question

我编写了一个程序来从表达式列表中递归地评估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.

我不明白为什么我的价值观会消失,或者是否有更好的方法来评估清单.

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.

我不认为你使用这种过于复杂的方法是必要的.

如果你想能够用固定的运算符arity来评估任意复杂的表达式(用post-fix编写)(所以你可以说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)只是用于评估仅使用fixed-arity运算符的有效后置修复算术表达式所需的全部内容.