浮点数问题
尝试在浏览器端做算术运算的同学，多多少少都会遇到过这样奇怪的问题：
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：
- 从
Input queue中取出一个元素x；- 如果
x是操作数，直接添加到队列q中；- 如果
x是左括号(，直接压入栈s中；- 如果
x是右括号)，从栈s中弹出运算符添加到队列q中，直至栈顶元素为左括号，弹出左括号并丢弃掉（如果直至栈s清空依然找不到左括号，则表达式格式错误）；- 如果
x是除括号外的运算符，与栈s的栈顶元素o1比较：如果x的优先级大于o1，则把x压入栈s；反之，从栈s中不断弹出操作符并添加到队列q中，直至栈顶元素的优先级低于x，或栈顶元素为左括号(，然后把x压入栈s；- 重复步骤 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 上，欢迎交流。
