题解 | #表达式求值#两个栈，一个保存数字，一个保存运算符。

//遍历string, 遇到数字，放入数字栈，遇到操作符，非右括号的全部入栈；
//遇到右括号，就去计算最近匹配的左括号之间的表达式的值；
//string遍历结束后，还需要检查操作符栈中是否还有操作符，有的话说明还有表达式没计算，再去计算剩余表达式部分的结果；
//计算分两种情况：1.遇到右括号了，计算直到遇到左括号结束；2.表达式到末尾，计算剩下的表达式。


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    stack<int> nums;
    stack<char> opts;
    //表达式计算：1.处理到左括号之前； 2.没有括号，就处理目前全部的表达式
    void calc() {
        stack<int> tmpnum; //
        stack<char> tmpopt; //临时 
        tmpnum.push(nums.top());  nums.pop(); //先入栈第一个操作数
        while(!opts.empty() && opts.top() != '(') { 
            tmpnum.push(nums.top()); nums.pop(); // 入栈第二个操作数
            tmpopt.push(opts.top()); opts.pop();  //入栈操作符
            if(tmpopt.top() == '*') { // 如果最近的操作符是乘号，因为乘号优先级最高，先处理乘号和其左右的两个操作数，并将结果再次入栈
                int leftopt = tmpnum.top(); tmpnum.pop();
                int rightopt = tmpnum.top(); tmpnum.pop();
                tmpnum.push(leftopt * rightopt);
                tmpopt.pop();
            }
        }
        if(!opts.empty() && opts.top() == '(') { opts.pop(); } // 上面结束循环的条件不是原栈空了，就是或者遇到左括号了，如果是左括号，需要单独出栈
        while(!tmpopt.empty()) { // 计算，栈内只有 + - 运算
            char op = tmpopt.top(); tmpopt.pop();
            int left = tmpnum.top(); tmpnum.pop();
            int right = tmpnum.top(); tmpnum.pop();
            if(op == '+') {
                tmpnum.push(left+right);
            } else if(op == '-') {
                tmpnum.push(left - right);
            } 
        }
        while(!tmpnum.empty()) { // 处理结束，数据栈最后的数就是当前表达式的计算结果，写回去原栈
          nums.push(tmpnum.top()); tmpnum.pop();  
        }
    }
    int solve(string s) {
        int result = 0;
        int leftnum = 0, rightnum = 0;
        for(int i = 0; i < s.length(); ) {
            if(s[i] <= '9' && s[i] >= '0') { // 数字入栈
                int tmp = 0;
                while(i < s.length() && (s[i] <= '9' && s[i] >= '0') ) {
                    tmp = tmp*10 + s[i++] - '0';
                }
                nums.push(tmp);
            } else if(s[i] == ')') { // 遇到右括号，处理前面最近匹配的左括号之间的表达式
               calc();
                ++i;
            } else { 
                opts.push(s[i++]); //操作符入栈
            }
        }
        if(!opts.empty() ) { // 处理栈中剩下的没有括号的部分
            calc();
        }
        result = nums.top();
        return result;
    }
};