相对而言，Basic Calculator II更简单一点，所以我们先从Basic Calculator II开始。
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5实现用字符串表示的表达式求值，只包含非负数、加减乘除和空格。
这道题目的直观感受就是我们需要使用栈来实现，且由于乘除的优先级高于加减，所以当遇到乘除时我们需要立即进行计算，当遇到加减时先计算前一个运算符操作的结果，再保存此运算符，不断循环。
自己写的代码很冗长，这里贴出从别人写的帖子借鉴的思路写出来的代码，不需要用到栈，很巧妙：
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
s = re.sub(r'\d+', ' \g<0> ', s)
ops = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.div}
func = ops['+']
expr = s.split()
total = pos = factor1 = 0
func = ops['+']
while pos < len(expr):
element = expr[pos]
if element in '+-':
total = func(total, factor1)
func = ops[element]
elif element in '*/':
pos += 1
factor2 = int(expr[pos])
factor1 = ops[element](factor1, factor2)
else:
factor1 = int(expr[pos])
pos += 1
return func(total, factor1)
Basic Calculator：
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 .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23实现包含括号、非负数与加减的表达式求值，与前一题的思路很类似，只是这里因为括号的存在需要用到栈，代码如下：
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
ops = {'+': operator.add, '-': operator.sub}
operator_stack = []
value_stack = []
length = len(s)
pos = 0
value_stack.append(0)
operator_stack.append('+')
while pos < length:
if s[pos] == ' ':
pos += 1
continue
elif s[pos] == '(':
operator_stack.append(s[pos])
value_stack.append(0)
operator_stack.append('+')
elif s[pos].isdigit():
factor = 0
while pos < length and s[pos].isdigit():
factor = factor * 10 + int(s[pos])
pos += 1
pos -= 1
value_stack.append(factor)
elif s[pos] in '+-':
factor2 = value_stack.pop()
factor1 = value_stack.pop()
factor = ops[operator_stack.pop()](factor1, factor2)
value_stack.append(factor)
operator_stack.append(s[pos])
elif s[pos] == ')':
factor2 = value_stack.pop()
factor1 = value_stack.pop()
factor = ops[operator_stack.pop()](factor1, factor2)
operator_stack.pop()
value_stack.append(factor)
pos += 1
return ops[operator_stack.pop()](value_stack[0], value_stack[1])