代码随想录算法训练营第六天 补卡|150.逆波兰表达式求值

150.逆波兰表达式求值https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html·题意计算机进行数值运算的操作为二叉树的后序遍历表达式。·核心思想判断符合条件则出栈运算。相似题目有效的括号、删除重复字符。·易错点1操作数运算顺序出栈顺序与运算操作数顺序的不同可能导致运算错误针对除法和减法出栈顺序为右侧先出作为计算的第一个操作数。如5,2,/计算机运算为5/2。出栈顺序为25运算为2/5需要逆置顺序。2除法运算向零取值分为操作数为同号、异号的结果。除法则又分为浮点型除法a/b、地板除法a//b。需根据向零取整重定义除法运算。·浮点除法与地板除法浮点除法a/b 得出正常取值。int(a/b)转整型同号则为正int(a/b)向下取值为向零取值。eg: 5/22.5, int(5/2)int(2.5)2 向下取值向零取值;异号则为负int(a/b)向上取值为向零取值. eg: 5/(-2)-2.5, int(5/(-2))int(-2.5)-2向上取值向零取整。地板除法a//b 得出向下取值。同号则向下取值为向零取值 eg:5/22.5,5//22向下取值为向零取值。异号则向下取值结果越小,通过绝对值处理可将异号除法向零取整:-(abs(a)/abs(b))eg:5/(-2)-2.5, 5//(-2)-3 向下取值为更负-(abs(5)//abs(-2))-2 向上取值向零取整 也可直接在(a//b)1·向零截断取整法的定义及处理通过操作数、结果、已有除法的处理来进行操作数为同号结果为正向下取值为向零取值。 int(a/b) a//b均满足操作数为异号结果为负向下取值结果越小。向零取整可通过对操作数处理、对结果处理。int(a/b)满足。a//b会更负需处理。代码(1)重定义除法:#除法向0取整含同号、异号相除 def div(a:int, b:int)-int: return int(a/b) if a * b 0 else -(abs(a)//abs(b)) #return int(a/b) #return a//b if a*b 0 else (a//b)1(2)波兰表达式求值from operator import add, sub, mul #除法向0取整含同号、异号相除 def div(a:int, b:int)-int: return int(a/b) if a * b 0 else -(abs(a)//abs(b)) #return int(a/b) #return a//b if a*b 0 else (a//b)1 class Solution: def evalRPN(self, tokens: List[str]) - int: op_map {:add, -:sub, *:mul, /:div} st0 [] for token in tokens: if token not in {, -, *, /}: st0.append(int(token))#原始均为字符遇到数字转整数运算 else: num2 st0.pop()#先弹出的操作数作为右操作数按运算逻辑来说属于第二个数 num1 st0.pop()#后出的元素作为左操作数(被除数\被减数) st0.append(op_map[token](num1, num2))#取哈希函数运算 return st0.pop()