将中缀表示法转换为后缀表示法时出现概念问题

Question

在将中缀表示法转换为后缀表示法时，如何认识/理解运算符的优先顺序/优先顺序：“*”、“/”、“+”、“-”、“^”、“)”、“(”。

我知道人们可以只看一个算法来解决这个问题，但我不想这样做。我的思维过程应该是怎样的？

Answer 1

运算符优先级是一种约定，也是一种正式infix语言的属性，用来指示应该首先计算哪些操作。较高的优先级操作意味着它应该在较低优先级的操作之前操作。

分组括号不是运算符优先级的一部分。(请注意，其他类型的括号，如函数调用括号，可能是，但我假设您在这里不是指那些)，它们用于显式地指示操作的顺序。括号仅用于指示中缀表示法中的操作顺序。给定语言中运算符优先约定的目的是避免在大多数情况下使用括号。例如，如果我想用4乘以5，然后在结果上加上7，我可以这样写：

4*5+7

这在普通算术运算符优先规则下是有效的，因为乘法('*')比加法('+')具有更高的优先级。但是，如果我想将3和4相加，然后将结果乘以8，我需要这样写：

(3+4)*8

在这种情况下，我希望操作的顺序不同于“高优先级操作优先”的正常顺序。换句话说，只有当我们使用中缀表示法并希望操作按优先顺序以外的顺序执行时，括号才是必要的。

在标准算术中，求幂("^")具有最高优先级。接下来是乘法和除法(优先级相等)，最后是加法和减法。因此，使用这些运算符编写的不带括号的中缀表达式将首先计算所有求幂，然后计算所有乘法和除法(按从左到右的顺序)，最后再按从左到右的顺序计算所有加法和减法。

如果要推断未知语言的运算符优先级，则需要查看使用和不使用括号的位置。由于在任何地方使用括号都是有效的，即使在不必要的情况下也是如此，所以这只是一种启发式方法。对于上面的例子，我可以这样写：

((4*5)+7)

这并没有给出任何关于运算符优先级的提示。这是因为在这种情况下，每个二元运算符都有括号，因此假设加法和乘法的优先级不同，两个集合中至少有一个是冗余的。

类似地，查看下一个示例：

(3+4)*8

由于加法前后使用了括号，但乘法没有，因此我们可以推断，在这种语言中，加法的优先级可能低于乘法。否则，括号将是多余的。因此，寻找在未知语言中使用和不使用括号的模式，试图找出运算符的优先顺序。更常见的情况是，基于所考虑的语言的正式规范来假定某个优先级别。大多数正式语言都有一个中缀形式的运算符优先顺序图，以避免这种歧义。

我们永远不需要在前缀或后缀语言中使用括号，因为术语和运算符的顺序已经明确了计算的顺序。因此，这个问题实际上是一个特定于infix语言的问题。

Answer 2

如果圆括号被正确地平衡，你总是可以找到一个没有括号的子表达式，这可以将问题减少到这种情况。

现在问问你自己，根据优先规则，这样的表达式中应该首先执行哪种操作？