逆波兰表示式求值

🎯 问题描述（来源于LeetCode）

描述：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。
    说明：
  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

示例：

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

💻 解题思路

思路1：栈

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack=[]
        for x in tokens:
            try:
                stack.append(int(x))
            except ValueError:
                if x == '+':
                    stack[-2]=stack[-2]+stack[-1]
                    stack.pop()
                elif x == '-':
                    stack[-2]=stack[-2]-stack[-1]
                    stack.pop()
                elif x == '*':
                    stack[-2]=stack[-2]*stack[-1]
                    stack.pop()
                elif x == '/':
                    stack[-2]=int(stack[-2]/stack[-1])
                    stack.pop()
        return stack[0]

思路1：📊 性能分析

提交结果
  • 运行时间：19ms击败6.77%
  • 内存消耗：20.36MB击败52.24%
复杂度验证
  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(N)O(N)

思考