leetcode：227. 基本计算器 II

题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例：

  1. 输入：s = "3+2*2"
  2. 输出：7
  1. 输入：s = "3+2*2"
  2. 输出：7
  1. 输入：s = " 3+5 / 2 "
  2. 输出：5
  1. 输入：s = "1-1+1"
  2. 输出：1

解答 & 代码

栈：保存整数

  • 核心思想：先进行所有乘除操作（乘除法优先于加减法体现在，乘除法可以和栈顶的数结合，而加减法只能把自己放入栈）
    • 如果是加号 or 减号之后的数字，直接将数字压入栈中（减号取相反数）
    • 如果是乘除号之后的数字，则直接先于栈顶元素进行乘除法计算，并替换栈顶元素为计算后的结果
  1. 遍历字符串，并用变量 preSign 记录整数之前的符号（初始化为 '+')
    1. 每次遍历完一个整数，根据 preSign 决定操作：
      1. 如果 preSign 是乘除号，则将栈顶数值和当前整数相乘 or 相除后，替换栈顶
      2. 如果 preSign 是减号，则将当前整数的相反数压入栈中
      3. 如果 preSign 是加号，则将当前整数直接压入栈中

  2. 最后将栈中所有整数相加，就是最终的计算结果

    1. class Solution {
    2. public:
    3.  int calculate(string s) {
    4.      stack<int> numS;        // 栈，保存整数
    5.      char preSign = '+';        // 之前的符号，初始化为 '+'
    6.      int idx = 0;
    7.      // 遍历字符串
    8.      while(idx < s.size())
    9.      {
    10.          char ch = s[idx];
    11.          // 1. 若当前字符是空格，则跳过
    12.          if(ch == ' ')
    13.              ++idx;
    14.          // 2. 若当前字符是符号，则更新 preSign
    15.          else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
    16.          {
    17.              preSign = ch;
    18.              ++idx;
    19.          }
    20.          // 3. 若当前字符是数字，则遍历完该整数
    21.          else if(ch >= '0' && ch <= '9')
    22.          {
    23.              // 遍历得到当前整数
    24.              int num = 0;
    25.              while(idx < s.size() && s[idx] >= '0' && s[idx] <= '9')
    26.              {
    27.                  num = num * 10 + (s[idx] - '0');
    28.                  ++idx;
    29.              }
    31.              // 如过 preSign 是 * or /，则将栈顶数值和当前整数相乘 or 相除，来替换栈顶
    32.              if(preSign == '*')
    33.                  numS.top() *= num;
    34.              else if(preSign == '/')
    35.                  numS.top() /= num;
    36.              // 如果 preSign 是 -，则将当前整数的相反数压入栈中
    37.              else if(preSign == '-')
    38.                  numS.push(-num);
    39.              // 如果 preSign 是 +，则直接将当前整数压入栈中
    40.              else
    41.                  numS.push(num);
    42.          }
    43.      }
    45.      // 将栈中所有整数相加，就是最终的计算结果
    46.      int result = 0;
    47.      while(!numS.empty())
    48.      {
    49.          result += numS.top();
    50.          numS.pop();
    51.      }
    52.      return result;
    53.  }
    54. };

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

  • 时间复杂度 O(N)：
  • 空间复杂度 O(N)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 96.49% 的用户
  4. 内存消耗：8.4 MB, 在所有 C++ 提交中击败了 63.84% 的用户