数据结构：后缀表达式：结合性 (Associativity) 与一元运算符 (Unary Operators)
目录
结合性 (Associativity)：解决同级操作符的“站位”问题
问题的引出
结论：对原有规则的精炼
一元运算符 (Unary Operators)：解决符号的“身份”问题
问题的引出
如何区分一元和二元操作符？
如何将一元运算符整合进我们的转换算法？
结论：对原有算法的扩展
手动转换示例：a * (-b + c)
我们接着上一次的内容，深入探讨在处理表达式时必须面对的两个更精细的问题：结合性 (Associativity) 和 一元运算符 (Unary Operators)。
数据结构：中缀到后缀的转换（Infix to Postfix Conversion）-CSDN博客
结合性 (Associativity)：解决同级操作符的“站位”问题
问题的引出
我们上次得出的规则是：
当新操作符的优先级低于或等于栈顶操作符时，就将栈顶操作符弹出。
这个规则在处理 a + b * c 时工作得很好。
但我们来思考一个新情景：8 - 5 + 3。 这里的 - 和 + 优先级完全相同。按照我们已有的规则来手动转换：
-
读到
8：输出8。 -
读到
-：操作符栈为空，压入-。栈：[-]。 -
读到
5：输出8 5。 -
读到
+：新操作符+的优先级与栈顶的-相等。根据“低于或等于就弹出”的规则，我们将-弹出。-
输出变为
8 5 -。 -
操作符栈变为空，然后压入
+。栈：[+]。
-
-
读到
3：输出8 5 - 3。 -
字符串结束：弹出栈中剩余的
+。最终结果：8 5 - 3 +。
我们来验算一下这个后缀表达式：8 5 - 得到 3，然后再计算 3 3 + 得到 6。 这个结果，其实等价于我们先计算了 (8 - 5) 再加上 3。
这个 (8 - 5) + 3 的计算顺序不是凭空来的。这是我们在数学中一个根深蒂固但可能没注意到的隐性规则：
对于
+、-、*、/这些操作符，当它们优先级相同时，我们总是从左到右依次计算。
这个“从左到右”的组合规则，就叫做左结合性 (Left-to-Right Associativity)。
我们的转换算法中“等于就弹出”这一条，恰好就完美地、自动地实现了左结合性。
因为当遇到同级操作符时，它总是让先出现（在左边）的操作符先被弹出并输出，从而保证了它在后缀表达式中也更靠前，也就被先计算。
现在，引出新的问题：是不是所有操作符都是左结合的？
思考一下幂运算 ^。表达式 2 ^ 3 ^ 2 应该如何计算？
-
方案A（左结合）：
(2 ^ 3) ^ 2=8 ^ 2=64 -
方案B（右结合）：
2 ^ (3 ^ 2)=2 ^ 9=512
在绝大多数编程语言和数学约定中，幂运算是右结合的，也就是方案B。赋值运算符 = 也是一个典型的右结合操作符（例如 a = b = 5 的意思是 a = (b = 5)）。
如果我们对 ^ 仍然使用“等于就弹出”的规则，当第二个 ^ 遇到栈顶的第一个 ^ 时，它会把第一个 ^ 弹出去，这就导致了左结合的计算顺序，这对于幂运算是错误的。
为了正确处理右结合操作符，我们必须修改规则：
-
对于右结合操作符，当新来的操作符与栈顶的操作符优先级相等时，我们不应该弹出栈顶的那个，而是应该让新来的也压入栈中，因为它应该“等待”更右边的运算先完成。
-
换句话说，只有当新来的操作符优先级严格地低于栈顶的右结合操作符时，才把它弹出来。
结论：对原有规则的精炼
我们的操作符优先级比较规则，必须同时考虑结合性：
-
当新操作符
op2和栈顶操作符op1比较时：-
如果
op1的优先级 >op2的优先级，则弹出op1。 -
如果
op1的优先级 <op2的优先级，则压入op2。 -
如果
op1的优先级 ==op2的优先级：-
并且
op1是左结合的，则弹出op1。 -
并且
op1是右结合的，则压入op2。
-
-
结合性 (Associativity) 的本质，是为同优先级操作符提供了一个解决歧义的“方向”规则。
一元运算符 (Unary Operators)：解决符号的“身份”问题
问题的引出
到目前为止，我们处理的所有操作符 +, -, *, / 都是二元运算符 (Binary Operators)，因为它们都需要两个操作数。
现在看这个表达式：3 * -5。 这里的 - 是什么意思？
它不是“减法”，因为它的右边是 5，但左边是 *，而不是一个数字。这个 - 的作用是“取负”，它只作用于一个操作数 5。
这种只作用于一个操作数的操作符，就叫做一元运算符 (Unary Operator)。
这立刻带来了一个巨大的问题：符号 - 现在有了双重身份。它可以是“二元减”，也可以是“一元负”。我们的算法在读到一个 - 时，必须先搞清楚它的身份，才能决定如何处理。
如何区分一元和二元操作符？
答案是看它的上下文，也就是它出现的位置。
-
一个操作符是二元的，如果它的前面是一个操作数（数字）或者一个右括号
)。-
例如：
10 - 5(-前面是10)，(a+b) - c(-前面是))
-
-
一个操作符是一元的，如果它的前面什么都没有（它是表达式的第一个字符），或者它的前面是另一个操作符，或者是一个左括号
(。-
例如：
-5(前面什么都没有)，3 * -5(-前面是*)，10 + (-5)(-前面是()
-
如何将一元运算符整合进我们的转换算法？
-
身份识别：在我们的扫描程序中，当遇到一个有歧义的符号（如
-或+）时，我们必须先通过上述的上下文规则来判断它的“身份”。 -
赋予独立的属性：为了在算法中清晰地处理，我们可以把“一元负”看作一个全新的、独立的操作符。为了方便，我们可以在内部给它起个别名，比如用
~来代表一元负。-
这样
3 * -5在内部就被预处理成了3 * ~5。
-
-
确定一元操作符的优先级和结合性：
-
优先级：在
3 * -5中，我们必须先计算-5（也就是~5），然后再进行乘法。这意味着一元运算符的优先级非常高，必须高于*和/。 -
结合性：在
- - 5中，它的意思是- (-5)，结果是5。计算顺序是从右到左。所以，一元运算符是右结合的。
-
结论：对原有算法的扩展
为了处理一元运算符，我们的转换过程需要增加一个预处理步骤，或者在主循环中增加判断逻辑：
-
在扫描时：当遇到
+或-，通过检查它前面的字符，来确定它是二元还是。 -
在操作符栈中：如果确定是“一元负”，就把它当作一个具有高优先级和右结合性的特殊操作符（如
~）来处理。
手动转换示例：a * (-b + c)
-
预处理/识别：
a * ( ~b + c )，我们将括号内的-识别为一元负~。 -
开始转换：
| 当前字符 | 操作符中转站（栈） | 后缀表达式结果 | 解释 |
a | [] | a | 操作数，输出 |
* | [*] | a | 栈空，* 入栈 |
( | [*, (] | a | ( 直接入栈 |
~ | [*, (, ~] | a | 栈顶是(，~直接入栈 (~优先级高) |
b | [*, (, ~] | a b | 操作数，输出 |
+ | [*, (, +] | a b ~ | +优先级低于~，弹出~；然后+入栈 |
c | [*, (, +] | a b ~ c | 操作数，输出 |
) | [*] | a b ~ c + | 遇到)，弹出+，丢弃( |
| 末尾 | [] | a b ~ c + * | 弹出栈中剩余的* |
最终结果：a b ~ c + *。这个结果正确地表达了先计算 b 的负值，然后与 c 相加，最后再与 a 相乘的顺序。