我所说的使用是指它在许多计算器中的使用，例如 HP35-
我的猜测（和困惑）是——
- 后缀实际上更节省内存 - （所以在这里发表评论）。（混淆 - 两者的评估算法与堆栈相似）
- 当时计算器中的键盘输入类型（混淆 - 这应该无关紧要，因为它只取决于首先或最后给出的运算符的顺序）
可以问这个问题的另一种方式是后缀表示法比前缀有什么优势？
任何人都可以启发我吗？
问问题
3148 次
5 回答
5
一方面，更容易实施评估。
使用前缀，如果您推送一个运算符，然后是它的操作数，您需要提前知道该运算符何时拥有其所有操作数。基本上，您需要跟踪您推送的运算符何时拥有所有操作数，以便您可以展开堆栈并进行评估。
由于一个复杂的表达式可能最终会在堆栈上包含许多运算符，因此您需要一个可以处理此问题的数据结构。
例如，这个表达式：- + 10 20 + 30 40将同时在堆栈上有一个-和一个+，对于每个，您需要知道您是否有可用的操作数。
使用后缀，当您压入运算符时，操作数（应该）已经在堆栈上，只需弹出操作数并进行评估。您只需要一个可以处理操作数的堆栈，不需要其他数据结构。
于 2015-06-22T08:12:41.457 回答
3
前缀表示法可能更常用......在数学中，在像 F(x,y) 这样的表达式中。这是一个非常古老的惯例，但与许多旧系统（英尺和英寸、信纸）一样，与我们使用设计更周到的系统相比，它也有缺点。
几乎每一年大学数学教科书都要浪费一页，至少要解释这f(g(x))意味着我们g先申请然后再申请f。按阅读顺序做更有意义：x.f.g意味着我们f先申请。然后，如果我们想申请h“之后”，我们就说x.f.g.h.
例如，考虑一个我最近必须处理的 3d 旋转问题。我们想根据 XYZ 约定旋转一个向量。在 postfix 中，操作是vec.rotx(phi).roty(theta).rotz(psi). 使用前缀，我们必须重载*or()然后反转操作的顺序，例如rotz*roty*rotx*vec. 当您想考虑更大的问题时，必须一直考虑这一点很容易出错并且令人恼火。
例如，我rotx*roty*rotz*vec在别人的代码中看到了类似的东西，我不知道这是一个错误还是一个不寻常的 ZYX 轮换约定。我还是不知道。该程序有效，因此它在内部是自洽的，但在这种情况下，前缀表示法使其难以维护。
前缀符号的另一个问题是，当我们（或计算机）解析f(g(h(x)))我们必须保存f在内存（或堆栈）中的表达式时，然后g，然后h，然后 ok 我们可以应用h到x，然后我们可以应用g到结果，然后f到结果。与 相比，内存中的东西太多了x.f.g.h。在某些时候（对于人类来说，比计算机早得多）我们会耗尽内存。这种方式的失败并不常见，但为什么在x.f.g.h不需要短期记忆的情况下甚至打开大门。这就像递归和循环之间的区别。
还有一件事：f(g(h(x)))有这么多括号，它开始看起来像 Lisp。当涉及到运算符优先级时，后缀表示法是明确的。
一些数学家（尤其是 Nathan Jacobson）尝试改变约定，因为在顺序非常重要的非交换代数中使用后缀更容易，但收效甚微。但既然我们有机会在计算方面做得更好，我们应该抓住这个机会。
于 2015-06-23T16:40:04.300 回答
2
基本上，因为如果您在postfix中编写表达式，则可以仅使用Stack来评估该表达式：
阅读表达式的下一个元素，
如果是操作数，则压入堆栈，
否则从操作所需的堆栈操作数中读取，并将结果压入堆栈。
如果不是表达式的结尾，请转到 1。
例子
expression = 1 2 + 3 4 + *
stack = [ ]
Read 1, 1 is Operand, Push 1
[ 1 ]
Read 2, 2 is Operand, Push 2
[ 1 2 ]
Read +, + is Operation, Pop two Operands 1 2
Evaluate 1 + 2 = 3, Push 3
[ 3 ]
Read 3, 3 is Operand, Push 3
[ 3 3 ]
Read 4, 4 is Operand, Push 4
[ 3 3 4 ]
Read +, + is Operation, Pop two Operands 3 4
Evaluate 3 + 4 = 7, Push 7
[ 3 7 ]
Read *, * is Operation, Pop two Operands 3 7
Evaluate 3 * 7 = 21, Push 21
[ 21 ]
于 2015-06-22T08:56:13.323 回答
2
如果您希望您的人工阅读顺序与机器的基于堆栈的评估顺序相匹配，那么 postfix 是一个不错的选择。
也就是说，假设您从左到右阅读，但并非所有人都这样做（例如希伯来语、阿拉伯语……）。并假设您的机器使用堆栈进行评估，但并非所有人都这样做（例如术语重写 - 请参阅Joy）。
另一方面，当机器评估“从后到前/从下到上”时，人类偏好前缀并没有错。如果关注的是令牌到达时的评估，则序列化也可以反转。工具辅助在前缀表示法中可能会更好地工作（首先了解函数/单词可能有助于确定有效参数的范围），但您始终可以从右到左键入。
我相信这只是一个约定...
于 2015-06-23T16:03:35.377 回答
2
两种符号的离线评估在理论机器中是相同的
（急切评估策略）仅使用一个堆栈进行评估（不将运算符放入堆栈）
它可以通过评估Prefix-notation right-to-left来完成。
- 7 + 2 3
# evaluate + 2 3
- 7 5
# evaluate - 7 5
2
这与评估Postfix-notation left-to-right相同。
7 2 3 + -
# put 7 on stack
7 2 3 + -
# evaluate 2 3 +
7 5 -
# evaluate 7 5 -
2
（优化的短路策略）使用两个堆栈进行评估（一个用于操作符，一个用于操作数）
它可以通过评估Prefix-notation left-to-right来完成。
|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# push < 2 3 in stack
instruction-stack: or, less_than
operand-stack: 1, 2, 3
# evaluate < 2 3 as 1
instruction-stack: or
operand-stack: 1, 1
# evaluate || 1 1 as 1
operand-stack:1
请注意，我们可以在这里轻松地 对表达式进行短路优化boolean（与之前的评估序列相比）。
|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# Is it possible to evaluate `|| 1` without evaluating the rest ? Yes !!
# skip < 2 3 and put place-holder 0
instruction-stack: or
operand-stack: 1 0
# evaluate || 1 0 as 1
operand-stack: 1
这与评估Postfix-notation right-to-left相同。
（优化的短路策略）用一个带元组的堆栈进行评估（同上）
它可以通过评估Prefix-notation left-to-right来完成。
|| 1 < 2 3
# put || 1 in tuple-stack
stack tuple[or,1,unknown]
< 2 3
# We do not need to compute < 2 3
stack tuple[or,1,unknown]
# evaluate || 1 unknown as 1
1
这与评估Postfix-notation right-to-left相同。
在计算器中进行在线评估，同时人工从左到右输入数据
将数字放入计算器时，可以立即评估后缀符号，而无需了解人类将要输入的符号。 2 3 +它与前缀表示法相反，因为当我们拥有时，- 7 +我们无事可做，直到我们得到类似的东西- 7 + 2 3。
在计算器中进行在线评估，同时人类从右到左输入数据
现在前缀表示法可以+ 2 3立即计算，而后缀表示法在它有时等待进一步的输入3 + -。
请参阅@AshleyF 请注意，阿拉伯语从右到左书写，而英语从左到左书写！
我猜little-endian和big-endian与此前缀/后缀表示法有关。
最后一条评论是，Dijkstra 强烈支持 Reverse-Polish notation（他是短路优化的强烈反对者，被认为是 Reverse-Polish notation 的发明者）。支持与否是你的选择（我不支持）。
于 2018-11-15T19:29:20.573 回答