【数据结构-表达式解析】【hard】力扣224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = “1 + 1”
输出：2

示例 2：
输入：s = " 2-1 + 2 "
输出：3

示例 3：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

栈

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        stack<int> st;
        st.push(1);
        int ret = 0;
        int sign = 1;
        int i = 0;
        while(i < n){
            if(s[i] == ' '){
                i++;
            }
            else if(s[i] == '('){
                st.push(sign);
                i++;
            }
            else if(s[i] == '+'){
                sign = st.top();
                i++;
            }
            else if(s[i] == '-'){
                sign = -st.top();
                i++;
            }
            else if(s[i] == ')'){
                st.pop();
                i++;
            }
            else{
                long num = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9'){
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
};

时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。

空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 n。

这种题目第一时间就想到用栈来做，这道题的难点是什么呢？我认为这道题有两个问题只要理清就可以。

第一个需要解决的问题是，在算式中我们存在括号，我们怎么样在含有括号的情况下，将括号拆开然后正确计算？比如说在(1-(2-1))中，实际上可以拆解成1-2+1，所以我们可以发现，括号内的符号拆解后，受到括号外符号的影响。

所以我们可以构建一个栈st来储存符号，我们初始化符号sign（1或-1）为1，当我们遍历字符串的时候，遇到左括号，就往栈中推入sign，推入的sign会位于栈顶，作用于这个左括号开始到右括号结束之间的符号，假设我们这时候sign是-1，然后遇到了一个左括号，然后接着在这个括号范围内遇到了一个减号，那么他就将sign变为1，也就是我们所说的负负得正，接着当我们遇到右括号的时候，就弹出栈顶的sign，因为栈顶的sign只作用于这个括号范围。

第二个问题是题目中的数字可能不止是个数，可能是十位、百位或者更多位，所以我们需要用一个while循环来将多个字符转化为一个数字。