# LeetCode: 227. 基本计算器 II¶

## 1、题目描述¶

输入: "3+2*2"



输入: " 3/2 "



输入: " 3+5 / 2 "



• 你可以假设所给定的表达式都是有效的。
• 请**不要**使用内置的库函数 eval

## 2、解题思路¶

​ 一般的，遇到这样的都能够使用栈来做，我们维护两个栈，一个栈存放数字，另一个栈存放运算符，因为乘法和除法的运算优先级比较高，那么我们在第一遍进行扫描的时候，就将乘除法计算出来，最后，运算符栈中剩下的就是加减法，这时候，每一次取出一个符号，就对数字栈的最后两个元素进行运算即可

class Solution:
def calculate(self, s):
"""
:type s: str
:rtype: int
"""

nums = []
sign = []

all_num = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
all_signs = {"+": 10, "-": 11, "*": 12, "/": 13}

calculate = False

current_sign = -1

for i in s:
if calculate and i in all_num:
if current_sign == all_signs["*"]:
nums[-1] = nums[-1] * all_num[i]

else:
nums[-1] = nums[-1] // all_num[i]
calculate = False
continue
if i in all_num:
nums.append(all_num[i])

if i in all_signs:
if all_signs[i] < all_signs["*"]:
sign.append(all_signs[i])
else:
current_sign = all_signs[i]
calculate = True

for i in range(len(sign) - 1, -1, -1):
num = nums.pop()
if sign[i] == all_signs["+"]:
nums[-1] = nums[-1] + num
else:
nums[-1] = nums[-1] - num

return nums[0]

print(Solution().calculate("1+2+3*6"))


​ 直接写出来，思路没啥问题，不过没理解好，如果是多位数字的话，需要判断的。。。

​ 上面写出来的是一位的数字的情况

​ 如果有多位数的话，还是将表达式转换成后缀表达式再来做

class Solution:
def calculate(self, s):
"""
:type s: str
:rtype: int
"""

nums = []
sign = []

expression = []

all_num = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
all_signs = {"+": 10, "-": 11, "*": 12, "/": 13}
low_priority = {"+": 10, "-": 11}
high_priority = {"*": 12, "/": 13}

is_num = False

for i in s:
if i in all_num:
if is_num:
expression[-1] = expression[-1] + i
else:
expression.append(i)
is_num = True

if i in all_signs:
is_num = False

if sign:
if sign[-1] in high_priority:
expression.append(sign.pop())

if sign and i in low_priority:
expression.append(sign.pop())

sign.append(i)

expression.extend(reversed(sign))

if len(expression) <= 0:
return 0
print(expression)

for i in expression:
if i not in all_signs:
nums.append(int(i))
else:
num = nums.pop()
if i == "+":
nums[-1] += num
elif i == "-":
nums[-1] -= num
elif i == "*":
nums[-1] *= num
elif i == "/":
nums[-1] //= num

return nums[-1]


​ 终于通过了，关于运算符的优先级的判断这需要注意