0

堆栈被认为是算术评估的理想数据结构。为什么会这样？
为什么我们甚至需要一个用于算术评估的数据结构？我已经研究了一段时间，但仍然感到困惑。我不明白前缀和后缀表达式的用途是什么，因为中缀表达式的可读性很强。

4

2 回答 2

0

关于为什么后缀/前缀而不是中缀的部分答案在这里得到了很好的解释。作为摘要中缀可读但不容易解析
至于为什么在这里使用堆栈是：
1：在O（1）时间内推送，弹出非常有用进行评估。
2：push：将操作数加到栈上。
3：pop：删除操作数并计算表达式（二进制） 4：最终结果是解析后唯一留在堆栈上的结果

于 2021-01-28T08:10:22.257 回答
0

中缀表达式是可读的，是的。但是如果你想编写一个可以计算算术表达式的算法，你会怎么做？

采用以下表达式：

3 + 4 * 5 + 2 ^ 3 * 12 + 6

你的算法是如何从那里开始的？

一种简单而幼稚的方法是查找最高优先级的操作，对其进行评估，然后重写字符串，并继续这样做，直到执行完所有操作。你会得到这个结果：

3 + 4 * 5 + 2 ^ 3 * 12 + 6
3 + 4 * 5 + 8 * 12 + 6
3 + 20 + 96 + 6
23 + 102
125

这是一种方法。但不是特别有效的方法。在字符串中查找最高优先级的操作所花费的时间与字符串的长度呈线性关系，并且每次操作都必须执行一次，并且每次都重写字符串。你最终会得到类似二次复杂度的东西。可能有一些技巧可以稍微提高效率，但它不会像其他现有方法那样有效。

另一种可能的方法是将表达式放入树中，称为“语法树”或“抽象语法树”。我们得到这个：

        +
 /   /    \   \
3   *      *   6
   / \    / \
  4   5  ^   12
        / \
       2   3

与我们之前的表达式相比，这棵树更容易评估算法：它是一个链接结构，您可以在其中轻松地用该分支的值替换一个分支，而无需重写树中的所有其他内容。所以你2^3在树中替换为 8 ，然后8 * 12替换为96，等等。

后缀（或前缀）符号对于人类来说更难阅读，但对于算法来说更容易操作。我之前的例子在后缀中变成了这个：

3 4 5 * + 2 3 ^ 12 * + 6 +

这可以很容易地从左到右阅读来评估；每次遇到数字时，将其压入堆栈；每次遇到算子，将两个数弹出栈顶，执行操作，压入结果。

假设后缀表达式是正确的，在评估结束时堆栈中应该有一个数字。

EXPR  | [3] 4 5 * + 2 3 ^ 12 * + 6 +
STACK | 3

EXPR   | 3 [4] 5 * + 2 3 ^ 12 * + 6 +
STACK  | 3 4

EXPR   | 3 4 [5] * + 2 3 ^ 12 * + 6 +
STACK  | 3 4 5

EXPR   | 3 4 5 [*] + 2 3 ^ 12 * + 6 +
STACK  | 3 20

EXPR   | 3 4 5 * [+] 2 3 ^ 12 * + 6 +
STACK  | 23

EXPR   | 3 4 5 * + [2] 3 ^ 12 * + 6 +
STACK  | 23 2

EXPR   | 3 4 5 * + 2 [3] ^ 12 * + 6 +
STACK  | 23 2 3

EXPR   | 3 4 5 * + 2 3 [^] 12 * + 6 +
STACK  | 23 8

EXPR   | 3 4 5 * + 2 3 ^ [12] * + 6 +
STACK  | 23 8 12

EXPR   | 3 4 5 * + 2 3 ^ 12 [*] + 6 +
STACK  | 23 96

EXPR   | 3 4 5 * + 2 3 ^ 12 * [+] 6 +
STACK  | 119

EXPR   | 3 4 5 * + 2 3 ^ 12 * + [6] +
STACK  | 119 6

EXPR   | 3 4 5 * + 2 3 ^ 12 * + 6 [+]
STACK  | 125

我们得到了结果。我们只需要通读一次表达式。因此执行时间是线性的。这比我们尝试直接评估中缀表达式并且不得不多次阅读它以寻找下一个要执行的操作时的二次执行时间要好得多。

请注意，从中缀到后缀的转换也可以在线性时间内完成，使用所谓的 Shutting Yard 算法，该算法使用两个堆栈。堆栈太棒了！

于 2021-01-28T11:48:48.540 回答