后缀表达式列表求值 [英] Postfix expression list evaluation

问题描述

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

I have written a program to evaluate a post-fix expression in prolog recursively from an expression list. For example, given the following list:

[+,1,2]

它应该返回 3.我构造谓词的方式是递归地调用自身，直到它到达列表的末尾，以便它向后读取值.(与从左到右阅读此列表相同:[2,1,+]).

It should return 3. They way I have constructed my predicate is to call itself recursively until it reaches the end of the list so that it reads values backwards. (the same as reading this list from left to right:[2,1,+]).

我的问题是，当我尝试通过递归调用返回多个值时，所有值都会突然消失.

My problem is that when I try to return more than one value through the recursive calls all the values suddenly disappear.

代码如下:

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

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!
')
   ;  (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!
')
   ;
      % if doesnt catch either of these states the program is broken
      (  print('something broke
'),
         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.

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

I don't understand why my values disappear, or if there is a better way to evaluate the list.

推荐答案

关于你的编程技巧的一些建议.您应该在谓词定义和 if-else 构造的主体中使用头部匹配和统一而不是显式统一.您还应该避免非尾递归递归，除非您的算法本质上是递归的(例如，按顺序遍历树).这将使代码更容易编写、阅读和理解.现在，我什至不想调试您的代码，但看起来您的 Store2 永远不会绑定到整数，并且始终是未绑定的变量，无论您输入什么程序有.

Some advice on your programming technique. You should use head matching and unification instead of explicit unification in the body of your predicate definitions, and if-else constructs. You should also avoid not tail-recursive recursion, unless your algorithm is inherently recursive (in-order tree traversal, for example). This will make the code easier to write, read, and understand. Right now, I don't even feel like debugging your code, but it looks like your Store2 would never be bound to an integer, and is always going to be an unbound variable, no matter what input your program has.

现在开始你的程序.目前尚不清楚您要达到的目标.如果您只想评估 [Arithmetic_operator, Operand1, Operand2] 形式的列表，编写起来会容易得多:

Now to your program. It is not clear what you are trying to achieve. If you only want to evaluate list of the form [Arithmetic_operator, Operand1, Operand2], it would be much easier to write:

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

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

I don't see the need for this overly complicated approach you are using.

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

If you want to be able to evaluate arbitrarily complex expressions, written in post-fix, with fixed operator arity (so you can say 2, 3, +, but not 2, 4, 1, +, for a sum of 7):

• 从您的输入中读取一个元素
  • 将元素推到栈顶
  • 尝试减少堆栈:
    • 弹出操作符和操作数，如果在栈顶
    • 评估
    • 将结果推回栈顶

    您可以像这样显式定义不同运算符的效果(这里只有 + 和 -):

    You could explicitly define the effect of different operators (here, only + and -) like this:

    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).
    

    注意运算符如何匹配堆栈顶部，并在其下方有操作数时应用，将结果推回堆栈，或堆栈保持不变.

    Note how either an operator matches the top of your stack, and is applied when there are operands below it, pushing the result back on the stack, or the stack is left unchanged.

    你可以从你的输入推送到你的堆栈:

    And you can push from your input to your stack:

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

    所以现在你可以这样称呼它:

    So now you could call this with:

    ?- 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) 是评估有效后缀所需的全部内容仅具有固定数量运算符的算术表达式.

    So these two predicates, evaluate(Input,Stack,Result), and eval_stack(Stack,NewStack) is all you would need for evaluating a valid post-fix arithmetic expressions with fixed-arity operators only.

    这篇关于后缀表达式列表求值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！