0227. Basic Calculator II ========================= 题目信息 -------- :题号: 0227 :难度: Medium :主题: 字符串、表达式、栈、数学 :原题: `LeetCode 0227 `_ :重点: 乘除优先于加减、整数除法向零截断、空格、无括号 题目重述 -------- 给定一个合法的算术表达式字符串 ``s``,计算并返回表达式的整数结果。表达式由非负十进制整数、空格以及 ``+``、``-``、``*``、``/`` 四种二元运算符组成,不含括号。乘法和除法的优先级高于加法和减法;同一优先级按从左到右结合。 字符串长度位于 ``[1, 3 * 10^5]``。题目保证表达式合法,表达式中的每个整数及最终结果都适合 32 位有符号整数。整数除法必须向零截断,例如 ``7 / 3`` 的结果为 ``2``。不能使用把字符串直接作为表达式执行的内置求值函数。 自建示例 -------- 乘除先计算: .. code-block:: text 输入:s = "18-5*3+7/2" 输出:6 解释:先得到 5*3=15 和 7/2=3,再按从左到右计算 18-15+3=6。 除法丢弃小数部分: .. code-block:: text 输入:s = "20/3-8" 输出:-2 解释:20/3 向零截断为 6,因此最终结果为 6-8=-2。 保留尚未合并的最后一项 ---------------------- 表达式没有括号,乘除只需要在当前加减项内部立即计算;加减遇到时可以把前一项提交到总和。 维护三个状态: ``result`` 已经确定不会再与后续乘除相连的项之和。 ``last_term`` 当前加减段中最后一项,可能是正数或负数,等待与下一个乘除运算结合。 ``number`` 与 ``op`` 正在读取的数字,以及它前面的运算符。 读到下一个运算符时,根据 ``op`` 更新:``+`` 把 ``last_term`` 加入 ``result`` 并令最后一项为正数, ``-`` 同样提交并令最后一项为负数,``*`` 或 ``/`` 只改写 ``last_term``。字符串末尾设置一个虚拟分隔点, 确保最后一个数字也被处理。 正确性说明 ---------- 在扫描每个运算符前,``result + last_term + number`` 表示已读前缀的值,其中 ``last_term`` 尚未与 当前数字结合。加减会结束当前高优先级项,因此先提交旧项;乘除只修改该项,正好实现乘除优先。 除法使用 C++ 对整数的向零截断语义,符合题目定义。扫描结束后再提交最后一项,得到完整表达式值。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int calculate(const std::string& s) { long long result = 0; long long last_term = 0; long long number = 0; char op = '+'; for (int i = 0; i <= static_cast(s.size()); ++i) { const char ch = (i == static_cast(s.size())) ? '+' : s[i]; if (ch >= '0' && ch <= '9') { number = number * 10 + (ch - '0'); continue; } if (ch == ' ') continue; switch (op) { case '+': result += last_term; last_term = number; break; case '-': result += last_term; last_term = -number; break; case '*': last_term *= number; break; case '/': last_term /= number; break; } number = 0; op = ch; } return static_cast(result + last_term); } }; 代码分析 -------- 空格不触发结算;虚拟末尾运算符只用于触发最后一次更新,不会影响 ``result + last_term`` 的最终组合。 每个字符只扫描一次,时间复杂度为 ``O(|s|)``,除固定数量的累加状态外空间为 ``O(1)``。 使用 ``long long`` 保存中间项,并依赖题目保证最终结果适合 ``int``。