Postfix表达式列表评估
我已经编写了一个程序,用于从表达式列表中递归地评估prolog中的post-fix表达式。例如,假设下面的列表:Postfix表达式列表评估
[+,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.
我没有看到你正在使用这种过于复杂的方法的需要。
如果你希望能够评估任意复杂的表达式,写在修复后,固定运营商元数(所以你可以说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)
是所有你只需要使用固定运算符运算符来评估有效的后缀算术表达式。
我试图做的方法是颠倒后缀表达式,以便我的递归程序可以从右向左读取它:P 我给出的例子是让事情变得简单哈哈。我希望能够处理任何大小的表达式。 据我了解,你的程序版本会不断重新组织表达式,直到它匹配eval_stack谓词之一,然后用表达式的一部分替换结果? 感谢您的回应,我一直试图找出这一个几天现在:) – thegalah 2013-04-11 12:35:35
@thegalah我也得到了这种感觉.... :)除非有一个**非常**很好的理由,总是试图找到一个从左到右读Prolog列表的解决方案。然后,您可以使用统一,匹配和尾递归对列表进行自然迭代。是的,但看到我的编辑答案(并投票,以便其他人也可以使用它)。 – 2013-04-11 12:38:20
[标签:DCG]任何人? – false 2014-11-17 20:07:11