题目
给你一个字符串表达式 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 * 105s由数字、'+'、'-'、'('、')'、和' '组成s表示一个有效的表达式- ‘+’ 不能用作一元运算(例如， “+1” 和
"+(2 + 3)"无效) - ‘-‘ 可以用作一元运算(即 “-1” 和
"-(2 + 3)"是有效的) - 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
解答
- 动态规划
题目要求实现一个计算器，计算一个字符串表达式的值。因为表达式中可能会存在括号，为了方便计算，可以使用递归的方法来实现。当遇到左括号时，递归调用自身来计算括号内的表达式值，当遇到右括号时，返回计算结果。当遇到加号或减号时，记录当前的操作符。当遇到数字时，记录当前的数值，并根据之前的操作符进行相应的计算。
具体步骤如下：
- 定义一个辅助栈，用于存储之前的操作符和数字；
- 遍历表达式字符串，遇到数字时记录下来，遇到左括号时递归调用自身，遇到右括号时返回计算结果；
- 遇到加号或减号时，记录当前的操作符，遇到其他字符时忽略；
- 当遇到表达式字符串的末尾时，将栈中剩余的数字和操作符进行计算，并返回最终结果。
class Solution {
public:
int calculate(string s) {
stack<int> st; // 定义一个辅助栈，用于存储之前的操作符和数字
int num = 0; // 用于记录当前的数值
int res = 0; // 用于记录最终结果
int sign = 1; // 用于记录当前的操作符，1表示加号，-1表示减号
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i])) { // 如果当前字符是数字
num = num * 10 + (s[i] - '0'); // 记录当前的数值
} else if (s[i] == '(') { // 如果当前字符是左括号
int j = i, cnt = 0;
for (; i < s.size(); i++) {
if (s[i] == '(') cnt++;
if (s[i] == ')') cnt--;
if (cnt == 0) break;
}
num = calculate(s.substr(j + 1, i - j - 1)); // 递归调用自身计算括号内的表达式值
}
if (s[i] == '+' || s[i] == '-' || i == s.size() - 1) { // 如果当前字符是加号或减号，或者已经遍历到表达式字符串的末尾
if (s[i] == '+') {
st.push(sign * num); // 将之前记录的数值乘上当前的操作符，并压入栈中
sign = 1; // 更新操作符为加号
} else if (s[i] == '-') {
st.push(sign * num); // 将之前记录的数值乘上当前的操作符，并压入栈中
sign = -1; // 更新操作符为减号
} else if (s[i] == ')' || i == s.size() - 1) {
st.push(sign * num); // 将最后一个数值乘上当前的操作符，并压入栈中
int tmp = 0;
while (!st.empty()) { // 从栈中取出数字和操作符进行计算，直到栈为空
tmp += st.top();
st.pop();
}
res = tmp; // 更新最终结果
}
num = 0; // 清空当前的数值
}
}
return res; // 返回最终结果
}
};上述代码使用了一个栈来存储之前的数字和操作符，用于最后的计算。遇到左括号时，递归调用自身计算括号内的表达式值。遇到加号或减号时，记录当前的操作符和数字，当遇到右括号或表达式字符串的末尾时，将栈中剩余的数字和操作符进行计算，得到最终结果。
需要注意的是，在遇到左括号时，需要找到对应的右括号位置，才能正确地计算括号内的表达式值。这里使用了一个变量cnt来记录遍历到的左括号数量和右括号数量的差值，当cnt为0时，说明找到了对应的右括号。
另外，需要注意的是，当遍历到表达式字符串的末尾时，也需要将之前记录的数字和操作符进行计算，得到最终结果。因此，在遍历完表达式字符串后，还需要进行一次栈中剩余数字和操作符的计算，以得到最终结果。
最后，需要注意对于操作数可能有多个位数的情况，需要在遍历字符串时将多位数字组合成一个完整的数值。这里使用了一个变量num来记录当前的数值，每次遍历到数字时，将其乘以10并加上当前位的数值即可。
综上所述，上述代码实现了一个简单的基本计算器，可以计算表达式中的加减法和括号，并返回最终结果。