772. 基本计算器 III

题设¶

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，乘号 *，除号 /，非负整数和空格。

输入: "1 + 1"
输出: 2

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

输入: "2*(5+5*2)/3+(6/2+8)"
输出: 21

步骤一：仅加法¶

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  const queue = [];
  for(let i = 0; i < s.length; i++) {
    queue.push(s[i])
  }
  queue.push('+'); // 处理最后一次加法

  let num = 0, sum = 0;

  while (queue.length > 0) {
    const c = queue.shift();

    if (/\d/.test(c)) {
      num = num * 10 + Number(c);
    } else {
      sum += num;
      num = 0;
    }
  }

  return sum;
};

步骤二：支持减法¶

加入 sign 标志当前 num 符号

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  const queue = [];
  for(let i = 0; i < s.length; i++) {
    if (s[i] !== ' ') { // 过滤空格
      queue.push(s[i])
    }
  }
  queue.push('+'); // 处理最后一次加法

  let num = 0, sum = 0;
  let sign = '+'; // 当前 num 符号标志变量

  while (queue.length > 0) {
    const c = queue.shift();

    if (/\d/.test(c)) {
      num = num * 10 + Number(c);
    } else {
      if (sign === '-') {
        sum -= num;
      } else if (sign === '+'){
        sum += num;
      }
      num = 0;
      sign = c;
    }
  }

  return sum;
};

步骤三：支持乘法和除法¶

考虑符号优先级
堆栈缓存高优先级计算结果

var calculate = function(s) {
  const queue = [];
  for(let i = 0; i < s.length; i++) {
    if (s[i] !== ' ') { // 过滤空格
      queue.push(s[i])
    }
  }
  queue.push('+'); // 处理最后一次加法

  let num = 0;
  let sign = '+'; // 当前 num 符号标志变量
  let stack = [];

  while (queue.length > 0) {
    const c = queue.shift();

    if (/\d/.test(c)) {
      num = num * 10 + Number(c);
    } else {
      if (sign === '+') {
        stack.push(num);
      } else if (sign === '-'){
        stack.push(-num);
      } else if (sign === '*') {
        stack.push(stack.pop() * num);
      } else if (sign === '/') {
        stack.push(stack.pop() / num);
      }

      num = 0;
      sign = c;
    }
  }

  let sum = 0;
  for(let i = 0; i < stack.length; i++) {
    sum += stack[i];
  }

  return sum;
};

步骤四：支持小括号¶

递归计算括号内表达式
遇到左括号 ( 时，开始递归计算括号内表达式
遇到右括号 ) 时，表明小括号计算结束，结束循环，返回当前总和

var calculate = function(s) {
  const queue = [];
  for(let i = 0; i < s.length; i++) {
    if (s[i] !== ' ') { // 过滤空格
      queue.push(s[i])
    }
  }
  queue.push('+'); // 处理最后一次加法

  return _calculate(queue);
};

var _calculate = function(queue) {
  let sign = '+'; // 当前 num 符号标志变量
  let num = 0;
  let stack = [];

  while (queue.length > 0) {
    const c = queue.shift();

    if (/\d/.test(c)) {
      num = num * 10 + Number(c);
    } else if (c === '(') {
      // 遇到小括号，开始递归计算号内表达式，将计算结果赋给当前 num
      num = _calculate(queue);
    } else {
      if (sign === '+') {
        stack.push(num);
      } else if (sign === '-'){
        stack.push(-num);
      } else if (sign === '*') {
        stack.push(stack.pop() * num);
      } else if (sign === '/') {
        stack.push(stack.pop() / num);
      }

      num = 0;
      sign = c;

      // 遇到右括号退出循环，返回当前计算总和
      if (c === ')') {
        break;
      }
    }
  }

  let sum = 0;
  for(let i = 0; i < stack.length; i++) {
    sum += stack[i];
  }

  return sum;
};