为什么后缀（逆波兰）表示法比前缀表示法更常用？

Question

为什么后缀（逆波兰）表示法比前缀表示法更常用？

algorithmcalculatorpostfix-notationpolish-notation

11

当我说“使用”时，我的意思是它在许多计算器（如HP35）中的使用。

我的猜测（和困惑）是 -

后缀表示实际上更节省内存-（SO帖子评论在这里）。（困惑-两者的评估算法类似，都使用堆栈）
计算器中的键盘输入类型（困惑-这并不重要，因为它只取决于首先给出还是最后给出的操作符顺序）

另一个问这个问题的方式是后缀表示相对于前缀表示有什么优势？
有人能启发我吗？

- Amartya

5个回答

4

前缀表示法在数学中可能更常用，例如F(x,y)这样的表达式。这是一个非常古老的传统，但像许多旧系统（英尺和英寸，信纸）一样，与我们如果使用更具思考性的设计系统相比，它有缺点。

几乎每一本大学一年级的数学教科书都要浪费至少一页来解释f(g(x))的意思是我们先应用g然后再应用f。按阅读顺序做更有意义：x.f.g表示我们先应用f。然后如果我们想要“之后”应用h，我们只需要说x.f.g.h。

以我最近处理的三维旋转问题为例。我们想根据XYZ约定旋转向量。在后缀中，操作是vec.rotx(phi).roty(theta).rotz(psi)。使用前缀，我们必须重载*或()，然后反转操作顺序，例如rotz*roty*rotx*vec。这很容易出错，并且在想要思考更大问题时不得不一直考虑这个问题，这很烦人。

例如，我在别人的代码中看到了类似于rotx*roty*rotz*vec的东西，我不知道这是一个错误还是一个不寻常的ZYX旋转约定。我仍然不知道。程序工作了，所以它在内部是自洽的，但在这种情况下，前缀表示法使维护变得困难。

前缀表示法的另一个问题是当我们（或计算机）解析表达式f(g(h(x)))时，我们必须将f保留在我们的内存中（或在堆栈上），然后是g，然后是h，然后好的，我们可以将h应用于x，然后我们可以将g应用于结果，然后将f应用于结果。与x.f.g.h相比，需要在内存中存储太多的东西。在某个点上（对于人类而言，比计算机更快），我们会耗尽内存。这种方式的失败并不常见，但为什么要打开这扇门呢？x.f.g.h不需要短期记忆。这就像递归和循环之间的区别。

还有一件事：f(g(h(x)))有太多的括号，看起来像Lisp。当涉及运算符优先级时，后缀表示法是无歧义的。

一些数学家（特别是Nathan Jacobson）曾经试图改变惯例，因为后缀在非交换代数中更容易处理，其中顺序真的很重要，但成功的机会很小。但既然我们有机会在计算中做得更好，我们应该抓住这个机会。

- Edward Doolittle

3

基本上，因为如果你用后缀表达式编写表达式，你可以只使用一个堆栈来计算该表达式：

读取表达式的下一个元素，
如果它是操作数，则将其推入堆栈中，
否则从堆栈中读取所需的操作数，并将结果推入堆栈中。
如果表达式未结束，请转到步骤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 ]

- Khaled.K

当从右到左进行评估时，它与前缀表示法（例如* + 4 3 + 2 1）有何不同？ - KRoy

2

离线评估的两种表示法在理论机中是相同的

(贪心求值策略)只使用一个堆栈进行求值(不将运算符放入堆栈)

可以通过从右到左评估前缀表示法来完成。

- 7 + 2 3
# evaluate + 2 3
- 7 5
# evaluate - 7 5
2

这与计算后缀表达式的从左到右的方式相同。

7 2 3 + -
# put 7 on stack
7 2 3 + -
# evaluate 2 3 +
7 5 -
# evaluate 7 5 -
2

（优化的短路策略）使用两个栈进行评估（一个用于运算符，一个用于操作数）

可以通过从左到右评估前缀表示法来完成。

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

这与评估后缀表示法从右到左相同。

(优化短路策略)使用一个包含元组的栈进行评估（与上述相同）

可以通过评估前缀表示法从左到右来完成。

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

这与评估后缀表达式从右到左相同。

在线计算器在人类从左到右输入数据时的评估

将数字输入计算器时，后缀表达式2 3 +可以立即评估，而不需要知道人类将要输入的符号是什么。这与前缀表达式相反，因为当我们有- 7 +时，我们什么也不做，直到我们得到像- 7 + 2 3这样的东西。

在线计算器在人类从右到左输入数据时的评估

现在，前缀表达式可以立即评估+ 2 3，而后缀表达式则在有3 + -时等待进一步输入。

请参考@AshleyF的注释，阿拉伯语从右到左书写，而英语从左到右书写！

我猜小端和大端与此前缀/后缀表示法有关。

最后一个评论，逆波兰表示法得到了Dijkstra的强烈支持（他是短路优化的强烈反对者，并被认为是逆波兰表示法的发明者）。支持他的观点还是不支持（我不支持）由你决定。

- KRoy

2

如果你喜欢人类的阅读顺序与机器的基于堆栈的评估顺序相匹配，那么后缀表达式是一个不错的选择。假设你从左到右阅读，但并非所有人都是这样（例如希伯来语、阿拉伯语等）。同时，假设你的机器使用堆栈进行评估，但并非所有机器都是这样（例如术语重写-请参见Joy）。另一方面，如果人类更喜欢前缀而机器在“从后往前/从下往上”评估，则也没有问题。如果关注的是作为标记到达时的评估，则序列化也可以反转。在前缀表示法中，工具辅助可能会更好（首先了解函数/单词可能有助于限定有效参数范围），但你也可以从右到左输入。我认为这只是一种惯例...

- AshleyF

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lasse V. Karlsen · Accepted Answer

首先，使用后缀表示法更易实现求值。

对于前缀表示法，如果您先压入一个运算符，然后是它的操作数，您需要知道何时该运算符已经具备了所有操作数。基本上，您需要跟踪您所推送的运算符何时拥有其所有操作数，以便您可以展开堆栈并进行评估。

由于复杂表达式可能最终在堆栈上有许多运算符，因此您需要有一个能够处理这些运算符的数据结构。

例如，这个表达式：- + 10 20 + 30 40 在同一时间将有一个 - 和一个 +存在于堆栈中，对于每个运算符，您都需要知道是否拥有可用的操作数。

使用后缀表示法，当您推送一个运算符时，操作数（应）已经在堆栈上，只需弹出操作数并进行计算即可。您只需要一个能够处理操作数的堆栈，不需要其他任何数据结构。