描述

请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：0\le |s| \le 1000≤∣s∣≤100，保证计算结果始终在整型范围内

要求：空间复杂度： O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入： 
"1+2"
复制
返回值： 
3
复制

示例2

输入： 
"(2*(3-4))*5"
复制
返回值： 
-10
复制

示例3

输入： 
"3+2*3*4-1"
复制
返回值： 
26
解题思路：
1、表达式中有括号、乘号，要重点考虑优先级问题；
2、加号和减号可以合并为加法，减号为加一个负数；括号可以看做一个子问题，使用递归的方法计算；
3、默认运算符为加法，轮询字符串s：
遇到数字后将数字组合为num，将num压入栈；
遇到'('后递归调用，递归方法在遇到‘(’后结束；
先根据前置运算符将计算结果入栈，如果前置运算符是乘法，则弹出栈顶元素与当前元素相乘后入栈（先弹出再入栈！！）；
4、注意对队尾元素的处理，除队尾外，遇到数字要累积计算num直到非数字，到队尾后要能走到入栈流程。 
if (i != len - 1) {
    continue;
}
完整代码如下： 
class Solution {
public:
    vector<int> func(string s, int index) {
        stack<int> st;
        char op = '+';
        int num = 0;
        int len = s.size();
        vector<int> res(2, 0);
        for (int i = index; i < len; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i] - '0');
                if (i != len - 1) {
                    continue;
                }
            }
            if (s[i] == '(') {
                vector<int> tmp(2, 0);
                tmp = func(s, i+1);
                num = tmp[0];
                i = tmp[1];
                if (i != len - 1) {
                    continue;
                }
            }
            
            switch(op) {
                case '+':
                    st.push(num);
                    break;
                case '-':
                    st.push(-num);
                    break;
                case '*':
                {
                    int t = st.top();
                    st.pop();
                    st.push(t*num);
                    break;
                }
                default:
                    break;
            }
            if (s[i] == ')') {
                res[1] = i;
                break;
            } else {
                op = s[i];
            }
            num = 0;
        }
        num = 0;
        while (!st.empty()) {
            num += st.top();
            st.pop();
        }
        
        res[0] = num;
        return res;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        vector<int> res(2, 0);
        res = func(s, 0);
        return res[0];
    }
};