本文共 3440 字，大约阅读时间需要 11 分钟。
相对而言，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)很是精简，这里我们需要做些初始化，使第一个操作数为0，第一个操作符为加号。 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]) 转载地址：http://gmbvb.baihongyu.com/