题目如下：

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 .The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].Some examples:"1 + 1" = 2" 6-4 / 2 " = 4"2*(5+5*2)/3+(6/2+8)" = 21"(2+6* 3+5- (3*14/7+2)*5)+3"=-12 Note: Do not use the eval built-in library function.

 

解题思路：算法上没有什么技术难度，无非就是要考虑各种情况。我的方法是用两个栈分别保存运算符号和非运算符号(包括数字和括号)。遇到右括号后，往前找左括号，遇到乘号或者除号，直接计算出结果。

代码如下：（写的很乱，也没心情优化了）

class Solution(object):    operator = []    num = []    def calcMandD(self,v):        if len(self.operator) == 0 or len(self.num) == 0:            return False         if (self.operator[-1] == '*' or self.operator[-1] == '/') and (self.num[-1] != '(' and self.num[-1] != ')'):            if self.operator[-1] == '*' :                tmp = int(self.num[-1]) * int(v)                self.num[-1] = str(tmp)            else:                tmp = int(self.num[-1]) / int(v)                self.num[-1] = str(tmp)            del self.operator[-1]            return True        return False    def calcParentheses(self):        t1 = self.num[-1]        del self.num[-1]                tn = []        to = []                tn.append(t1)                while self.num[-1] != '(':            t2 = self.num[-1]                        to.insert(0, self.operator[-1])            tn.insert(0, t2)            del self.operator[-1]            del self.num[-1]        del self.num[-1] #del (                        t1 = tn[0]        del tn[0]        while len(tn) > 0:            t2 = tn[0]            if to[0] == '+':                t1 = int(t1) + int(t2)            elif to[0] == '-':                t1 = int(t1) - int(t2)            del to[0]            del tn[0]                return str(t1)        #self.num.append(str(t1))    def calcAandM(self):        t1 = self.num[0]        del self.num[0]        while len(self.num) > 0:            t2 = self.num[0]            if self.operator[0] == '+':                t1 = int(t1) + int(t2)            elif self.operator[0] == '-':                t1 = int(t1) - int(t2)            del self.operator[0]            del self.num[0]        return int(t1)                    def calculate2(self, s):         n = ''        for i in s:            if i == ' ':                continue            if i == '+' or i == '-' or i == '*' or i == '/':                if n != '':                    if self.calcMandD(n) == False:                        self.num.append(n)                n = ''                self.operator.append(i)                continue            if i == '(':                if n != '':                    self.num.append(n)                n = ''                self.num.append(i)                continue            if i == ')':                if n != '':                    if self.calcMandD(n) == False:                        self.num.append(n)                n = ''                ret = self.calcParentheses()                while len(self.operator) >0 and (self.operator[-1] == '*' or self.operator[-1] == '/') and (self.num[-1] != '(' and self.num[-1] != ')'):                    if self.operator[-1] == '*':                        #print self.num                        #print self.operator                        ret = int(self.num[-1]) * int(ret)                    else:                        ret = int(self.num[-1])/int(ret)                    del self.operator[-1]                     del self.num[-1]                self.num.append(ret)                                                    continue            if i>='0' and i <= '9':                n += i        if n!='':            if self.calcMandD(n) == False:                self.num.append(n)                      def calculate(self, s):        """        :type s: str        :rtype: int        """        self.operator = []        self.num = []        self.calculate2(s)        #print (self.operator)        #print (self.num)        return self.calcAandM()