227. 基本计算器 II

Difficulty
Hard
Tags
栈
URL
https://leetcode.cn/problems/basic-calculator-ii/
Star
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
  • 1 <= s.length <= 3 * 105
  • s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数
 
本题 参考
🕢
224. 基本计算器

法1 双栈法

思路
参考
🕢
224. 基本计算器 ，本题多了运算符，所以堆运算符号的操作 也相应改变。具体如下：
在遇到运算符号的时候，将当前栈中 运算符 比前的运算符 优先级 高的计算完成，
题解
class Solution:
    def calculate(self, s: str) -> int:
        ops = {"+":0, "-":0, "*":1, "/":1}
        stack_nums = []
        stack_ops = []
        i = 0
        while i < len(s):
            if s[i] == " ":
                i += 1
            elif s[i].isdigit():
                temp = []
                while i < len(s) and s[i].isdigit():
                    temp.append(s[i])
                    i += 1
                stack_nums.append(int("".join(temp)))
            elif s[i] == "(":
                stack_ops.append("(")
                if i < len(s) and s[i+1] in ops:
                    stack_nums.append(0)
                i += 1
            elif s[i] == ")":
                while len(stack_ops) > 0 and stack_ops[-1] != "(":
                    self._calculate(stack_nums, stack_ops)
                stack_ops.pop()
                i += 1
            elif s[i] in ops:
                cur_op = s[i]
                if i == 0:
                    stack_nums.append(0)

                while len(stack_ops) > 0 and ops[stack_ops[-1]] >= ops[cur_op]:
                    self._calculate(stack_nums, stack_ops)
                stack_ops.append(cur_op)
                i += 1   

        while len(stack_ops) > 0:
            self._calculate(stack_nums, stack_ops)

        return stack_nums.pop()

    def _calculate(self, stack_nums, stack_ops):
        if len(stack_nums) < 2 or len(stack_ops) < 1:
            return
        x = stack_nums.pop()
        y = stack_nums.pop()
        op = stack_ops.pop()
        res = None
        if op == "+":
            res = x + y
        elif op == "-":
            res = y - x
        elif op == "*":
            res = x * y
        elif op == "/":
            res = int(y / x)
        
        stack_nums.append(res)