题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：

1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位整数

示例：

输入：s = "1 + 1"
输出：2

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

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

解答 & 代码

解法一：两个栈

class Solution {
public:
    int calculate(string s) {
        // 存储每个左括号之前的数值绝对值（若字符串为 '(12+(' 则是存储两个左括号之间的数值绝对值）
        stack<int> resultS;    
        // 存储每个左括号之前的符号：'+' or '-'
        stack<char> signS;
        int idx = 0;            // 当前遍历到的字符串下标
        int result = 0;            // 当前计算结果，初始化为 0
        char curSign = '+';        // 当前的符号，'+' or '-'，初始化为 '+'
        // 遍历字符串
        while(idx < s.size())
        {
            // 跳过空格
            while(idx < s.size() && s[idx] == ' ')
                ++idx;
            if(idx == s.size())        // 如果已经遍历到尾部则跳出循环，直接结束
                break;
            /* 跳过空格后，当前的字符有 4 种可能 */
            // 1. 如果当前字符是数字，则遍历完当前的这个整数 num
            if(s[idx] >= '0' && s[idx] <= '9')
            {
                int num = 0;
                while(idx < s.size() && s[idx] >= '0' && s[idx] <= '9')
                {
                    // 注意下面这行代码的括号，如果不加 s[idx] 先和前面相加可能会溢出
                    num = num * 10 + (s[idx] - '0');
                    ++idx;
                }
                // 根据当前的符号（即当前整数之前的正负号），将当前的计算结果加上 or 减去 num
                if(curSign == '+')
                    result += num;
                else if(curSign == '-')
                    result -= num;
            }
            // 2. 如果当前字符是 '+' or '-'，则改变当前的符号 curSign
            else if(s[idx] == '+' || s[idx] == '-')
            {
                curSign = s[idx];
                ++idx;
            }
            // 3. 如果当前字符是 '('，则将当前的计算结果和符号压入栈，并将计算结果和符号清空
            else if(s[idx] == '(')
            {
                resultS.push(result);    // 将当前计算结果入栈
                signS.push(curSign);    // 将当前符号入栈
                result = 0;                // 将当前计算结果清零
                curSign = '+';            // 将符号位重新初始化为 '+'
                ++idx;
            }
            // 4. 如果当前字符是 ')'，则从栈中弹出之前的计算结果和符号，和当前的计算结果合并
            else if(s[idx] == ')')
            {
                // 从栈中取出和当前 ')' 匹配的 '(' 之前的计算结果
                int preResult = resultS.top();    
                resultS.pop();
                // 从栈中取出和当前 ')' 匹配的 '(' 之前的符号
                char preSign = signS.top();
                signS.pop();
                // 如果之前的符号为 '+'，则将之前的计算结果加上当前的计算结果
                if(preSign == '+')
                    preResult += result;
                // 如果之前的符号为 '-'，则将之前的计算结果减去当前的计算结果
                else if(preSign == '-')
                    preResult -= result;
                // 将当前计算结果更新为合并后的计算结果
                result = preResult;
                ++idx;
            }
        }
        return result; 
    }
};

复杂度分析：设字符串 s 长为 N

时间复杂度 O(N)：遍历每个字符一次
空间复杂度 O(N)：栈空间复杂度，最坏情况下，比如字符串为 "(((((1)))))"，有 (N-1)/2 个左括号，则栈中最多需要同时存储 (N-1)/2 个元素

执行结果：

执行结果：通过
执行用时：8 ms, 在所有 C++ 提交中击败了 80.79% 的用户
内存消耗：7.9 MB, 在所有 C++ 提交中击败了 73.99% 的用户

解法二：一个栈存所有整数，递归处理括号

注意这里的一个操作：将字符串存储到双端队列（貌似队列就行？），再对双端队列进行处理

其实也可以不用双端队列，直接处理数组，在 recurCal() 函数传入的参数中增加一个引用参数 int& idx 代表当前处理到的位置，但是 leetcode 提交后发现时空效率都低很多

class Solution {
private:
  bool isDigit(char ch)
  {
      return ch >= '0' && ch <= '9';
  }
  int recurCal(deque<char>& s)
  {
      stack<int> numS;        // 栈，存放所有整数
      char preSign = '+';        // 之前的符号，初始化为加号
      // 遍历双端队列，每次弹出队首的一个字符
      while(!s.empty())
      {
          char ch = s.front();
          s.pop_front();
          // 1. 如果当前是空格，则跳过
          if(ch == ' ')
              continue;
          // 2. 如果当前是加号或减号，则更新 preSign
          else if(ch == '+' || ch == '-')
              preSign = ch;
          // 3. 如果当前是数字，则遍历得到当前的整数，存入栈中
          else if(isDigit(ch))
          {
              int num = ch - '0';
              while(!s.empty() && isDigit(s.front()))
              {
                  num = num * 10 + (s.front() - '0');
                  s.pop_front();
              }
              if(preSign == '+')            // 如果之前的符号是加号，则该整数直接入栈
                  numS.push(num);
              else if(preSign == '-')        // 如果之前的符号是减号，则该整数的相反数入栈
                  numS.push(-num);
          }
          // 4. 如果当前是遇左括号，则开始递归计算括号内计算后的的 num，存入栈中
          else if(ch == '(')
          {
              int num = recurCal(s);
              if(preSign == '+')
                  numS.push(num);
              else if(preSign == '-')
                  numS.push(-num);
          }
          // 5. 递归结束条件：如果当前是右括号，则结束遍历，返回递归结果
          else if(ch == ')')
              break;
      }
      // 计算栈中所有整数的和，就是最终的计算结果
      int result = 0;
      while(!numS.empty())
      {
          result += numS.top();
          numS.pop();
      }
      return result;
  }
public:
  int calculate(string s) {
      // 将字符串的字符存入双端队列
      deque<char> sq;
      for(int i = 0; i < s.size(); ++i)
          sq.push_back(s[i]);
      return recurCal(sq);
  }
};

执行结果： ``` 执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 44.27% 的用户内存消耗：11.6 MB, 在所有 C++ 提交中击败了 17.01% 的用户 ```

hot 100

[困难] 224. 基本计算器

题目

解答 & 代码

解法一：两个栈

解法二：一个栈存所有整数，递归处理括号