后缀表达式列表评估 [英] Postfix expression list evaluation
问题描述
我编写了一个程序，用于从表达式列表中递归地评估后缀表达式.例如，给出以下列表:
[+,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.
我不明白为什么我的价值观消失了，或者是否有更好的方法来评估名单.
有关您的编程技术的一些建议.您应该在谓词定义和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来计算用后缀编写的任意复杂表达式(因此您可以说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)仅用于使用固定对数运算符来评估有效的后缀算术表达式.
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]
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.
Here's the code:
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
).
I get the following output:
?- 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.
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.
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.
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):
- Read one element from your input
- Push the element to the top of the stack
- Try to reduce the stack:
- pop operator and operands, if on top of the stack
- evaluate
- push result back on the top of the stack
- When input is empty, your stack is your result
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].
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屋！
