堆栈和算术评估
Stack And Arithmetic Evaluation
堆栈据说是算术求值的理想数据结构。为什么会这样？
为什么我们甚至需要用于算术评估的数据结构？我已经研究了一段时间了，但仍然感到困惑。我不明白 Prefix 和 Postfix 表达式的用途是什么，因为 Infix 表达式非常可读。
为什么 postfix/prefix over infix 的部分答案得到了很好的解释 here。作为摘要中缀可读但不容易解析
至于这里为什么要用stack是：
1: O(1) 时间内的 push,pop 对评估很有用。
2: push: 把操作数加到栈上。
3：弹出：删除操作数并评估表达式（二进制）
4: 解析后最后的结果只剩下栈
中缀表达式是可读的，是的。但是如果你想写一个可以计算算术表达式的算法，你会怎么做？
取下面的表达式：
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，等等
Postfix（或前缀）符号对于人类来说更难阅读，但对于算法来说更容易操作。我之前的例子在后缀中变成了这个：
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
结果出来了。我们只需要通读一次表达式。因此执行时间是线性的。这比我们尝试直接计算中缀表达式时的二次执行时间要好得多，并且不得不多次阅读它，寻找下一个要执行的操作。
请注意，从中缀到后缀的转换也可以在线性时间内完成，使用所谓的 Shunting Yard 算法，该算法使用两个堆栈。堆栈很棒！
堆栈据说是算术求值的理想数据结构。为什么会这样？
为什么我们甚至需要用于算术评估的数据结构？我已经研究了一段时间了，但仍然感到困惑。我不明白 Prefix 和 Postfix 表达式的用途是什么，因为 Infix 表达式非常可读。
为什么 postfix/prefix over infix 的部分答案得到了很好的解释 here。作为摘要中缀可读但不容易解析
至于这里为什么要用stack是：
1: O(1) 时间内的 push,pop 对评估很有用。
2: push: 把操作数加到栈上。
3：弹出：删除操作数并评估表达式（二进制）
4: 解析后最后的结果只剩下栈
中缀表达式是可读的，是的。但是如果你想写一个可以计算算术表达式的算法，你会怎么做？
取下面的表达式：
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，等等
Postfix（或前缀）符号对于人类来说更难阅读，但对于算法来说更容易操作。我之前的例子在后缀中变成了这个：
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
结果出来了。我们只需要通读一次表达式。因此执行时间是线性的。这比我们尝试直接计算中缀表达式时的二次执行时间要好得多，并且不得不多次阅读它，寻找下一个要执行的操作。
请注意，从中缀到后缀的转换也可以在线性时间内完成，使用所谓的 Shunting Yard 算法，该算法使用两个堆栈。堆栈很棒！