LeetCode 227. 基本计算器 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：栈 + 符号标记（推荐）
相似题目

题目描述

✅ 227. 基本计算器 II

思路分析

解法一：栈 + 符号标记（推荐）

核心思路：

只含 +、-、*、/，无括号。利用运算优先级：先处理乘除，再累加加减。

关键设计：维护前一个运算符 op（初始为 '+'），每次遇到新运算符或字符串末尾时，依据 op 决定如何处理当前数字 num：

op == '+'：push(num)

op == '-'：push(-num)

op == '*'：push(pop() * num)（弹出上一个数与 num 计算，结果压回）

op == '/'：push(pop() / num)

最终将栈中所有数字累加即为结果。

为何正确：*// 遇到时立即与上一个数计算，相当于”先乘除后加减”；+/- 的结果全部入栈，最后一次性求和。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度，仅一次遍历

空间复杂度：O(n)，栈最多存储 n/2 个数字

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char op = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 累计当前数字
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            // 遇到运算符或字符串末尾，处理前一个运算符
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                if (op == '+') {
                    stack.push(num);
                } else if (op == '-') {
                    stack.push(-num);
                } else if (op == '*') {
                    stack.push(stack.pop() * num);
                } else if (op == '/') {
                    stack.push(stack.pop() / num);
                }
                op = c;
                num = 0;
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}

func calculate(s string) int {
    stack := []int{}
    num := 0
    op := byte('+')
    for i := 0; i < len(s); i++ {
        c := s[i]
        // 累计当前数字
        if c >= '0' && c <= '9' {
            num = num*10 + int(c-'0')
        }
        // 遇到运算符或字符串末尾，处理前一个运算符
        if (c != ' ' && (c < '0' || c > '9')) || i == len(s)-1 {
            switch op {
            case '+':
                stack = append(stack, num)
            case '-':
                stack = append(stack, -num)
            case '*':
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                stack = append(stack, top*num)
            case '/':
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                stack = append(stack, top/num)
            }
            op = c
            num = 0
        }
    }
    res := 0
    for _, v := range stack {
        res += v
    }
    return res
}

相似题目

题目	难度	考察点
224. 基本计算器	困难	栈处理括号+加减
772. 基本计算器 III	困难	栈处理括号+四则运算
150. 逆波兰表达式求值	中等	栈处理后缀表达式
394. 字符串解码	中等	栈处理嵌套括号
71. 简化路径	中等	栈处理路径字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/14490119