算法训练营第二十一天|227. 基本计算器 II
题目链接：https://leetcode.cn/problems/basic-calculator-ii/description/ 优秀题解：https://leetcode.cn/problems/basic-calculator-ii/solutions/91271/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
题目核心分析与思路
问题概述：
实现一个计算器，计算一个包含非负整数、+、-、*、/四种运算符和空格的字符串表达式的值。表达式是有效的，且除法为整数除法，向零截断。
核心挑战：
与之前单纯的“逆波兰表达式”或“相邻重复项消除”不同，本题引入了运算符优先级：*和/的优先级高于+和-。我们不能简单地顺序计算，必须让高优先级的运算先发生。
为什么用栈？
栈可以帮助我们“暂停”计算。基本策略是：
遍历字符串，解析出数字和运算符。
遇到数字时，需要将其与前面可能存在的连续数字字符组合成完整的操作数。
关键：遇到运算符时，根据其类型决定立即计算还是暂缓计算：
如果当前运算符是
+或-：由于优先级低，其左操作数的计算可能被后面的高优先级运算符影响，因此不能立即计算。我们将其连同符号一起压入栈中暂存。如果当前运算符是
*或/：由于优先级高，必须立即计算。此时它的左操作数就是上一个刚刚解析完的数字（或上一个乘除法的结果），右操作数是下一个即将解析的数字。计算后，用结果更新或替换栈中对应的值。
算法步骤（栈法）：
初始化：一个栈
stack<int>用于存储中间结果，一个变量num存储当前解析的数字，一个变量sign存储当前数字之前的运算符（初始为+，因为第一个数字是正的）。遍历字符串：
遇到数字：更新
num = num * 10 + (c - '0')。遇到运算符或到达字符串末尾：说明一个完整的操作数
num已解析完毕，此时需要根据它之前的运算符sign来决定如何处理它：sign为+：将num压入栈。sign为-：将-num压入栈。sign为*：弹出栈顶元素top，计算top * num，将结果压回栈。sign为/：弹出栈顶元素top，计算top / num，将结果压回栈。
处理完毕后，重置
num = 0，并将当前遇到的运算符c赋值给sign，作为下一个数字的前置运算符。
计算结果：遍历结束后，栈中所有元素（它们都代表带符号的数字，且高优先级的乘除已计算完毕）的和即为最终结果。
#include <stack> #include <string> using namespace std; class Solution { public: int calculate(string s) { stack<int> stk; long long num = 0; // 当前解析的数字 char sign = '+'; // 初始化符号，第一个数字默认为正 int n = s.size(); for (int i = 0; i < n; ++i) { char c = s[i]; if (isdigit(c)) { // 构建多位数 num = num * 10 + (c - '0'); } // 当遇到运算符 或 到达字符串末尾时，处理上一个运算符和数字 if ((!isdigit(c) && c != ' ') || i == n - 1) { switch (sign) { case '+': stk.push(num); break; case '-': stk.push(-num); break; case '*': { int top = stk.top(); stk.pop(); stk.push(top * num); break; } case '/': { int top = stk.top(); stk.pop(); stk.push(top / num); break; } } // 重置数字，并记录新的运算符 num = 0; sign = c; } } // 对栈中所有数字求和 int result = 0; while (!stk.empty()) { result += stk.top(); stk.pop(); } return result; } };