0227. Basic Calculator II

题目信息

题号:

0227

难度:

Medium

主题:

字符串、表达式、栈、数学

原题:

LeetCode 0227

重点:

乘除优先于加减、整数除法向零截断、空格、无括号

题目重述

给定一个合法的算术表达式字符串 s,计算并返回表达式的整数结果。表达式由非负十进制整数、空格以及 +、-、*、/ 四种二元运算符组成,不含括号。乘法和除法的优先级高于加法和减法;同一优先级按从左到右结合。

字符串长度位于 [1, 3 * 10^5]。题目保证表达式合法,表达式中的每个整数及最终结果都适合 32 位有符号整数。整数除法必须向零截断,例如 7 / 3 的结果为 2。不能使用把字符串直接作为表达式执行的内置求值函数。

自建示例

乘除先计算:

输入:s = "18-5*3+7/2"
输出:6
解释:先得到 5*3=15 和 7/2=3,再按从左到右计算 18-15+3=6。

除法丢弃小数部分:

输入: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++ 实现

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<int>(s.size()); ++i) {
            const char ch = (i == static_cast<int>(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<int>(result + last_term);
    }
};

代码分析

空格不触发结算;虚拟末尾运算符只用于触发最后一次更新,不会影响 result + last_term 的最终组合。 每个字符只扫描一次,时间复杂度为 O(|s|),除固定数量的累加状态外空间为 O(1)。 使用 long long 保存中间项,并依赖题目保证最终结果适合 int。