36 - Hard - 基本计算器 II

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

思路：先顺序提取了数字和符号，然后顺序遍历符号，+-直接操作，*/需要回退+-的操作

def add(x, y):
    return x + y


def sub(x, y):
    return x - y


def mul(x, y):
    return x * y


def div(x, y):
    return x // y


class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = list(filter(lambda x: x != " ", s))
        _calculator = {"*": mul, "/": div, "+": add, "-": sub}
        _digits = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
        num_list  = []
        symbol_list = []
        temp_num = 0
        is_still_digit = False
        for i in s:
            if i in _digits:  # 数字
                if is_still_digit:
                    temp_num *= 10
                is_still_digit = True
                temp_num += _digits[i]
            else:  # 数字结束
                num_list.append(temp_num)
                temp_num = 0
                is_still_digit = False
                symbol_list.append(i)
        num_list.append(temp_num)
        # 至此，数字和符号提取完毕
        # 如："3+5/2"
        # 则num_list = [3, 5, 2]
        # 则symbol_list = ['+', '/']
        last_num = num_list[0]  # 初值：第一个数字
        res = num_list[0]  # 初值：第一个数字
        last_symbol = "+"  # 初值：+，经过回退后res变为0；否则开头连续乘除会有问题
        for k, v in enumerate(symbol_list):  # 顺序遍历符号
            if v in ["+", "-"]:  # 直接操作
                res = _calculator[v](res, num_list[k+1])
                last_num = num_list[k+1]
                last_symbol = v  # 记录上一个加号或者减号
            elif v in ["*", "/"]:
                if last_symbol == "+":  # 回退+
                    res = _calculator["-"](res, last_num)
                elif last_symbol == "-":  # 回退-
                    res = _calculator["+"](res, last_num)
                last_num = _calculator[v](last_num, num_list[k+1])  # 先乘除
                res = _calculator[last_symbol](res, last_num)  # 再利用last_symbol更新res
        return res