Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
模拟加减法计算器,包含+,-,(,),和数字,栈操作,碰到除")"以外的字符都压进栈,碰到")"就把从上一个"("到目前为止的字符算出一个结果压进栈,处理完第一遍之后此时栈内已无括号,再从左到右计算一次即可,写得比较繁琐,运行效率一般

 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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理