在将中缀表示法转换为后缀表示法时,如何实现/理解运算符的优先顺序/优先级: “*”、“/”、“+”、“-”、“^”、“)”、“(”。
我知道人们可以只看一个算法并解决这个问题,但我不想那样做。我的思维过程应该是怎样的?
最佳答案
运算符优先级是正式中缀语言的约定和属性,用于指示应首先评估哪些操作。较高优先级的操作意味着它应该在较低优先级的操作之前运行。
分组括号不是运算符优先级的一部分。 (请注意,其他类型的括号(例如函数调用括号)可能是,但我假设您在这里没有提到它们)它们用于明确指示操作顺序。括号仅用于指示中缀表示法中的操作顺序。给定语言中运算符优先级约定的目的是避免在大多数情况下使用括号。因此,例如,如果我想将 4 乘以 5,然后将结果加 7,我可以这样写:
4*5+7
这在正常的算术运算符优先级规则下是有效的,因为乘法 ('*') 的优先级高于加法 ('+')。但是如果我想将 3 和 4 相加,然后将这个结果乘以 8,我需要这样写:
(3+4)*8
在这种情况下,我希望操作顺序不同于“高优先级操作优先”的正常顺序。换句话说,仅当我们使用中缀表示法并希望操作以优先顺序以外的顺序执行时,才需要括号。
在标准算术中,求幂 ("^") 具有最高优先级。接下来是乘法和除法(优先级相等),最后是加法和减法。因此,使用这些不带括号的运算符编写的中缀表达式将首先计算所有幂运算,然后计算所有乘法和除法(按从左到右的顺序),最后计算所有加法和减法,同样按从左到右的顺序。
如果要推断未知语言的运算符优先级,则需要查看使用和不使用括号的位置。由于即使在不必要的情况下也可以在任何地方使用括号,这只是一种启发式方法。对于上面的例子,我可以这样写:
((4*5)+7)
这并没有给出关于运算符优先级的提示。这是因为在这种情况下每个二元运算符都有括号,因此假设加法和乘法的优先级不同,至少两个集合中的一个是冗余的。
类似地,看下一个例子:
(3+4)*8
由于括号用于加法而不是乘法,我们可以推断在这种语言中加法的优先级可能低于乘法。否则,括号将是多余的。因此,寻找括号用于和不用于尝试找出未知语言中的运算符优先级的模式。更常见的做法是根据所考虑的语言的正式规范来假定某个优先级。大多数形式语言都有中缀形式的运算符优先级表,以避免这种歧义。
我们从不需要前缀或后缀语言中的括号,因为术语和运算符的顺序已经明确了评估顺序。因此,这个问题实际上是一个特定于中缀语言的问题。
关于algorithm - 将中缀表示法转换为后缀表示法时出现概念性问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31321436/