江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第227题：基本计算器II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。 注意: - s 由整数和算符 '+'、'-'、''、'/' 以及 ' ' 组成 - s 表示一个有效的表达式 - 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内 - 题目数据保证答案是一个 32-bit 整数

题目描述

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

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

注意:

  • s 由整数和算符 '+'、'-'、'*'、'/' 以及 ' ' 组成
  • s 表示一个有效的表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

  • 1 <= s.length <= 3 * 10^5
  • s 由整数和算符 '+'、'-'、'*'、'/' 以及 ' ' 组成
  • s 表示一个有效的表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

解题思路

本题要求实现一个基本计算器，支持加减乘除运算。与基本计算器I不同，本题不需要处理括号，但需要考虑运算符的优先级。

实现这种计算器时，需要处理以下几个关键点：

  1. 提取数字：将连续的数字字符转换为整数
  2. 处理不同优先级的运算符：乘除法优先于加减法
  3. 处理除法向零截断

方法：栈

我们可以使用栈来解决这个问题。栈用于保存需要延迟计算的数值（即处理加减法运算）。具体思路如下：

  1. 遍历字符串，并用一个变量记录当前处理的数字
  2. 当遇到运算符或遍历到字符串末尾时，根据上一个运算符的类型进行相应处理：
    • 如果上一个运算符是+，将当前数字入栈
    • 如果上一个运算符是-，将当前数字的相反数入栈
    • 如果上一个运算符是*，将栈顶元素出栈，乘以当前数字，再将结果入栈
    • 如果上一个运算符是/，将栈顶元素出栈，除以当前数字，再将结果入栈
  3. 重置当前数字为0，记录当前的运算符
  4. 遍历完成后，将栈中所有数字相加，得到最终结果

时间复杂度：O(n)，其中n是字符串的长度。我们需要遍历字符串一次。 空间复杂度：O(n)，最坏情况下所有数字都需要入栈。

代码实现

C# 实现

public class Solution {
    public int Calculate(string s) {
        Stack<int> stack = new Stack<int>();
        int currentNumber = 0;
        char operation = '+'; // 初始操作符为+
        
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            
            if (char.IsDigit(c)) {
                // 处理多位数字
                currentNumber = currentNumber * 10 + (c - '0');
            }
            
            // 遇到操作符或到达字符串末尾时进行计算
            if ((!char.IsDigit(c) && c != ' ') || i == s.Length - 1) {
                switch (operation) {
                    case '+':
                        stack.Push(currentNumber);
                        break;
                    case '-':
                        stack.Push(-currentNumber);
                        break;
                    case '*':
                        stack.Push(stack.Pop() * currentNumber);
                        break;
                    case '/':
                        stack.Push(stack.Pop() / currentNumber);
                        break;
                }
                
                operation = c;
                currentNumber = 0;
            }
        }
        
        // 计算栈中所有数字的和
        int result = 0;
        while (stack.Count > 0) {
            result += stack.Pop();
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        currentNumber = 0
        operation = '+'  # 初始操作符为+
        
        for i, char in enumerate(s):
            if char.isdigit():
                # 将字符转为数字并处理多位数
                currentNumber = currentNumber * 10 + int(char)
            
            # 遇到操作符或到达字符串末尾时进行计算
            if (not char.isdigit() and char != ' ') or i == len(s) - 1:
                if operation == '+':
                    stack.append(currentNumber)
                elif operation == '-':
                    stack.append(-currentNumber)
                elif operation == '*':
                    stack.append(stack.pop() * currentNumber)
                elif operation == '/':
                    # Python的除法结果是浮点数，需要使用int()向零截断
                    stack.append(int(stack.pop() / currentNumber))
                
                operation = char
                currentNumber = 0
        
        # 计算栈中所有数字的和
        return sum(stack)

C++ 实现

class Solution {
public:
    int calculate(string s) {
        stack<int> stack;
        int currentNumber = 0;
        char operation = '+'; // 初始操作符为+
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            
            if (isdigit(c)) {
                // 处理多位数字
                currentNumber = currentNumber * 10 + (c - '0');
            }
            
            // 遇到操作符或到达字符串末尾时进行计算
            if ((!isdigit(c) && c != ' ') || i == s.length() - 1) {
                if (operation == '+') {
                    stack.push(currentNumber);
                } else if (operation == '-') {
                    stack.push(-currentNumber);
                } else if (operation == '*') {
                    int top = stack.top();
                    stack.pop();
                    stack.push(top * currentNumber);
                } else if (operation == '/') {
                    int top = stack.top();
                    stack.pop();
                    stack.push(top / currentNumber);
                }
                
                operation = c;
                currentNumber = 0;
            }
        }
        
        // 计算栈中所有数字的和
        int result = 0;
        while (!stack.empty()) {
            result += stack.top();
            stack.pop();
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言 执行用时 内存消耗 说明
C# 72 ms 38.5 MB 使用栈处理加减乘除的优先级
Python 88 ms 16.2 MB 代码简洁，但由于Python的解释性质稍慢
C++ 8 ms 8.6 MB 性能最优，内存消耗最小

补充说明

代码亮点

  1. 使用栈处理不同优先级的运算符，确保乘除法先于加减法运算
  2. 通过简单的符号变换将减法转换为加法处理（将负数入栈）
  3. 代码结构清晰，遍历一次字符串完成所有计算

优化方向

  1. 预先分配栈空间，减少动态分配的开销
  2. 可以使用字符数组代替字符串，提高访问效率
  3. 可以在遍历过程中直接计算加减法，减少使用栈的空间

解题难点

  1. 处理运算符的优先级，特别是乘除法优先于加减法
  2. 正确解析多位数字
  3. 处理除法的向零截断
  4. 处理字符串中的空格

常见错误

  1. 忘记处理多位数字的情况
  2. 运算符优先级处理错误
  3. 忽略除法需要向零截断的要求
  4. 没有正确处理字符串末尾的数字

相关题目