LeetCode 基本计算器 II

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

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

我的算法实现，目前还没有通过，显示超出时间限制：

class Solution {
    val digitsMap = mutableMapOf(
        Pair('0', 0), Pair('1', 1),
        Pair('2', 2), Pair('3', 3),
        Pair('4', 4), Pair('5', 5),
        Pair('6', 6), Pair('7', 7),
        Pair('8', 8), Pair('9', 9)
    )
    fun calc(a: Int, c: Char, b: Int):Int {
        return when(c) {
            '*' -> a * b
            '/' -> a / b
            '-' -> a - b
            else -> a + b
        }
    }
    fun getDigit(a: Int, s: String): IntArray {
        var sum = a
        var k = 1
        for (i in 1 until s.length) {
            if (digitsMap.contains(s[i])) {
                sum = sum*10 + digitsMap[s[i]]!!
                k ++
                continue
            }
            break
        }

        return intArrayOf(sum, k)
    }
    fun calculate(s: String): Int {

        if (digitsMap.contains(s[0])) {
            val dk = digitsMap[s[0]]?.let { getDigit(it, s) }
            if (dk?.get(1) == s.length) {
                return dk[0]
            }
        }

        val symbolMap = mutableMapOf(Pair('*', 2), Pair('/', 2), Pair('+', 1), Pair('-', 1))
        val symbol = Stack<Char>()
        val digits = Stack<Int>()
        var c: Char? = null
        var i = 0
        while (i < s.length) {
            if (digitsMap.contains(s[i])){
                val dk = digitsMap[s[i]]?.let { getDigit(it, s.slice(i until s.length)) }
                if (c != null) {
                    digits.push(dk?.get(0)?.let { calc(digits.pop(), c!!, it) })
                    c = null
                } else {
                    digits.push(dk?.get(0))
                }
                i += dk?.get(1)!!
            } else if (symbolMap.contains(s[i])) {
                if (symbol.size > 0) {
                    val char = symbol.pop()

                    if (symbolMap[char]!! < symbolMap[s[i]]!!) {
                        c = s[i]
                        symbol.push(char)
                    } else {
                        c = null
                        val a = digits.pop()
                        val b = digits.pop()
                        digits.push(calc(b, char, a))
                        symbol.push(s[i])
                    }
                } else {
                    symbol.push(s[i])
                }
                i++
            }
        }
        val a = digits.pop()
        val b = digits.pop()
        return calc(b, symbol.pop(), a)
    }
}

明天继续，最先开始想的就是先实现出来，然后再优化。

补充，我觉得我实现的并没有什么问题，但是使用 kotlin 就是出现了问题，于是我使用 javascript 实现了一遍，发现居然通过了，虽然耗时也不低：

      // 将字符串转换成数组表达式
      const getExpressionArr = (s) => {
        let dStr = "";
        const arr = [];
        for (let i = 0; i < s.length; i++) {
          // 如果是空字符串则跳过
          if (s[i] === " ") continue;
          // 如果是数字，那么就累加数组
          if (!isNaN(parseInt(s[i], 10))) {
            dStr += s[i];
            continue;
          }
          // 当遇到非数组以及空格之外的符号则添加到数组中
          arr.push(dStr - 0, s[i]);
          dStr = "";
        }
        arr.push(dStr - 0)
        return arr;
      };
      // 计算
      const calc = (a, c, b) => {
        switch (c) {
          case "-":
            return a - b;
          case "*":
            return a * b;
          case "/":
            return Math.floor(a / b);
          default:
            return a + b;
        }
      };
      /**
       * @param {string} s
       * @return {number}
       */
      var calculate = function (s) {
        const swapArr = getExpressionArr(s);
        const symbolGrade = {"-": 1, "+": 1, "*":2, "/": 2}
        const digits = [],
          symbols = [];
        // 保存字符，就是那个大于前面字符的字符
        let c = null;
        for (let i = 0; i < swapArr.length; i++) {
          // 当值是数字的时候
          if (typeof swapArr[i] === "number") {
            if (c !== null) {
              // 根据条件大的字符将新的计算结果保存起来
              digits.push(calc(digits.pop(), c, swapArr[i]));
              // 操作完成以后置为 null
              c = null;
            } else {
              digits.push(swapArr[i]);
            }
          } else {
            if (symbols.length > 0) {
              const char = symbols.pop()
              // 当当前的字符等级大于前面的字符等级，那么把最新的字符保存起来
              if (symbolGrade[char] < symbolGrade[swapArr[i]]) {
                c = swapArr[i]
                symbols.push(char)
              } else {
                // 如果字符等级相同，那么先计算前面的结果
                const b = digits.pop();
                const a = digits.pop();
                digits.push(calc(a, char, b))
                symbols.push(swapArr[i])
              }
            } else {
              symbols.push(swapArr[i])
            }
          }
        }
        const b = digits.pop();
        const a = digits.pop() || 0;
        return calc(a, symbols.pop(), b)
      };

为啥 kotlin 这么慢呢，看了一圈并没有发现原因，真的很奇怪，慢得一批。

提示：

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

来源：力扣（LeetCode）