Basic Calculator

这里带了括号，不过我们其实能从这两道题明显看出来计算器类型的题目如果想干净优雅的实现，一个result，preVal和sign的记录是必不可少的，自己用Python实现了一遍，原理还是看discussion的java代码更好

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        result, curVal = 0, 0
        sign = 1
        n = len(s)

        for i in xrange(n):
            if s[i].isdigit():
                curVal = 10 * curVal + ord(s[i]) - ord('0')
            elif s[i] == '+':
                result += (sign * curVal)
                curVal = 0
                sign = 1
            elif s[i] == '-':
                result += (sign * curVal)
                curVal = 0
                sign = -1
            elif s[i] == '(':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif s[i] == ')':
                result += (sign * curVal)
                result *= stack.pop()
                result += stack.pop()
                curVal = 0
        return result + sign * curVal

Basic Calculator II

此题主要的问题是要对字符串进行合适的预处理，必须去掉所有空格，包括字符串中间的空格，然后利用preVal和curVal两个变量实现对于乘除法和加减法两种优先级不同的计算符号的处理，另外我们将所有字符串都看做是由0加上当前字符串，所以一开始sign的符号可以设置为加号，每次乘除法时我们不对res进行操作而只是将curVal的值赋到preVal上，而进行加减法时我们再把preVal加到res上且把preVal设置成curVal，下面是代码

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        lst = [x for x in s.strip() if x != ' ']
        preVal = 0
        sign = '+'
        res = 0
        n = len(lst)
        i = 0
        while i < n:
            curVal = 0
            while i < n and lst[i].isdigit():
                curVal = 10 * curVal + ord(lst[i]) - ord('0')
                i += 1
            if sign == '+':
                res += preVal
                preVal = curVal
            elif sign == '-':
                res += preVal
                preVal = -curVal
            elif sign == '*':
                preVal *= curVal
            elif sign == '/':
                preVal = int(float(preVal) / float(curVal))
            if i < n:
                sign = lst[i]
                i += 1

        return res + preVal

Basic Calculator III

Lintcode上面的一道题，这次是加减乘除括号一起上了，只能按照计算器最原始的计算方法即一个数字栈一个符号栈进行计算，同时还需要对符号的优先级进行考虑，如果当前符号优先级没有之前符号栈中的高，则需要把符号栈中的优先级比它高的全部算完，总体思路简单，实现难度太炸了...

class Solution:
    """
    @param: expression: a list of strings
    @return: an integer
    """
    def evaluateExpression(self, expression):
        # write your code here
        numStack, opStack = [], []
        result = 0

        cur = 0
        op = ('+', '-', '*', '/', '(', ')')
        while cur < len(expression):
            curString = expression[cur]
            if curString in op:
                if curString == '(':
                    opStack.append(curString)
                elif curString == ')':
                    while opStack and opStack[-1] != '(':
                        numStack.append(self.cal(numStack.pop(), numStack.pop(), opStack.pop()))
                    opStack.pop()
                else:
                    while opStack and self.precedence(curString, opStack[-1]):
                        numStack.append(self.cal(numStack.pop(), numStack.pop(), opStack.pop()))
                    opStack.append(curString)
            else:
                numStack.append(int(curString))

            cur += 1

        while opStack:
            numStack.append(self.cal(numStack.pop(), numStack.pop(), opStack.pop()))

        return numStack.pop() if numStack else 0

    def cal(self, numA, numB, op):
        if op == '+':
            return numA + numB
        elif op == '-':
            return numB - numA
        elif op == '*':
            return numA * numB
        else:
            return numB / numA

    def precedence(self, stringA, stringB):
        if stringB == '*' or stringB == '/':
            return True
        if stringB == '+' or stringB == '-':
            return stringA != '*' and stringA != '/'
        return False