题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

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

示例 2：
输入：s = “ 3/2 “
输出：1

示例 3：
输入：s = “ 3+5 / 2 “
输出：5

提示：

  • 1 <= s.length <= 3 * 105
  • s 由整数和算符 (‘+’, ‘-‘, ‘*’, ‘/‘) 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

思路

  • 用栈存储每次计算的 num ，因为num可能为10以上的数，所以需要一个num变量
  • 当遍历的当前字符串不是数字
    • “+”：直接推入栈中
    • “-“：负数推入栈中，为了之后直接进行加法运算
    • ““：从栈中弹出当前的num
    • “/“：从栈中弹出/当前的num | 0
  • 思考：
    • 如果只有一个number值怎么办：
      • 默认preSign给”+”先将第一个number推进栈
      • 需要对遍历的每一个字符串进行记录preSign=s[i] ```javascript const calculate = function (s) { s = s.replace(/\s/g, ‘’) let num = 0 const stackNum = [] let preSign = ‘+’ for (let i = 0; i < s.length; i++) { if (!isNaN(Number(s[i]))) { // 存储每次计算的 num num = num 10 + Number(s[i]) } if (isNaN(Number(s[i])) || i === s.length - 1) { if (preSign === “+”) { stackNum.push(Number(num)) } else if (preSign === “-“) { stackNum.push(-Number(num)) } else if (preSign === ““) { stackNum.push(Math.floor(stackNum.pop() * num)) } else if (preSign === “/“) { stackNum.push(Math.floor(stackNum.pop() / num | 0)) } preSign = s[i]; num = 0 } } let add = 0 while (stackNum.length) { add += stackNum.pop() } return add };

calculate(“42+2”) ```

复杂度分析

  • 遍历次数最大是字符串长度
  • O(N)