算法学习

Appearance

227. 基本计算器 II Medium ​

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

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

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

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

示例 1：
输入：s = "3+2*2"
输出：7

示例 2：
输入：s = " 3/2 "
输出：1

示例 3：
输入：s = " 3+5 / 2 "
输出：5

解题思路 ​

输入：一个字符串表达式 s输出：返回该表达式的计算结果（只包含非负整数和运算符 + - * /，无括号）

本题属于 表达式解析栈 问题。

我们可以通过遍历字符串，结合栈结构和运算符优先级来实现：

思路步骤：

  1. 使用变量 num 构造当前的数字（支持多位数）。

  2. 使用 prev_op 记录上一个运算符，初始设为 '+'，默认第一个数字作为正数处理。

  3. 使用栈 stack 存储每一步的阶段性结果（用于加减/乘除处理顺序）。

  4. 遍历字符串：

    • 如果是数字，就更新 num = num * 10 + int(c)。

    • 如果遇到操作符或到达末尾，就根据 prev_op 来处理当前数字：

      • '+'：将 num 入栈；
      • '-'：将 -num 入栈；
      • '*'：弹出栈顶与 num 相乘后入栈；
      • '/'：弹出栈顶与 num 相除（注意向零取整）后入栈。

    • 更新 prev_op = 当前操作符，并将 num 重置为 0。

  5. 最后返回栈中所有元素的和作为最终结果。

代码实现 ​

python
class Solution:
    def calculate(self, s: str) -> int:
        num = 0                  # 当前正在构建的数字（可能是多位数）
        stack = []               # 栈，用于保存每一段的计算结果
        prev_op = '+'            # 记录上一个操作符，初始为 '+'（默认第一个数为正）

        # 遍历字符串每个字符
        for i in range(len(s)):
            c = s[i]

            # 如果是数字字符，累加到当前数字中
            if c.isdigit():
                num = num * 10 + int(c)

            # 如果遇到操作符（+ - * /），或者到了字符串末尾
            if (not c.isdigit() and c != ' ') or i == len(s) - 1:
                # 根据上一个操作符处理当前的 num
                if prev_op == '+':
                    stack.append(num)  # 加号：当前数字直接入栈
                elif prev_op == '-':
                    stack.append(-num)  # 减号：将当前数字变成负数后入栈
                elif prev_op == '*':
                    stack.append(stack.pop() * num)  # 乘法：弹出栈顶元素乘以当前数字
                elif prev_op == '/':
                    # 除法：注意要向零取整（例如 -3 / 2 应为 -1，而不是 -2）
                    stack.append(int(stack.pop() / num))

                prev_op = c  # 更新当前操作符为这次遇到的操作符
                num = 0      # 重置当前数字，准备读取下一个数

        # 最终栈中所有数字相加得到结果
        return sum(stack)
javascript
/**
 * @param {string} s
 * @return {number}
 */
const calculate = function(s) {
    let num = 0;
    let stack = [];
    let prev_op = '+';

    for (let i in s) {
        const c = s[i];

        if (/[0-9]/.test(c)) num = num * 10 + Number(c);

        if (!/[0-9]/.test(c) && c !== ' ' || i == s.length - 1) {
            if (prev_op == '+') stack.push(num); 
            if (prev_op == '-') stack.push(-num);
            if (prev_op == '*') stack.push(stack.pop() * num);
            if (prev_op == '/') stack.push(parseInt(stack.pop() / num));

            num = 0;
            prev_op = c;
        }
    }

    return stack.reduce((acc, curr) => acc + curr, 0);
};

复杂度分析 ​

时间复杂度：O(n)

空间复杂度：O(n)

链接 ​

227 国际版

227 中文版