BFE.devAI解答 - JavaScript 代码题
124. 四则运算的结果

思路： 首先，我们需要将字符串转换成tokens，处理的方式参考119. 创建一个tokenizer ，即去掉空白字符后，将整个字符串分割成若干个token。

接下来，我们需要考虑计算的步骤，我们可以通过两个栈来实现，一个栈用来存储数字，另一个栈用来存储运算符号。从左到右遍历tokens，对于每个token，执行以下操作：

1. 如果当前token是数字，将其压入数字栈中。
2. 如果当前token是运算符号，分两种情况：
   • 如果当前运算符号是左括号(，将其压入运算符号栈中。
   • 如果当前运算符号是右括号)，则反复弹出运算符号栈中的元素，直到遇到左括号为止。在此过程中，从数字栈中弹出两个数字并执行相应运算，将结果压回数字栈中。
   • 如果当前运算符号不是左括号或右括号，则将其与运算符号栈栈顶元素进行比较，如果当前运算符的优先级不高于栈顶运算符的优先级，则从数字栈中弹出两个数字并执行栈顶运算符的相应运算。将结果压回数字栈中。重复比较操作直到当前运算符的优先级高于栈顶运算符的优先级，然后将当前运算符压入运算符栈中。
3. 对于最后一个token，如果其是数字，则将其压入数字栈中，如果是运算符，执行与上一步类似的操作，直到所有的token处理完毕为止。
4. 最后，从数字栈中弹出唯一的数字即为计算结果。

需要注意：

1. 运算符的优先级，乘和除的优先级高于加和减。
2. 当遇到除法计算时，需要判断除数是否为0。若为0，则返回Infinity或者- Infinity 。
3. 当遇到负数计算时，需要处理负号，可以将减号判断是否是负号，若是，则将其转为减号。
4. 当遇到多个连续的符号，可以将其当作一个符号处理，例如“- 1+23”即为“-1+23”。

完整代码：

function calculate(str) {
  // 将字符串转换成tokens
  const tokens = tokenize(str);

  // 运算符优先级
  const priority = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
  };

  // 数字栈和运算符栈
  const numStack = [];
  const opStack = [];

  // 遍历tokens
  tokens.forEach(token => {
    if (isNumber(token)) {
      // 如果是数字，将其压入数字栈中
      numStack.push(+token);
    } else if (token === '(') {
      // 如果是左括号，将其压入运算符栈中
      opStack.push(token);
    } else if (token === ')') {
      // 如果是右括号，弹出运算符栈中的元素，并执行相应运算
      while (opStack[opStack.length - 1] !== '(') {
        const op = opStack.pop();
        const num2 = numStack.pop();
        const num1 = numStack.pop();
        numStack.push(calculateResult(num1, op, num2));
      }
      opStack.pop(); // 弹出左括号
    } else {
      // 如果是运算符，比较优先级，并执行相应运算
      while (
        opStack.length > 0 &&
        opStack[opStack.length - 1] !== '(' &&
        priority[token] <= priority[opStack[opStack.length - 1]]
      ) {
        const op = opStack.pop();
        const num2 = numStack.pop();
        const num1 = numStack.pop();
        numStack.push(calculateResult(num1, op, num2));
      }
      opStack.push(token);
    }
  });

  // 处理剩余的运算符
  while (opStack.length > 0) {
    const op = opStack.pop();
    const num2 = numStack.pop();
    const num1 = numStack.pop();
    numStack.push(calculateResult(num1, op, num2));
  }

  return numStack.pop();
}

// 判断一个token是否为数字
function isNumber(token) {
  return /^\d+$/.test(token);
}

// 计算两个数字的运算结果
function calculateResult(num1, op, num2) {
  let result;
  switch (op) {
    case '+':
      result = num1 + num2;
      break;
    case '-':
      result = num1 - num2;
      break;
    case '*':
      result = num1 * num2;
      break;
    case '/':
      if (num2 === 0) {
        return num1 > 0 ? Infinity : -Infinity;
      }
      result = num1 / num2;
      break;
  }
  return result;
}

// 将字符串转换成tokens
function tokenize(str) {
  const tokens = [];
  let i = 0;
  while (i < str.length) {
    const char = str[i];
    if (char === ' ') {
      // 跳过空格
      i++;
      continue;
    }
    if (isNumberChar(char)) {
      // 合并数字字符
      let j = i + 1;
      while (j < str.length && isNumberChar(str[j])) {
        j++;
      }
      tokens.push(str.slice(i, j));
      i = j;
      continue;
    }
    // 处理连续的符号
    if (char === '-' || char === '+') {
      if (isOp(tokens[tokens.length - 1]) || !tokens.length) {
        let j = i + 1;
        while (j < str.length && str[j] === char) {
          j++;
        }
        const sign = j % 2 === 0 ? '+' : char;
        tokens.push(sign);
        i = j;
        continue;
      }
    }
    // 其他情况直接作为token
    tokens.push(char);
    i++;
  }
  return tokens;
}

// 判断一个字符是否为数字字符
function isNumberChar(char) {
  return /\d/.test(char);
}

// 判断一个token是否为运算符
function isOp(token) {
  return ['+', '-', '*', '/', '(', ')'].indexOf(token) !== -1;
}