0224. Basic Calculator
======================
题目信息
--------
:题号: 0224
:难度: Hard
:主题: 字符串、表达式、栈、递归
:原题: `LeetCode 0224 `_
:重点: 加减法、嵌套括号、一元负号、空格、禁止内置求值器
题目重述
--------
给定一个合法的算术表达式字符串 ``s``,计算并返回其整数结果。表达式由数字、空格、加号 ``+``、减号 ``-``、左括号 ``(`` 和右括号 ``)`` 组成;整数均为非负十进制数,但减号可以作为一元负号使用。表达式不包含乘法或除法。
字符串长度位于 ``[1, 3 * 10^5]``。题目保证表达式合法,每个整数及最终结果都适合 32 位有符号整数;加号不会作为一元运算符出现,也不会出现两个连续的二元运算符。不能调用把字符串直接当作表达式执行的内置函数。
自建示例
--------
嵌套括号改变符号:
.. code-block:: text
输入:s = "18-(6-(2+1))"
输出:15
解释:内层 2+1 等于 3,随后 6-3 等于 3,最终 18-3 等于 15。
一元负号作用于括号:
.. code-block:: text
输入:s = "-(7-10)+4"
输出:7
解释:7-10 等于 -3,括号前的一元负号把它变为 3,再加 4 得到 7。
用栈保存括号外的上下文
----------------------
扫描表达式时,当前 ``result`` 和 ``sign`` 只描述最近一层括号中的部分结果。遇到左括号时,
把进入括号前的累计结果和括号整体应使用的符号压栈,然后从零开始计算括号内部;遇到右括号时,
先结算当前数字,再把括号结果乘以保存的符号并加回外层结果。
对每个数字只在读到下一个运算符、右括号或字符串末尾时结算。这样一元负号无需把负号和数字合成特殊词法:
它只把当前项的 ``sign`` 设为 ``-1``;若后面紧跟左括号,保存的负号就会作用于整个括号表达式。
状态转移可以写成:
.. code-block:: text
'+' 或 '-': result += sign * number,清零 number,更新 sign
'(': 保存 result 与 sign,result=0,sign=1
')': 结算 number,恢复 outer_result + outer_sign * result
正确性说明
----------
在任意时刻,栈中的每一帧都保存一个尚未结束的外层括号上下文;当前变量表示最内层已扫描部分。
数字结算时只加入当前层,二元加减的从左到右顺序被保留。右括号结算完整内层结果后一次性应用外层符号,
因此括号嵌套不会把符号错误地施加到单个数字或后续表达式上。表达式合法且最终读完后,结算剩余数字即得到总结果。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int calculate(const std::string& s) {
std::stack> context;
long long result = 0;
long long number = 0;
int sign = 1;
for (int i = 0; i < static_cast(s.size()); ++i) {
const char ch = s[i];
if (std::isdigit(static_cast(ch))) {
number = number * 10 + (ch - '0');
} else if (ch == '+' || ch == '-') {
result += sign * number;
number = 0;
sign = (ch == '+') ? 1 : -1;
} else if (ch == '(') {
context.push({result, sign});
result = 0;
number = 0;
sign = 1;
} else if (ch == ')') {
result += sign * number;
number = 0;
const auto [outer_result, outer_sign] = context.top();
context.pop();
result = outer_result + outer_sign * result;
sign = 1;
}
}
result += sign * number;
return static_cast(result);
}
};
代码分析
--------
空格被自然跳过;``std::isdigit`` 先转换为 ``unsigned char``,避免传入负的窄字符值。
每个括号只入栈、出栈一次,每个字符只扫描一次,时间复杂度为 ``O(|s|)``,额外空间为括号最大嵌套深度
``O(|s|)``。用 ``long long`` 保存中间累计值,再按题目合同返回 ``int``;代码不调用表达式求值器。