题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

1.问题理解

逆波兰表达式是一种后缀表达式，特点就是将运算符置于操作数之后，从而无需括号就能明确运算顺序，例如：

  • 中缀表达式(2+1)*3 对应的逆波兰表达式为["2", "1" , "+" , "3" , "*"]

2.核心算法：栈

1.初始化空栈：用于存储操作数

2.遍历表达式：

  • 遇到数字，加入栈中

  • 遇到运算符：弹出栈顶两个元素，按运算符计算，将结果压回栈中

3.返回结果：遍历结束后，栈中唯一的元素即为最终结果

示例解析：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

压入4,13,5到栈中，遇到/ 弹出5,13 ，计算 13 / 5 = 2 ->压入2 到栈中，遇到+ ->弹出 2 和 4，计算 4 + 2 = 6

3.关键点和边界条件

  • 除法处理​：Python 中 / 是浮点除法，需用 int(x/y) 或 // 实现向零截断（如 6 / -132 = -0.045... → 0）同时 python 默认// 为向下整除（负无穷方向），比如 6 // -132 = -1 ，所以需要再特殊处理负数向 0 取整

  • ​负数处理​：需正确解析负数字符串（如 "-11"）

  • 操作数顺序​：减法和除法需区分左右操作数（如 b - a 而非 a - b）

from operator import add,sub,mul

# 正负号整除的两种情况
def div(x,y):
    return int(x/y) if x*y >0 else -(abs(x) // abs(y))

class Solution:

    op_map = {'+':add,'-':sub,'*':mul,'/':div}

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+','-','*','/'}:
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1,op2))
        return stack.pop()