[LeetCode]150. 逆波兰表达式求值(Evaluate Reverse Polish Notation)

题目描述

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

输入: [“2”, “1”, “+”, “3”, “*“]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2:

输入: [“4”, “13”, “5”, “/“, “+”]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3:

输入: [“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
= 22

解题思路

使用栈,将整数依次入栈,遇到运算符时出栈两个做运算,把计算结果入栈,直到结束。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def __init__(self):
self.stack = []

def evalRPN(self, tokens: List[str]) -> int:
if len(tokens) == 1:
return int(tokens[0])
operator = ["+", "-", "*", "/"]
for token in tokens:
if token not in operator:
self.stack.append(int(token))
else:
num2 = self.stack.pop()
num1 = self.stack.pop()
if token == "+":
res = num1 + num2
elif token == "-":
res = num1 - num2
elif token == "*":
res = num1 * num2
else:
res = int(num1 / num2)
self.stack.append(res)
return res

执行用时: 64 ms
内存消耗: 12.8 MB