algorithm - 为什么我们需要前缀、后缀表示法

Question

我知道它们如何相互转换，但从未真正了解它们的应用程序是什么。通常的中缀操作可读性很强，但是它在哪里失败导致了前缀和后缀表示法的开始

score 59 · Accepted Answer

中缀表示法对于人类来说很容易阅读，而前/后缀表示法对于机器来说更容易解析。前置/后置表示法的一大优势是永远不会出现像运算符优先级这样的问题。

例如，考虑中缀表达式1 # 2 $ 3。现在，我们不知道这些运算符是什么意思，所以有两种可能的对应后缀表达式：1 2 # 3 $和1 2 3 $ #. 如果不了解这些运算符的使用规则，则中缀表达式本质上是毫无价值的。

或者，用更一般的术语来说：可以在没有任何额外知识的情况下从前/后缀表达式恢复原始（解析）树，但对于中缀表达式而言，情况并非如此。

score 5 · Accepted Answer

后缀表示法，也称为RPN，从左到右非常容易处理。一个操作数被压入堆栈；运算符从堆栈中弹出其操作数并压入结果。很少或不需要解析。Forth 和一些计算器都使用它（HP 计算器因使用 RPN 而闻名）。

前缀符号几乎同样容易处理；它在 Lisp 中使用。

score 2 · Accepted Answer

至少对于前缀符号的情况：使用前缀运算符的优点是在语法上，它读起来就好像运算符是一个函数调用

score 1 · Accepted Answer

前缀/后缀与中缀的另一个方面是运算符的数量（它应用于多少个参数）不再必须严格限制为 2。它可以更多，有时更少（默认值为 0 或 1自然暗示，如加法/减法为零，乘法/除法为一）。

score -1 · Accepted Answer

在中缀表达式的情况下，评估所需的时间是 O(n^2) 原因是运算符的优先级。
例如：a+b*c
在这里我们不会直接计算 a+b
首先我们遍历整个表达式并找到具有最高优先级的运算符。在我们的例子中，它是*，因此我们首先评估b*c 并再次遵循相同的过程，直到我们完成对表达式的评估。

但在后缀或中缀表达式的情况下并非如此。评估后缀表达式所需的时间是 O(n)

中缀到后缀的转换 ==== O(n)
后缀评估 ==== O(n)

总时间 = O(n) + O(n)= O(n)

在后缀评估的情况下，我们不需要考虑运算符的优先级。只是我们需要从左到右评估

同样，在前缀表达式的情况下，我们需要从右到左计算

5 回答 5