JavaScript实现四则混合运算

背景

最近在项目中需要自己解析四则混合运算，如果只是简单的加减乘除运算，我相信对大家来说没有任何困难，但是实现带括号的四则运算，还是有一定的难度的。

• 操作数：小数、整数
• 运算符：加、减、乘、除
• 分界符：圆括号 ( ) ， 用于指示运算的先后顺序

这里使用逆波兰表达式解决数值运算以及括号带来的优先级提升问题。

逆波兰表达式

• 中缀表达式(Infix Notation)
  是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间。比如1 + 2 + 3

• 前缀表达式(Prefix Notation)
  是指将运算符写在前面、操作数写在后面、不包含括号的表达式，而且为了纪念其发明者波兰数学家 Jan Lukasiewicz 所以前缀表达式也叫做波兰表达式。比如- 1 + 2 3

• 后缀表达式(Postfix Notation)
  与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -

前后缀表达式的出现是为了方便计算机处理，它的运算符是按照一定的顺序出现，所以求值过程中并不需要使用括号来指定运算顺序，也不需要考虑运算符号（比如加减乘除）的优先级。逆波兰表达式在编译技术中有着普遍的应用。

中缀表达式转换成后缀表达式算法：

1. 从左至右扫描一中缀表达式。
2. 若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3. 若读取的是运算符：
   1. 该运算符为左括号”(“，则直接存入运算符堆栈。
   2. 该运算符为右括号”)”，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
   3. 该运算符为非括号运算符：
      1. 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
      2. 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
      3. 若比运算符堆栈栈顶的运算符优先级低或者优先级相等，则输出栈顶运算符到操作数堆栈，直到比运算符堆栈栈顶的运算符优先级低或者为空时才将当前运算符压入运算符堆栈。
   4. 当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

流程图如下所示：

逆波兰表达式求值算法：

1. 循环扫描语法单元的项目。
2. 如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3. 如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4. 如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5. 将运算结果重新压入堆栈。
6. 重复步骤 2-5，堆栈中即为结果值。

算法实现

• 中缀表达式转换成逆波兰表达式

const operatorRand = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2,
};

/**
 * 中缀表达式转换成逆波兰表达式
 * @param {string[]} str 中缀表达式
 */
function convert(inputArr) {
  if (!Array.isArray(inputArr) || inputArr.length === 0) return [];

  const operatorArr = [];
  const outputArr = [];

  inputArr.forEach(input => {
    if (!Number.isNaN(Number(input))) {
      // 如果是数字，只接输出
      outputArr.push(input);
    } else if (input === '(') {
      // 如果是左括号，入操作符栈
      operatorArr.push(input);
    } else if (input === ')') {
      // 如果是右括号，循环输出，知道匹配到左括号为止
      while (operatorArr.length > 0) {
        const operator = operatorArr.pop();
        if (operator === '(') break;
        outputArr.push(operator);
      }
    } else {
      // 如果是运算符
      while (operatorArr.length >= 0) {
        const topOperator = operatorArr[operatorArr.length - 1];

        // 如果运算符栈为空，或者栈顶运算符是(，或者当前运算符优先级比栈顶运算符优先级高
        if (
          operatorArr.length === 0 ||
          topOperator === '(' ||
          operatorRand[input] > operatorRand[topOperator]
        ) {
          operatorArr.push(input);
          break;
        } else {
          outputArr.push(operatorArr.pop());
        }
      }
    }
  });

  // 输入循环结束，如果运算符栈不为空，循环输出
  while (operatorArr.length > 0) {
    outputArr.push(operatorArr.pop());
  }

  return outputArr;
}

• 逆波兰算法求值

function compute(leftNum, rightNum, operator) {
  switch (operator) {
    case '+':
      return leftNum + rightNum;
    case '-':
      return leftNum - rightNum;
    case '*':
      return leftNum * rightNum;
    default:
      // 除法
      return leftNum / rightNum;
  }
}

/**
 * 计算逆波兰表达式
 * @param {string} str 逆波兰表达式
 */
export function count(reversePolishArr) {
  if (!Array.isArray(reversePolishArr) || reversePolishArr.length === 0) return 0;

  const tmpArr = [];

  reversePolishArr.forEach(input => {
    if (!Number.isNaN(Number(input))) {
      // 数字接直接push
      tmpArr.push(Number(input));
    } else {
      // 运算符
      const num1 = tmpArr.pop();
      const num2 = tmpArr.pop();

      if (isNaN(num1) || isNaN(num2)) {
        throw new Error(`无效的表达式：${reversePolishArr.join(',')}`);
      }

      tmpArr.push(compute(num2, num1, input));
    }
  });

  return Number(tmpArr[0].toFixed(3));
}

完整代码请参考：https://github.com/zubincheung/js-rpn