224. 基本计算器 - 力扣（LeetCode）
典型的利用栈应用，注意减号不满足结合律。
利用双栈处理表达式的思路：
通过两个栈来实现：其中一个保存操作数，另一个是保存运算符。从左向右遍历表达式，当遇到数字，就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较：
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。这儿注意括号的处理，当遇到左括号，就压入运算符栈，如果碰到右括号，则从操作数弹出两个元素，从运算符栈弹出一个操作符进行计算，并将结果加入到操作数栈中，重复这步直到遇到左括号。
这题中，因为只有加号和减号，所以只要碰到操作符，就从操作数里弹出两个操作数进行处理，也就是省去了优先级比较的步骤。
另外还要注意栈先进后出的特点，注意操作数的顺序,以及数字的累加(char类型到int的转化，以及个位十位转化)。
其实括号放在哪个栈的可以，难点在于代码逻辑处理以及边界条件判断。
class Solution { public: int calculate(string s) { stack<int> num; stack<char> op; int tmp = -1; for(const auto &c : s){ // 空格直接忽略 if(c == ' ') continue; // 是数字的时候，入栈需要累加之后再入栈 // 再遇到操作符之前，这个数字就还没有结束 if(isdigit(c)){ if(tmp == -1) tmp = c - '0'; else // 此时c是char类型，要先转化为int才能push tmp = tmp * 10 + (c - '0'); }else{ // 进入else代表此时的 c 不是数字了，而它之前的数字已经累加完成 // 将累加完成的数字入栈 if(tmp != -1){ num.push(tmp); tmp = -1; } // 下面对此时的 c 进行处理，c 可能为操作符或者括号： if( c == '+' || c == '-'){ while(!op.empty()){ if(op.top() == '(') break; // 运算开始 int num1 = num.top(); num.pop(); int num2 = num.top(); num.pop(); if(op.top() == '+'){ num.push(num2 + num1); op.pop(); }else{ // 注意是num2 - num1（顺序） num.push(num2 - num1); op.pop(); } } // 运算符入栈 op.push(c); }else if(c == '('){ // 左括号直接入栈 op.push(c); }else{ // c 是右括号,一直运算到碰到左括号 while(op.top() != '('){ int num1 = num.top(); num.pop(); int num2 = num.top(); num.pop(); if(op.top() == '+'){ num.push(num2 + num1); op.pop(); }else{ // 注意是num2 - num1（顺序） num.push(num2 - num1); op.pop(); } } // 运算结束，弹出左括号 op.pop(); } } } // 字符串末尾如果是数字，那么最后一个数字也需要入栈，如果是括号，就不需要 if(tmp != -1) num.push(tmp); // 处理最后栈中的数据 while(!op.empty()){ int num1 = num.top(); num.pop(); int num2 = num.top(); num.pop(); if(op.top() == '+'){ num.push(num2 + num1); op.pop(); }else{ // 注意是num2 - num1（顺序） num.push(num2 - num1); op.pop(); } } return num.top(); } };这一题只有加减运算，可以简化一下，首先全部转化为加法，使用一个sign记录符号位即可。所以我们只需要累加 sign*数字 就可以了。从左往右遍历：
是数字：记下当前的数字，即为当前结果是 + ：sign置为1是 - ：sign置为-1是 ( ：当前累加结果入栈，当前符号入栈（两次入栈）是 ) ：两次出栈得到符号位和数字，进行计算只用一个栈就可以了：
class Solution { public: int calculate(string s) { stack<int> stk; int res = 0, sign = 1, n = s.size();//sign代表正负，是后续计算元素的符号 for(int i = 0; i < n; ++i){ char c = s[i]; if(isdigit(c)){ int cur = c - '0'; while(i != n-1 && isdigit(s[i+1])){//下一个也是数字 ++i; int v = s[i] - '0'; cur = 10*cur + v; } res += sign*cur; } else if(c == '+') sign = 1; else if(c == '-') sign = -1; else if(c == '('){ stk.push(res); res = 0; stk.push(sign);//括号前面的符号位 sign= 1; } else if(c == ')'){ int a = stk.top(); stk.pop();//符号 int b = stk.top(); stk.pop(); res = a*res + b; } } return res; } };