Medium

题目描述

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

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

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

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

示例 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 位的整数

解题思路

这道题考查的是表达式求值，需要处理运算符优先级。由于乘除法优先级高于加减法，我们需要特殊处理。

核心思路：

  1. 使用栈来处理运算符优先级问题
  2. 遍历字符串，解析数字和运算符
  3. 对于加减法：直接将数字（或负数）入栈
  4. 对于乘除法：立即与栈顶元素计算，将结果重新入栈

算法步骤：

  1. 初始化栈和变量：num 存储当前数字，sign 存储上一个运算符（初始为’+’）
  2. 遍历字符串的每个字符：
    • 如果是数字：累加到 num
    • 如果是运算符或到达字符串末尾：根据 sign 处理上一个数字
      • ‘+’: 直接入栈
      • ‘-’: 将负数入栈
      • ‘*’: 与栈顶相乘后入栈
      • ‘/’: 与栈顶相除后入栈
  3. 最后将栈中所有数字相加得到结果

这种方法巧妙地利用栈的特性，确保乘除法能够立即计算，而加减法的操作数都保存在栈中最后统一处理。

推荐解法： 单次遍历 + 栈，时间复杂度最优。

代码实现

class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int num = 0;
        char sign = '+';
        
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.length() - 1) {
                if (sign == '+') {
                    stk.push(num);
                } else if (sign == '-') {
                    stk.push(-num);
                } else if (sign == '*') {
                    int top = stk.top();
                    stk.pop();
                    stk.push(top * num);
                } else if (sign == '/') {
                    int top = stk.top();
                    stk.pop();
                    stk.push(top / num);
                }
                sign = s[i];
                num = 0;
            }
        }
        
        int result = 0;
        while (!stk.empty()) {
            result += stk.top();
            stk.pop();
        }
        return result;
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        sign = '+'
        
        for i, char in enumerate(s):
            if char.isdigit():
                num = num * 10 + int(char)
            
            if char in '+-*/' or i == len(s) - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                elif sign == '/':
                    stack.append(int(stack.pop() / num))
                sign = char
                num = 0
        
        return sum(stack)

public class Solution {
    public int Calculate(string s) {
        Stack<int> stack = new Stack<int>();
        int num = 0;
        char sign = '+';
        
        for (int i = 0; i < s.Length; i++) {
            if (char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.Length - 1) {
                if (sign == '+') {
                    stack.Push(num);
                } else if (sign == '-') {
                    stack.Push(-num);
                } else if (sign == '*') {
                    stack.Push(stack.Pop() * num);
                } else if (sign == '/') {
                    stack.Push(stack.Pop() / num);
                }
                sign = s[i];
                num = 0;
            }
        }
        
        int result = 0;
        while (stack.Count > 0) {
            result += stack.Pop();
        }
        return result;
    }
}

var calculate = function(s) {
    let stack = [];
    let num = 0;
    let operator = '+';
    
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        
        if (char >= '0' && char <= '9') {
            num = num * 10 + parseInt(char);
        }
        
        if (char === '+' || char === '-' || char === '*' || char === '/' || i === s.length - 1) {
            if (operator === '+') {
                stack.push(num);
            } else if (operator === '-') {
                stack.push(-num);
            } else if (operator === '*') {
                stack.push(stack.pop() * num);
            } else if (operator === '/') {
                stack.push(Math.trunc(stack.pop() / num));
            }
            
            operator = char;
            num = 0;
        }
    }
    
    return stack.reduce((sum, val) => sum + val, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历字符串一次，n为字符串长度
空间复杂度O(n)栈最多存储O(n)个数字（最坏情况全是加法）

相关题目