227_基本计算器_II

类型：字符串

基本计算器 II 💛 ⭐

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

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

💡 栈

乘除优先于加减，我们考虑先进行所有的乘除运算，并将这些数值放回原表达式，再进行加减。

因此我们可以使用一个栈。加减号后面的数字，我们直接压入栈。乘除号后面的数字，我们取出栈顶元素与其运算后入栈。

具体来说，遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符（第一个数字之前的运算符视为加号）。每次遍历到数字末尾时，根据 preSign 来决定计算方式：

加号：将数字压入栈；
减号：将数字的相反数压入栈；
乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。

最后将栈中的元素累加。

class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        stack = []
        preSign = '+'
        num = 0
        for i in range(n):
            if s[i] != ' ' and s[i].isdigit():
                num = num * 10 + ord(s[i]) - ord('0')
            if i == n - 1 or s[i] in '+-*/':
                if preSign == '+':
                    stack.append(num)
                elif preSign == '-':
                    stack.append(-num)
                elif preSign == '*':
                    stack.append(stack.pop() * num)
                else:
                    stack.append(int(stack.pop() / num))
                preSign = s[i]
                num = 0
        return sum(stack)

时间复杂度：O(n)，空间复杂度：O(1)