Posted on 2022-11-20 20:01
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
模拟 、
闲来无事重切Leet Code
模拟加减法计算器,包含+,-,(,),和数字,栈操作,碰到除")"以外的字符都压进栈,碰到")"就把从上一个"("到目前为止的字符算出一个结果压进栈,处理完第一遍之后此时栈内已无括号,再从左到右计算一次即可,写得比较繁琐,运行效率一般
1 #224
2 #Runtime: 640 ms
3 #Memory Usage: 16.7 MB
4
5 class Solution(object):
6 def calculate_brackets_removed(self, stk):
7 pre = 0
8 i = 0
9 while i < len(stk):
10 if stk[i] == '-' and not i:
11 stk[i + 1] = - stk[i + 1]
12 i += 1
13 elif isinstance(stk[i], int):
14 pre = stk[i]
15 i += 1
16 elif (stk[i] == '+' or stk[i] == '-') and i:
17 pre = self.cal(stk[i], pre, stk[i + 1])
18 i = i + 2
19 return pre
20
21 def cal(self, op, a, b):
22 if op == '+':
23 return a + b
24 if op == '-':
25 return a - b
26
27 def calculate(self, s):
28 """
29 :type s: str
30 :rtype: int
31 """
32 stk = []
33 p = 0
34 for i in s:
35 if i == ' ':
36 continue
37 if i == '(':
38 stk.append(i)
39 elif i.isnumeric():
40 if stk and isinstance(stk[-1], int):
41 t = int(stk[-1]) * 10 + int(i)
42 stk.pop()
43 stk.append(t)
44 else:
45 stk.append(int(i))
46 elif i == ')':
47 stk_rev = stk[::-1]
48 idx = len(stk) - (stk_rev.index("(") + 1)
49 t = self.calculate_brackets_removed(stk[idx + 1 : ])
50 del stk[idx : ]
51 stk.append(t)
52 elif i == '+' or i == '-':
53 stk.append(i)
54 return self.calculate_brackets_removed(stk)