-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy path2018-11-14-224-Basic-Calculator.py
More file actions
108 lines (93 loc) · 2.87 KB
/
2018-11-14-224-Basic-Calculator.py
File metadata and controls
108 lines (93 loc) · 2.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-11-14 16:59:14
# @Last Modified by: 何睿
# @Last Modified time: 2018-11-14 20:53:36
import re
# Implement a basic calculator to evaluate a simple expression string.
# The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
# Example 1:
# Input: "1 + 1"
# Output: 2
# Example 2:
# Input: " 2-1 + 2 "
# Output: 3
# Example 3:
# Input: "(1+(4+5+2)-3)+(6+8)"
# Output: 23
# Note:
# You may assume that the given expression is always valid.
# Do not use the eval built-in library function.
class Solution(object):
# 通用方法
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
num_stack = []
ope_stack = []
s = re.findall(r'[0-9]+|[+]+|[-]+|[(]|[)]', s)
for item in s:
if item == "(":
ope_stack.append(item)
elif item in ["+", "-"]:
if not ope_stack or ope_stack[-1] == "(":
ope_stack.append(item)
else:
self.sub_calculate(ope_stack, num_stack)
ope_stack.append(item)
elif item == ")":
if ope_stack:
while ope_stack[-1] != '(':
self.sub_calculate(ope_stack, num_stack)
ope_stack.pop()
else:
num_stack.append(int(item))
if ope_stack:
self.sub_calculate(ope_stack, num_stack)
return num_stack[0]
def sub_calculate(self, ope_stack, num_stack):
ope = ope_stack.pop()
if ope in ["+", "-"]:
num_2 = num_stack.pop()
num_1 = num_stack.pop()
if ope == "+":
num_stack.append(num_1+num_2)
if ope == "-":
num_stack.append(num_1-num_2)
class QuickSolution(object):
# 快速方法
def calculate(self, s):
num = 0
sign = 1
stack = []
total = 0
for item in s:
if item.isdigit():
num = num * 10 + ord(item)-ord("0")
elif item == "+":
total += sign*num
sign = 1
num = 0
elif item == "-":
total += sign * num
sign = -1
num = 0
elif item == "(":
stack.append((total, sign))
sign = 1
total = 0
num = 0
elif item == ")":
total += sign*num
pretoatal, presign = stack.pop()
total = pretoatal+presign*total
num = 0
if num:
total += num*sign
return total
if __name__ == "__main__":
so = QuickSolution()
res = so.calculate("1-(5)")
print(res)