中缀表达式转后缀表达式时如何处理括号前的负号？

问题根源 #

常规中缀转后缀算法默认所有-都是二元减法运算符，但你遇到的是一元负号（表示对后续表达式取反），两者的优先级和运算规则完全不同，直接按二元运算符处理会导致后缀表达式结构错误，无法正常求值。

具体解决方法 #

1. 区分一元负号与二元减号 #

在转换前或转换过程中，明确标记一元负号：

• 判断规则：当-满足以下任一条件时，即为一元负号：
  • 位于表达式的开头（如-3+5）
  • 紧跟在左括号(之后（如3*(-(3+2))）
  • 紧跟在其他运算符（+、-、*、/）之后（如3*-(3+6/2)）
• 标记方式：可以用特殊符号（比如~）替换一元负号，避免和二元减号混淆。例如：
  • 3*-(3+6/2) → 3*~(3+6/2)
  • 3*(-(3+6/2)) → 3*(~(3+6/2))

2. 调整中缀转后缀的运算符优先级 #

给一元负号设置高于乘除的优先级（符合数学运算规则），修改转换算法的入栈/出栈逻辑：

• 当遇到一元负号时，直接入栈，直到遇到优先级更低的运算符或右括号时再弹出到输出队列。
• 二元减号的优先级保持和加法一致，低于乘除。

3. 修改后缀表达式的求值逻辑 #

常规求值逻辑是遇到二元运算符时弹出两个操作数计算，针对一元负号需要调整：

• 当遇到一元负号标记（如~）时，只弹出一个操作数，取其相反数后重新压入栈中。

实例演示 #

以3*-(3+6/2)为例：

1. 预处理后为3*~(3+6/2)
2. 转换为后缀表达式：3 3 6 2 / + ~ *
3. 求值过程：
   • 依次压入3、3、6、2 → 栈：[3, 3, 6, 2]
   • 遇到/：弹出6和2，计算6/2=3，压入 → 栈：[3, 3, 3]
   • 遇到+：弹出3和3，计算3+3=6，压入 → 栈：[3, 6]
   • 遇到~：弹出6，计算-6，压入 → 栈：[3, -6]
   • 遇到*：弹出3和-6，计算3*-6=-18 → 最终结果正确

另一种无标记的实时判断方案 #

如果不想用特殊符号标记，也可以在转换过程中实时判断-是否为一元运算符：

• 遍历表达式时，每遇到-就检查其前一个字符的类型，符合一元负号规则时，按一元运算符的优先级和入栈逻辑处理，否则按二元减号处理。

内容的提问来源于stack exchange，提问作者legionary7931