利用栈实现四则混合运算引擎

浮点数问题

尝试在浏览器端做算术运算的同学，多多少少都会遇到过这样奇怪的问题：

0.1 + 0.2    // 0.30000000000000004
1 - 0.9    // 0.09999999999999998
19.9 * 100    // 1989.9999999999998
0.3 / 0.1    // 2.9999999999999996

这是由于 JS 是一门弱类型语言，不像 Java 有 int、float、double 等丰富的数据类型，JS 中所有数字（无论整数或小数）都只有 Number 一种类型。其采用 IEEE 754 的 64 位双精度浮点数，由 1 位符号位、11 位的指数位和 52 位的尾数位组成。由于有限的存储位数，当数字从十进制转换成二进制的尾数无穷时，多出的部分就会被截断，在计算结束转换为十进制时就会出现浮点误差。为了更好理解下面例子的换算过程，建议先读这篇文章： JavaScript 浮点数陷阱及解法 。

举 0.1+0.2 的例子（ 此网站 支持十进制与双精度浮点数的转换）：

0.1 的双精度浮点数为 0 01111111011 1001100110011001100110011001100110011001100110011010，指数位转换成十进制是 1019，1019 - 1023 = -4，补上整数部分 1 再小数点前移4位，得 0.1 的二进制数为 0.00011001100110011001100110011001100110011001100110011010。按照同样的转换方法：

// 0.1 + 0.2
  0.00011001100110011001100110011001100110011001100110011010
+ 0.0011001100110011001100110011001100110011001100110011010
= 0.0100110011001100110011001100110011001100110011001100111

// 由于双精度的位数限制，最后一位舍去进1，得
0 01111111101 0011001100110011001100110011001100110011001100110100

// 转换成十进制
0.30000000000000004

解决方案

浮点数运算的解决方案很简单，就是把小数转换成整数后再进行相应的运算。譬如：

(0.1 * 10 + 0.2 * 10) / 10    // 0.3

代码实现：

function operate(left, right, operator) {
  /** 固定小数位精度的写法 **/
  const precision = 2;
  const factor = +'1000000000000'.slice(0, precision + 1);

  /** 自动获取最大小数位的写法 **/
  // const lPrecision = (left.toString().split('.')[1] || '').length;
  // const rPrecision = (right.toString().split('.')[1] || '').length
  // const factor = Math.pow(10, Math.max(lPrecision, rPrecision));

  if (operator === '+') {
    return Math.round(left * factor + right * factor) / factor;
  } else if (operator === '-') {
    return Math.round(left * factor - right * factor) / factor;
  } else if (operator === '*') {
    return Math.round(left * factor * right * factor) / Math.pow(factor, 2);
  } else if (operator === '/') {
    return Math.round(left / right * factor) / factor;
  }
}

operate(0.1, 0.2,'+');    // 0.3
operate(0.3, 0.1,'/');    // 3

然而这样简陋的处理在复杂的四则运算场景中使用会非常麻烦，我们可以实现一个简单的计算引擎，让其可以处理基本的四则混合运算（如 1 * ( 2 - 3 ) ）。

实现四则混合运算

四则混合运算涉及加、减、乘、除及括号的优先级，如果用正常的 中缀表达式 的计算思维来实现会比较复杂，所以我们引入逆波兰表达式。

逆波兰表达式

在 逆波兰表达式 中，所有运算符都被置于操作数后面，因此也称为后缀表示法。

// 正常算术式 -> 逆波兰表达式
`a + b`  ->  `a b +`
`a - b + c`  ->  `a b - c +`
`a * ( b - c )`  ->  `a b c - *`

逆波兰表达式的计算一般依赖堆栈结构，过程非常简单：

如为操作数则入栈，如为运算符则把栈内操作数弹出并计算，再重新入栈，遍历直至栈内只剩一个元素即为表达式的值。

逆波兰表达式不需要关心运算符之间的优先级问题，也不存在括号，可以极大限度地减小程序复杂度。

调度场算法

借助 调度场算法 ，我们可以简单地把中缀表达式转换成逆波兰表达式。为了更好地描述调度场算法的流程，这里初始化了三个对象：

• Input queue：输入队列，一般是预处理表达式字符串后提取出的元素数组；
• Operator stack：用于存储操作符的栈；
• Output queue：逆波兰表达式元素队列；

调度场算法流程如下，其中简称 Output queue 为队列 q，Operator stack 为栈 s：

1. 从Input queue中取出一个元素 x；
2. 如果 x 是操作数，直接添加到队列 q 中；
3. 如果 x 是左括号 ( ，直接压入栈 s 中；
4. 如果 x 是右括号 )，从栈 s 中弹出运算符添加到队列q中，直至栈顶元素为左括号，弹出左括号并丢弃掉（如果直至栈 s 清空依然找不到左括号，则表达式格式错误）；
5. 如果 x 是除括号外的运算符，与栈 s 的栈顶元素 o1 比较：如果 x 的优先级大于 o1，则把 x 压入栈 s；反之，从栈 s 中不断弹出操作符并添加到队列 q 中，直至栈顶元素的优先级低于 x，或栈顶元素为左括号 (，然后把 x 压入栈 s；
6. 重复步骤 1 - 5，当 Input queue 中已没有元素时，将栈 s 中的元素逐个弹出放入队列 q 中。

JS 实现

function Calculate(options = {}) {
  // 运算符权重
  this.weight = options.weight || {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
  };
  // 小数位精度
  this.decimal = options.decimal || 2;
  this.operatorStack = [];    // 运算符栈
  this.outputQueue = [];      // 逆波兰表达式队列
}

Calculate.prototype = {

  /**
   * @desc 四则运算，浮点数处理
   */
  operate(left, right, operator) {
    const factor = +'1000000000000'.slice(0, this.decimal + 1);
    if (operator === '+') {
      return Math.round(left * factor + right * factor) / factor;
    } else if (operator === '-') {
      return Math.round(left * factor - right * factor) / factor;
    } else if (operator === '*') {
      return Math.round(left * factor * right * factor) / Math.pow(factor, 2);
    } else if (operator === '/') {
      return Math.round(left / right * factor) / factor;
    }
  },

  /**
   * @desc 调度场算法
   */
  shuntingYard(token) {
    if (!isNaN(+token)) {
      this.outputQueue.push(+token);
    } else if (token === '(') {
      this.operatorStack.push(token);
    } else if (token === ')') {
      let top = this.operatorStack.pop();
      while (top && top !== '(') {
        this.outputQueue.push(top);
        top = this.operatorStack.pop();
      }
      if (!top) throw new Error('表达式格式错误：括号不闭合');
    } else {
      let top = this.operatorStack.pop();
      while (top && top !== '(' && this.weight[token] <= this.weight[top]) {
        this.outputQueue.push(top);
        top = this.operatorStack.pop();
      }
      top ? this.operatorStack.push(top, token) : this.operatorStack.push(token);
    }
  },

  /**
   * @desc 逆波兰表达式求值
   */
  calRpn() {
    const stack = [];
    while (this.outputQueue.length) {
      let token = this.outputQueue.shift();
      if (typeof token === 'number') {
        stack.push(token);
      } else {
        const right = stack.pop();
        const left = stack.pop();
        if (!right || !left) throw new Error('计算错误');
        stack.push(this.operate(left, right, token));
      }
    }
    if (stack.length !== 1) throw new Error('计算错误');
    return stack[0];
  },

  /**
   * @desc 校验表达式合法性，预处理等
   * @todo 更详细的格式校验
   */
  preValid(expStr) {
    return expStr;
  },

  run(expStr) {
    this.operatorStack = [];
    this.outputQueue = [];

    let chars;
    const str = this.preValid(expStr);
    const reg = /([\d\.]+|[\(\)\+\-\*\/])/g;
    while ((chars = reg.exec(str)) !== null) {
      this.shuntingYard(chars[0]);
    }
    while (this.operatorStack.length) {
      this.outputQueue.push(this.operatorStack.pop());
    }
    return this.calRpn()
  }
}

const cal = new Calculate();
cal.run('1-(2+3*8)');    // -25

代码实现已放在 github 上，欢迎交流。

Reference

• 维基百科：双精度浮点数
• 维基百科：逆波兰表示法
• 维基百科：调度场算法
• JavaScript 浮点数陷阱及解法