C++ 栈 模拟 力扣 227. 基本计算器 II 题解 每日一题

题目描述

题目链接：力扣 227. 基本计算器 II

题目描述：

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

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

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

提示：
1 <= s.length <= 3 * 10⁵
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2³¹- 1] 内
题目数据保证答案是一个 32-bit 整数

这道题为什么值得你花几分钟弄懂？

从能力增长来看，它能一次性帮我们强化三个关键技能：

1. 字符串处理能力：题目里的空格、多位数（比如“123+456”）需要精准解析，能帮你摆脱“只会处理规整输入”的短板，掌握实际开发中常用的字符遍历、数值提取技巧；
2. 数据结构应用：用栈解决运算优先级（乘除优先于加减）的思路，是栈的经典场景，吃透后能举一反三，应对后续含括号、复杂优先级的表达式问题；
3. 逻辑严谨性：整数除法的截断规则、无溢出处理等细节，能锻炼我们“考虑边界情况”的思维，这是从“能写代码”到“写好代码”的关键一步。

算法原理

这道题的核心是处理加减乘除的优先级问题，而栈正是解决这类问题的“利器”——相比传统“双栈（数字栈+符号栈）”的复杂实现，由于题目不含括号，我们可以进一步简化逻辑，用一个栈+一个符号变量就能高效完成计算，核心思路清晰易懂。

核心逻辑：化繁为简的优先级处理
传统表达式求值需要两个栈分别存储数字和符号，再通过优先级规则调整计算顺序。但本题无括号，仅需区分“加减”（低优先级）和“乘除”（高优先级），因此可以做如下简化：

• 用一个栈存储最终需要“加减求和”的数字（将减法转化为加负数，统一运算逻辑）；
• 用一个字符变量记录当前数字的前导符号（默认第一个数字的符号为+，确保操作统一）；
• 遍历字符串时，遇到低优先级的“加减”直接将数字（或其相反数）入栈；遇到高优先级的“乘除”，则取出栈顶元素与当前数字计算后，将结果重新压入栈，实现“先算乘除”的优先级要求。

分步模拟：模拟计算全流程
结合图中示例表达式+3+5*22-5+3/2（我随机写的），我们一步步看栈的工作流程：

1. 初始化与统一规则：为了方便后续操作统一，我们将第一个数字的符号ch = '+'，所有数字都需要和 “前一个运算符” 绑定，第一个数字没有前一个运算符，默认 + 可以让所有数字的处理逻辑完全统一（无需单独判断第一个数字），栈为空。遍历到第一个数字3，因符号为+，直接将3压入栈，此时栈：[3]。
   

2. 处理下一个低优先级符号：遇到+（前导符号更新为+），后续数字为5，同样直接入栈，栈：[3, 5]。
   

3. 处理高优先级运算（乘）：遇到*（前导符号更新为*），后续数字为22。此时需取出栈顶元素5，与22相乘得110，将110压回栈，栈：[3, 110]。
   

4. 处理低优先级运算（减）：遇到-（前导符号更新为-），后续数字为5，加减是同级运算，优先级低于乘除，因此可以先将减法对应的数字转为负数存入栈，最后统一求和（等价于按顺序计算加减），将5取反为-5入栈，栈：[3, 110, -5]。
   

5. 处理高优先级运算（除）：遇到+（前导符号更新为+），后续数字为3，入栈后栈：[3, 110, -5, 3]；接着遇到/（前导符号更新为/），后续数字为2，取出栈顶3与2做整数除法得1，压回栈，栈：[3, 110, -5, 1]。
   

6. 最终求和：遍历结束后，栈中所有元素求和（3+110-5+1=109），即为表达式的结果。
   

关键细节：多位数与空格处理

• 多位数解析：遍历到数字时，需通过“原数字×10 + 当前字符对应的数值”拼接（如'2'和'2'拼接为22）；
• 空格忽略：遇到空格直接跳过，不影响数字和符号的解析，确保输入格式不规整时也能正常计算。

算法逻辑总结

通过上述分步模拟，我们可以将复杂的表达式求值过程，提炼为一套清晰、可落地、无冗余的核心规则，全程围绕“单栈+单符号”的简化思路，精准解决优先级问题：

首先遍历字符串的核心操作流程

1. 遇到操作符（+、-、*、/）：
   直接更新“当前运算符号”变量ch（关键前提：第一个数字默认符号为+，确保所有数字的处理逻辑完全统一，无需特殊判断）；

2. 遇到数字（含多位数）：
   （1）先完整提取连续数字：通过“前序数字×10 + 当前字符数值”的方式，拼接出完整整数tmp（例如从'2'到'22'的解析）；
   （2）根据当前符号ch执行精准操作：

   • 若ch === '+'：直接将tmp压入栈（作为后续求和的正项）；
   • 若ch === '-'：将-tmp压入栈（减法转“加负数”，统一最终求和逻辑）；
   • 若ch === '*'：弹出栈顶元素，与tmp相乘后，将结果重新压入栈（优先完成乘法运算）；
   • 若ch === '/'：弹出栈顶元素，与tmp执行“仅保留整数部分”的除法后，将结果重新压入栈（优先完成除法运算）；

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

代码实现

classSolution{public:intnumber(string&s,int&i){intret=0;while(s[i]>='0'&&s[i]<='9'){ret*=10;ret+=(s[i]-'0');i++;}returnret;}intcalculate(string s){vector<int>num;charch='+';intn=s.size(),i=0;while(i<n){if(s[i]==' ')i++;elseif(s[i]>='0'&&s[i]<='9'){inttmp=number(s,i);if(ch=='+')num.push_back(tmp);elseif(ch=='-')num.push_back(-tmp);elseif(ch=='*')num.back()*=tmp;elsenum.back()/=tmp;}else{ch=s[i];i++;}}intret=0;for(autoe:num)ret+=e;returnret;}};

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

时间复杂度：O(n)

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

空间复杂度：O(n)

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

总结

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

1. 学习价值：这道题是提升字符串处理、栈应用、边界逻辑处理的“性价比题”，既贴合实际开发场景，又是面试高频考点，吃透后可举一反三解决同类表达式问题；
2. 核心思路：用“单栈+单符号”简化传统双栈逻辑，将减法转为“加负数”、乘除优先与栈顶计算，最终通过栈内元素求和得到结果，兼顾效率与可读性；
3. 实现关键：需注意多位数拼接、空格跳过、整数除法截断规则等细节，代码通过一次遍历完成所有逻辑，时间/空间复杂度均为 O(n)，满足题目性能要求。

下题预告

下一篇我们将挑战字符串题型中的经典“烧脑题”——力扣 394. 字符串解码！这道题是面试中考察“栈的灵活应用”和“字符串嵌套处理”的高频题，不仅需要精准解析数字与括号的嵌套逻辑，还要掌握“双栈分治”“递归解析”等核心解题思路，同时考验你对字符串拼接、索引控制的细节处理能力。

不管是笔试中对代码逻辑的严谨性要求，还是面试中对解题思路的清晰阐述，这道题都能全方位检验你的“嵌套问题拆解能力”和“数据结构活用思维”。相信吃透这道题，你对栈的应用、复杂字符串处理的理解会实现质的飞跃！

Doro 带着小花🌸来啦！🌸奖励🌸坚持搞定“基本计算器”的你！基础打牢才能不惧复杂题型，下一道题虽然涉及嵌套解析，看似有难度，但只要跟着思路拆解数字、括号、字符串的对应关系，一定能轻松攻克～ 别忘了收藏本文，后续刷题随时回顾栈的核心用法，也欢迎在评论区分享你解这道计算器题的心得，我们下道题不见不散！