当前位置：首页 > news >正文

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

news 2026/3/27 2:54:47

文章目录

题目描述
这道题为什么值得你花几分钟弄懂？
算法原理
- 算法逻辑总结
代码实现
- 时间复杂度与空间复杂度分析
- - 时间复杂度：O(n)
  - 空间复杂度：O(n)
总结
下题预告

题目描述

题目链接：力扣 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 整数

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

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

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

算法原理

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

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

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

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

初始化与统一规则：为了方便后续操作统一，我们将第一个数字的符号ch = '+'，所有数字都需要和 “前一个运算符” 绑定，第一个数字没有前一个运算符，默认 + 可以让所有数字的处理逻辑完全统一（无需单独判断第一个数字），栈为空。遍历到第一个数字3，因符号为+，直接将3压入栈，此时栈：[3]。
处理下一个低优先级符号：遇到+（前导符号更新为+），后续数字为5，同样直接入栈，栈：[3, 5]。
处理高优先级运算（乘）：遇到*（前导符号更新为*），后续数字为22。此时需取出栈顶元素5，与22相乘得110，将110压回栈，栈：[3, 110]。
处理低优先级运算（减）：遇到-（前导符号更新为-），后续数字为5，加减是同级运算，优先级低于乘除，因此可以先将减法对应的数字转为负数存入栈，最后统一求和（等价于按顺序计算加减），将5取反为-5入栈，栈：[3, 110, -5]。
处理高优先级运算（除）：遇到+（前导符号更新为+），后续数字为3，入栈后栈：[3, 110, -5, 3]；接着遇到/（前导符号更新为/），后续数字为2，取出栈顶3与2做整数除法得1，压回栈，栈：[3, 110, -5, 1]。
最终求和：遍历结束后，栈中所有元素求和（3+110-5+1=109），即为表达式的结果。

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

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

算法逻辑总结

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

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

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