227. Basic Calculator II

2020-06-10

原题：227. Basic Calculator II

source code

// Runtime: 128 ms, faster than 13.03% of JavaScript online submissions for Basic Calculator II.
// Memory Usage: 55.8 MB, less than 5.44% of JavaScript online submissions for Basic Calculator II.
var calculate = function (s) {
  const chs = s
    .replace(/\s/g, "")
    .replace(/([^\d])/g, "&$1&") //这里有点投机取巧了
    .split("&");
  const queue = [];
  for (let i = 0; i < chs.length; i++) {
    //注意这里不能用while(chs.length) {ch.shift()}，当case很大的时候数组操作耗时会超时
    const ch = chs[i];
    if (/\d/.test(ch)) {
      queue.push(parseInt(ch));
    } else {
      const b = parseInt(chs[++i]);
      if (ch === "+") {
        queue.push(b);
      } else if (ch === "-") {
        queue.push(-b);
      } else {
        const a = parseInt(queue.pop());
        queue.push(ch === "*" ? a * b : ~~(a / b));
      }
    }
  }

  return queue.reduce((a, b) => a + b, 0); //because the given expression is always valid
};

test cases

test("test1", () => {
  expect(calculate("3+2*2")).toEqual(7);
});

test("test2", () => {
  expect(calculate(" 3/2 ")).toEqual(1);
});

test("test3", () => {
  expect(calculate(" 3+5 / 2 ")).toEqual(5);
});

test("test4", () => {
  expect(calculate("12+37*5")).toEqual(197);
});

test("test5", () => {
  expect(calculate("1+1+1")).toEqual(3);
});

//这里还有个超大的case，一不注意就容易超时

其它解法：

Clean JavaScript solution Recommend

大体流程差不多，但是数字是逐字处理累加，非常模板的答案（面试官估计会更想看这个）。
Concise JavaScript abusing replacements

非常巧妙的切入点，有点奇淫技巧了。