C++ 栈模拟 LeetCode 227 基本计算器 II 题解

1. 遇到操作符（+、-、*、/）：直接更新'当前运算符号'变量 ch（关键前提：第一个数字默认符号为 +）；
2. 遇到数字（含多位数）： （1）先完整提取连续数字：通过'前序数字×10 + 当前字符数值'的方式，拼接出完整整数 tmp； （2）根据当前符号 ch 执行精准操作：
   • 若 ch == '+'：直接将 tmp 压入栈；
   • 若 ch == '-'：将 -tmp 压入栈；
   • 若 ch == '*'：弹出栈顶元素，与 tmp 相乘后，将结果重新压入栈；
   • 若 ch == '/'：弹出栈顶元素，与 tmp 执行'仅保留整数部分'的除法后，将结果重新压入栈。

遍历完整个字符串后，栈中存储的是所有经过'乘除优先级处理'后的加减项，只需将栈内所有元素求和，即可得到表达式的最终结果。

代码实现

class Solution {
public:
    int number(string& s, int& i) {
        int ret = 0;
        while (s[i] >= '0' && s[i] <= '9') {
            ret *= 10;
            ret += (s[i] - '0');
            i++;
        }
        return ret;
    }
    
    int calculate(string s) {
        vector<int> num;
        char ch = '+';
        int n = s.size(), i = 0;
        while (i < n) {
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9') {
                int tmp = number(s, i);
                if (ch == '+') num.push_back(tmp);
                else if (ch == '-') num.push_back(-tmp);
                else if (ch == '*') num.back() *= tmp;
                else num.back() /= tmp;
            } else {
                ch = s[i];
                i++;
            }
        }
        int ret = 0;
        for (auto e : num) ret += e;
        return ret;
    }
};

时间复杂度与空间复杂度分析

时间复杂度：O(n)

• 核心逻辑：算法仅对字符串 s 进行一次完整遍历（i 从 0 到 n-1 逐个移动，无回退）；
• 辅助操作：数字提取、栈的压入/弹出、最终求和均为线性遍历，无嵌套循环；
• 结论：整体时间复杂度为 O(n)（n 为字符串长度）。

空间复杂度：O(n)

• 栈的空间消耗：最坏情况下（表达式全为加减运算），栈需要存储所有数字，空间复杂度为 O(n)；
• 辅助变量：仅使用 ch、tmp、i 等常数级变量，无额外空间消耗；
• 结论：空间复杂度为 O(n)，在常规编程场景下属于可接受范围。

总结

本文围绕力扣 227. 基本计算器 II 展开，从'算法原理 - 代码实现'三个维度完整拆解了这道经典的表达式求值问题，核心要点可总结为：

1. 核心思路：用'单栈 + 单符号'简化传统双栈逻辑，将减法转为'加负数'、乘除优先与栈顶计算，最终通过栈内元素求和得到结果，兼顾效率与可读性；
2. 实现关键：需注意多位数拼接、空格跳过、整数除法截断规则等细节，代码通过一次遍历完成所有逻辑，时间/空间复杂度均为 O(n)，满足题目性能要求。