[牛客BM49&LeetCode227]基本计算器-双栈递归方法-最易理解
双栈+递归方法
比目前官网题解更容易理解且简单的方法。
双栈：一个栈用于存放数字，一个用于存放符号。
递归：括号内表达式求值作为返回值，减少处理括号时边界条件的难度。
基本思想：
参考人计算的思维，如果[后入栈的运算符优先级]大于[先入栈的运算符优先级]，那么进行计算。
奇怪的细节：
1.考虑字符串开始就有可能出现负号和正号，因此在两个栈的开头分别插入'0'、'-'或'0'、'+'。
2.int相加时中间结果可能溢出，使用long long保存结果。
另外：
这里使用递归和传统递归模板不同，传统模板如下：
=1= if (终止条件) return;
=2= [向下传递时]逻辑处理（可能有，也可能没有，具体问题具体分析）
=3= 递归调用
=4= [反弹/回溯]逻辑处理（可能有，也可能没有，具体问题具体分析）
本文使用的递归终止条件并不是在开头，可以看作这里有一个非常长的if终止条件语句。
class Solution {
public:
unordered_map<char, int> oper_prio{
{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2},
{'%', 2},
{'^', 3}
};
int func(string &s, int &idx) {
stack<int> nums;
stack<char> opers;
if (s[idx] == '+') {
nums.push(0);
opers.push('+');
++idx;
} else if (s[idx] == '-') {
nums.push(0);
opers.push('-');
++idx;
}
int num = 0;
while(idx < s.length()) {
// 1. 读取数字
if (isdigit(s[idx])) {
while (isdigit(s[idx])) {
num = num * 10 + s[idx] - '0';
++idx;
}
nums.push(num);
num = 0;
--idx; // 恢复指针
}
// 2.读取到'('
else if (s[idx] == '(') nums.push(func(s, ++idx));
// 3.读取到')'
else if (s[idx] == ')') break;
// 4. 读取到 Other operators
else {
while (!opers.empty() && oper_prio[opers.top()] >= oper_prio[s[idx]]) {
calc(nums, opers);
}
opers.push(s[idx]);
}
++idx;
}
while (!opers.empty()) {
calc(nums, opers);
}
return nums.top();
}
static void calc(stack<int> &nums, stack<char> &opers) {
long long num2 = nums.top(); nums.pop();
long long num1 = nums.top(); nums.pop();
char oper = opers.top(); opers.pop();
long long res;
switch(oper) {
case '+' : res = num1 + num2; break;
case '-' : res = num1 - num2; break;
case '*' : res = num1 * num2; break;
case '/' : res = num1 / num2; break;
case '%' : res = num1 % num2; break;
case '^' : res = pow(num1, num2); break;
}
nums.push(res);
}
int solve(string s) {
// write code here
int i = 0;
return func(s, i);
}
};