难度: Medium
给你一个字符串表达式 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 * 105s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开s 表示一个 有效表达式[0, 231 - 1] 内运行时间: 68 ms
内存: 0.0 MB
class Solution:
def calculate(self, s: str) -> int:
nums = []
cur = 0
op = "+"
for i in s+"+":
if i.isdigit():
cur = cur*10+int(i)
elif i in "+-*/":
if op == "+":
nums.append(cur)
elif op =="-":
nums.append(-cur)
elif op == '*':
nums[-1] = nums[-1]*cur
# nums.append(nums.pop()*cur)
elif op == "/":
if nums[-1]>0:
nums[-1] = nums[-1]//cur
else:
nums[-1] = 0-(abs(nums[-1])//cur)
op = i
cur = 0
print(nums)
return sum(nums)
这个题解使用了一个栈来模拟计算过程。遍历字符串 s 中的每个字符，如果当前字符是数字，则更新当前数 cur；如果当前字符是运算符，则根据上一个运算符 op 来决定如何处理当前数，并更新上一个运算符为当前运算符。具体来说： 1. 如果上一个运算符是加号，则将当前数压入栈； 2. 如果上一个运算符是减号，则将当前数的相反数压入栈； 3. 如果上一个运算符是乘号，则将栈顶元素弹出，与当前数相乘后压入栈； 4. 如果上一个运算符是除号，则将栈顶元素弹出，与当前数相除后压入栈，注意处理除数为负数的情况。 最后将栈中所有元素求和即为最终结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def calculate(self, s: str) -> int:
nums = []
cur = 0
op = "+"
for i in s+"+":
if i.isdigit():
# 如果当前字符是数字，则更新当前数 cur
cur = cur*10+int(i)
elif i in "+-*/":
# 如果当前字符是运算符，则根据上一个运算符 op 来决定如何处理当前数
if op == "+":
nums.append(cur)
elif op =="-":
nums.append(-cur)
elif op == '*':
nums[-1] = nums[-1]*cur
# nums.append(nums.pop()*cur)
elif op == "/":
if nums[-1]>0:
nums[-1] = nums[-1]//cur
else:
nums[-1] = 0-(abs(nums[-1])//cur)
# 更新上一个运算符为当前运算符
op = i
# 重置当前数为 0
cur = 0
print(nums)
# 返回栈中所有元素的和
return sum(nums)
在此算法中，处理运算符和数字的逻辑是在遇到一个新的运算符时才回顾并处理之前的数字和运算符。这意味着字符串末尾的数字和运算符不会被处理，除非有一个新的运算符触发这一处理逻辑。通过在字符串末尾添加一个'+'，算法可以确保最后一个数字也被正确地按之前的运算符处理，而'+'本身不会改变现有结果的总和，因为它只是将最后一个数字正常加入到结果中。
在处理除法时，特别是涉及负数的除法，需要确保结果的符号正确。在Python中，整数除法（//）的结果总是向下取整，即向负无穷方向取整。当被除数是负数的时候，使用0减去正数除法的结果是为了得到正确的商值。例如，`-3 // 2`结果为-2，而我们期望的商应该是更贴近0的-1，所以使用`0 - (abs(-3) // 2)`即`0 - 1 = -1`可得到预期结果。这种做法不会导致结果错误，而是一种确保在负数除法情况下符号正确的技巧。
直接修改栈顶元素而不是先出栈再压入可以减少操作的复杂性和提高一定的效率，因为这避免了不必要的出栈和入栈操作。然而，这种做法的潜在风险在于它修改了栈中的现有元素，这在多线程环境下或在其他需要跟踪元素历史的场景中可能会引发问题。在当前的单线程和简单计算场景中，这种方法是安全且有效的。
这种解法假设输入字符串只包含数字和合法的运算符（`+`, `-`, `*`, `/`），因此它没有处理非法字符的特定逻辑。如果输入包含字母或特殊字符，算法可能会表现出不可预测的行为或抛出错误。在实际应用中，应该在处理输入之前验证并清理数据，确保只包含预期的字符，从而避免运行时错误。