逆波兰表达式求值&&表达式计算器
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 = 22
提示：
1 <= tokens.length <= 104 tokens[i] 是一个算符（”+”、”-”、”*” 或 ”/”），或是在范围 [-200, 200] 内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
栈
题目限制所有的表达式都是合法的，可以使用栈。 将所有的数字全部入栈，碰到符号时，弹出两个栈顶元素，计算结果后入栈。 注意除法只保留整数部分，对于负数的情况需要特殊处理
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
if len(tokens) == 0:
return 0
# 注意一个数的情况
if len(tokens) == 1:
return int(tokens[0])
stack = []
ops = ['+', '-', '*', '/']
c = 0
for token in tokens:
if token in ops:
# print(token, stack)
b = stack.pop()
a = stack.pop()
if token == "+":
c = a + b
elif token == "-":
c = a - b
elif token == "*":
c = a * b
else:
c = int(a/b)
stack.append(c)
else:
stack.append(int(token))
return c2. 表达式计算器的通用套路
能同时解决leetcode 224，227，772
双栈的解法
循环遍历每个元素： 若为空格，跳过 若为左括号，入栈 若为右括号，则计算，直到碰到左括号 若为数字，则入栈 若为符号，则先计算，直到碰到左括号，然后符号入栈
细节需要注意：开头为符号以及括号内开头为符号的情况
class Solution:
def calculate(self, s: str) -> int:
def cal(ops, nums):
if len(ops) == 0:
return
while len(ops) > 0 and ops[-1] != '(' and len(nums) >= 2:
op = ops.pop()
b = nums.pop()
a = nums.pop()
if op == '+':
nums.append(a+b)
if op == '-':
nums.append(a-b)
n = len(s)
if n == 0:
return 0
ops = collections.deque()
nums = collections.deque()
# 若开头为符号，加个0方便计算
if s[0] == '-':
nums.append(0)
i = 0
while i < n:
# print('i', i, '\n')
e = s[i]
if e == ' ':
i += 1
elif e == '(':
ops.append(e)
i += 1
elif e == '+' or e == '-':
# 加入符号前，先做判断，将可以计算的部分先计算结果放入nums栈
cal(ops, nums)
ops.append(e)
# 如果左括号内第一个数是符号，那先补0，方便计算
if i > 0 and s[i-1] == '(':
nums.append(0)
i += 1
elif e == ')':
cal(ops, nums)
op = ops.pop()
i += 1
else:
num = 0
# print("-----", ops, nums)
while i < n and '0' <= s[i] and s[i] <= '9':
num = 10*num + int(s[i])
i += 1
nums.append(num)
# 最后可能存在一个括号外的符号和数字需要计算
cal(ops, nums)
return sum(nums)对于+、-、*、/只需要考虑入栈时候的优先级判断即可, 但是代码细节需要做一些微调
class Solution:
def calculate(self, s: str) -> int:
def get_priority(op):
pair = {
'+': 1,
'-': 1,
'*': 2,
'/': 2
}
return pair[op]
def cal(ops, nums):
if len(ops) == 0:
return
if len(ops) > 0 and ops[-1] != '(' and len(nums) >= 2:
op = ops.pop()
b = nums.pop()
a = nums.pop()
if op == '+':
nums.append(a+b)
if op == '-':
nums.append(a-b)
if op == '*':
nums.append(a*b)
if op == '/':
nums.append(int(a/b))
n = len(s)
if n == 0:
return 0
ops = []
nums = []
# 若开头为符号，加个0方便计算
if s[0] == '-':
nums.append(0)
i = 0
while i < n:
e = s[i]
if e == ' ':
i += 1
elif e == '(':
ops.append(e)
i += 1
elif e in ['+', '-', '*', '/']:
# 加入符号前，先做判断，将可以计算的部分先计算结果放入nums栈
while ops and get_priority(e) <= get_priority(ops[-1]):
cal(ops, nums)
ops.append(e)
# 如果左括号内第一个数是符号，那先补0，方便计算
if i > 0 and s[i-1] == '(':
nums.append(0)
i += 1
elif e == ')':
while ops and ops[-1] != '(':
cal(ops, nums)
op = ops.pop()
i += 1
else:
num = 0
# print("-----", ops, nums)
while i < n and '0' <= s[i] and s[i] <= '9':
num = 10*num + int(s[i])
i += 1
nums.append(num)
# print('i', i, ops, nums)
# 最后可能存在一个括号外的符号和数字需要计算
while ops:
cal(ops, nums)
return sum(nums)