1.题目基本信息

1.1.题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

1.2.题目地址

https://leetcode.cn/problems/basic-calculator-ii/description/

2.解题方法

2.1.解题思路

双栈

2.2.解题步骤

第一步，构建维护变量。分别维护计算数字栈和操作符栈

第二步，遍历计算式字符串，并更新维护变量

• 2.1.字符为空，直接跳过

• 2.2.截取连续数字

• 2.3.针对操作字符，弹出opStack顶部优先级大于等于当前操作符优先级的操作符执行计算，并将计算结果加入数字栈；最后将当前字符压入操作符栈

第三步，依次从操作符栈中弹出，执行计算，直到操作符栈为空

3.解题代码

python代码

class Solution:
    def calc(self, num1, num2, op):
        if op == "+":
            return num1 + num2
        elif op == "-":
            return num1 - num2
        elif op == "*":
            return num1 * num2
        elif op == "/":
            return num1 // num2
    
    def calculate(self, s: str) -> int:
        # 思路：双栈
        n = len(s)
        # 运算符的排序字典映射
        map1 = {"+": 0, "-": 0, "*": 1, "/": 1}
        # 第一步，构建维护变量。分别维护计算数字栈和操作符栈
        numStack = []
        opStack = []
        # 第二步，遍历计算式字符串，并更新维护变量
        i = 0
        while i < n:
            if s[i] == " ":
                # 2.1.字符为空，直接跳过
                i += 1
                continue
            elif s[i].isdigit():
                # 2.2.截取连续数字
                r = i
                while r < n and s[r].isdigit():
                    r += 1
                numStack.append(int(s[i:r]))
                i = r
            else:
                # 2.3.针对操作字符，弹出opStack顶部优先级大于等于当前操作符优先级的操作符执行计算，并将计算结果加入数字栈；最后将当前字符压入操作符栈
                while opStack and len(numStack) > 1 and map1[s[i]] <= map1[opStack[-1]]:
                    num2 = numStack.pop()
                    num1 = numStack.pop()
                    opChar = opStack.pop()
                    numStack.append(self.calc(num1, num2, opChar))
                opStack.append(s[i])
                i += 1
        # 第三步，依次从操作符栈中弹出，执行计算，直到操作符栈为空
        while opStack and len(numStack) > 1 :
            num2 = numStack.pop()
            num1 = numStack.pop()
            opChar = opStack.pop()
            numStack.append(self.calc(num1, num2, opChar))
        # print(numStack)
        return numStack[0] if numStack[0] != "-" else -numStack[1]

4.执行结果