题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
-
示例 1：
输入：s = "1 + 1"
输出：2 -
示例 2：
输入：s = " 2-1 + 2 "
输出：3 -
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23 -
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数
分析
本题中只含有加减法，因此优先级只需要考虑括号。但，比起层层计算括号内的算式，不如直接去掉括号顺序计算更快。
去括号要考虑什么呢？ 正负号。
若'('前符号为+，则去括号后，括号内加数的符号不变；反之加数变号。
遇到')'结束这个括号，变号标志就退回到'('前。
————>栈存本括号对应的变号标志
扫描字符串的策略
- 空格：跳过
- 数字：连续扫描得到这个数，最后数字乘以变号标志和当前符号
- 扫描到'+'：当前符号不变
- 扫描到'-'：当前符号变号
- 扫描到'('：当前符号入栈为变号标志
- 扫描到')'：变号标志退栈
代码
class Solution {
public:
int calculate(string s) {
const int sLen = s.length();
// 变号标志的栈，1表示不变号，-1表示变号
stack<int> signsStack;
signsStack.emplace(1);
// 当前数的前序符号，变号标志栈的栈顶。一个数字的最终符号是二者乘积
int currentSign = 1, topSign = 1;
// 结果求和
int ans = 0;
// 遍历算式
int p = 0;
while(p < sLen) {
// 跳过空格
if(s[p] == ' ') {
++p;
continue;
}
// 连续扫描数字，数字的最终符号是当前符号和变号标志的乘积
if(s[p] >= '0' && s[p] <= '9') {
long num = 0;
while(p < sLen && s[p] >= '0' && s[p] <= '9') {
num = num * 10 + s[p] - '0';
++p;
}
ans += currentSign * topSign * num;
} else {
// 遇'('，变号情况压栈，当前符号归位1
if(s[p] == '(') {
signsStack.emplace(currentSign * topSign);
topSign = signsStack.top();
currentSign = 1;
// 遇')'，回退到上一个状态
} else if(s[p] == ')') {
currentSign = signsStack.top();
signsStack.pop();
topSign = signsStack.top();
// 遇'+'或'-'，更新当前符号
} else if(s[p] == '+'){
currentSign = 1;
} else if(s[p] == '-') {
currentSign = -1;
}
++p;
}
}
return ans;
}
};