鏈接： 基本計算器
字符串計算器降宅，一種方法是將字符串轉(zhuǎn)換為逆波蘭式（其實是計算樹的后續(xù)遍歷序列）苫耸，然后直接遍歷計算鳞疲。另一種方法是使用兩個棧徽曲，分別存儲操作數(shù)和操作符园欣。
- 遇到(炕矮、+、-直接壓入操作符棧
- 遇到數(shù)字盐茎，通過遍歷兴垦，識別出數(shù)字，壓入操作數(shù)棧
- 遇到)字柠，彈出操作符探越、操作數(shù)，進行計算窑业，直到操作符棧為空或者操作符棧頂是“(”（這種情況需要把棧頂?shù)摹?”出棧）钦幔。
減號、負號的判斷常柄，如果-是第一個字符鲤氢，或者-的前一個字符是)，則這個-是負號西潘，否則就是減號卷玉。
“+”、“-”在操作符入棧前秸架，先把現(xiàn)有棧內(nèi)能計算的都算了揍庄。
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(" ", "")
ops = []
nums = []
index = 0
while index < len(s):
c = s[index]
if c == ")": #遇到)則開始計算，直到操作符棧里遇到(东抹，并將(出棧
while ops:
if ops[-1] != '(':
op = ops.pop()
a = nums.pop()
b = nums.pop()
if op == '+':
nums.append(a+b)
else:
nums.append(b-a)
else:
ops.pop()
break
elif c == "(":
ops.append("(")
elif c == '+': #將一個普通運算符入操作棧之前，先把能計算的的都算了
self.calc(nums, ops)
ops.append("+")
elif c == "-":
if index <= 0 or s[index-1] == "(": #這個-是負號沃测，通過添加一個操作數(shù)0將負號轉(zhuǎn)換成減號
ops.append("-")
nums.append(0)
else: #將一個普通運算符入操作棧之前缭黔，先把能計算的的都算了
self.calc(nums, ops)
ops.append("-")
else:
u = 0
j = index
while j < len(s) and self.is_num(s[j]):
u *= 10
u += ord(s[j]) - ord('0')
j += 1
nums.append(u)
index = j - 1
# print("index:{}, char:{}, ops:{}, nums:{}".format(index, s[index], ops, nums))
index += 1
# 將未計算的操作符和操作數(shù)進行計算，得到最終結(jié)果
self.calc(nums, ops)
return nums[-1]
def is_num(self, c):
if ord('0') <= ord(c) <= ord('9'):
return True
def calc(self, nums, ops):
while len(nums) >= 2 and len(ops) >= 1 and ops[-1] in ("+", "-"):
op = ops.pop()
a = nums.pop()
b = nums.pop()
if op == '+':
nums.append(a+b)
else:
nums.append(b-a)
