LeetCode[150] 逆波兰表达式求值

1 逆波兰表达式求值

1.1 题目描述

        根据逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

        注意：两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

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

示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5

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

1.2 思路分析

        如(3+4)*5-6的逆波兰表达式为3 4 + 5 * 6 -
        1. 将表达式3 4 + 5 * 6 -放到List中（方便遍历）
        2. 将List传递给一个方法，用于计算
        3. 拿到List后，从左至右开始遍历，遇到数字直接压入栈
        4. 遇到运算符，弹出栈顶和次顶的元素，进行计算，将得到的结果再次放入栈中
        5. 一直重复，直到List遍历完毕，可得到最终结果

复杂度分析

• 时间复杂度：\(O(n)\)，其中\(n\)是数组tokens的长度。需要遍历数组tokens一次，计算逆波兰表达式的值。
• 空间复杂度：\(O(n)\)，其中\(n\)是数组tokens的长度。使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。

1.3 代码实现

        Python中的运算符函数：
方法一：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operand_stack = []
        op_to_binary_fn = {
            "+": add,
            "-": sub,
            "*": mul,
            "/": lambda x, y: int(x / y)
        }       # 定义运算符              
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                operand2 = operand_stack.pop()
                operand1 = operand_stack.pop()
                num = op_to_binary_fn[token](operand1, operand2)
            finally:
                operand_stack.append(num)
        
        return operand_stack.pop()

方法二：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operand_stack = []
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                operand2 = operand_stack.pop()
                operand1 = operand_stack.pop()
                num = self.doMatch(token, operand1, operand2)
            finally:
                operand_stack.append(num)
        
        return operand_stack.pop()

        
    def doMatch(self, op, op1, op2):        # 自定义运算规则
        if op == "*":
            return op1 * op2
        elif op == "/":
            return int(op1/op2)
        elif op == "+":
            return op1 + op2
        else:
            return op1 - op2

        看了其他人的解题思路，一般就是在运算符上操作不同，有的使用eval()函数。
解题心得：
问题一：
        Python 中没有一个函数可以判断一个字符串是否为合理的整数（包括正、负数）。str.isdigit()可以判断正数，但是无法判断负数。
        使用int()函数，并做try-except。

• 如果是整数，那么可以用int()转成数字；
• 如果是运算符，那么int()会报错，从而进入 except中。

        整数字符串的最后一位肯定是数字，也可以以此来区分数字和运算符。

if token[-1].isdigit():
    stack.append(int(token))
else:
    pass    # 处理运算符

补充知识点：
operator 模块