给定一个逆波兰表达式,求表达式的值。 数据范围:表达式长度满足 1 \le n \le 10^4 \1≤n≤10 4 用pyton写一个波兰表达式,表达式中仅包含数字和 + ,- , * , / ,其中数字的大小满足 |val| \le 200 \∣val∣≤200 。
时间: 2024-05-15 21:14:17 浏览: 51
可以使用栈来求解逆波兰表达式,遍历表达式,遇到数字则入栈,遇到运算符则从栈中弹出两个数字进行计算,并将计算结果压入栈中,最终栈中只剩下一个元素,即为表达式的值。
Python 代码如下:
```python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
stack.append(int(token))
else:
num2 = stack.pop()
num1 = stack.pop()
if token == '+':
stack.append(num1 + num2)
elif token == '-':
stack.append(num1 - num2)
elif token == '*':
stack.append(num1 * num2)
elif token == '/':
stack.append(int(num1 / num2))
return stack[-1]
```
时间复杂度:遍历一遍表达式,时间复杂度为 O(n)。
空间复杂度:最坏情况下栈中存储所有数字,空间复杂度为 O(n)。
阅读全文