浮點(diǎn)數(shù)問題
嘗試在瀏覽器端做算術(shù)運(yùn)算的同學(xué)屎篱，多多少少都會遇到過這樣奇怪的問題：
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 等豐富的數(shù)據(jù)類型，JS 中所有數(shù)字（無論整數(shù)或小數(shù)）都只有 Number 一種類型蝇裤。其采用 IEEE 754 的 64 位雙精度浮點(diǎn)數(shù)廷支，由 1 位符號位频鉴、11 位的指數(shù)位和 52 位的尾數(shù)位組成。由于有限的存儲位數(shù)恋拍，當(dāng)數(shù)字從十進(jìn)制轉(zhuǎn)換成二進(jìn)制的尾數(shù)無窮時垛孔，多出的部分就會被截斷，在計算結(jié)束轉(zhuǎn)換為十進(jìn)制時就會出現(xiàn)浮點(diǎn)誤差施敢。為了更好理解下面例子的換算過程似炎，建議先讀這篇文章： JavaScript 浮點(diǎn)數(shù)陷阱及解法 。
舉 0.1+0.2 的例子（ 此網(wǎng)站 支持十進(jìn)制與雙精度浮點(diǎn)數(shù)的轉(zhuǎn)換）：
0.1 的雙精度浮點(diǎn)數(shù)為 0 01111111011 1001100110011001100110011001100110011001100110011010悯姊，指數(shù)位轉(zhuǎn)換成十進(jìn)制是 1019羡藐，1019 - 1023 = -4，補(bǔ)上整數(shù)部分 1 再小數(shù)點(diǎn)前移4位悯许，得 0.1 的二進(jìn)制數(shù)為 0.00011001100110011001100110011001100110011001100110011010仆嗦。按照同樣的轉(zhuǎn)換方法：
// 0.1 + 0.2
0.00011001100110011001100110011001100110011001100110011010
+ 0.0011001100110011001100110011001100110011001100110011010
= 0.0100110011001100110011001100110011001100110011001100111
// 由于雙精度的位數(shù)限制，最后一位舍去進(jìn)1先壕，得
0 01111111101 0011001100110011001100110011001100110011001100110100
// 轉(zhuǎn)換成十進(jìn)制
0.30000000000000004
解決方案
浮點(diǎn)數(shù)運(yùn)算的解決方案很簡單瘩扼，就是把小數(shù)轉(zhuǎn)換成整數(shù)后再進(jìn)行相應(yīng)的運(yùn)算。譬如：
(0.1 * 10 + 0.2 * 10) / 10 // 0.3
代碼實現(xiàn)：
function operate(left, right, operator) {
/** 固定小數(shù)位精度的寫法 **/
const precision = 2;
const factor = +'1000000000000'.slice(0, precision + 1);
/** 自動獲取最大小數(shù)位的寫法 **/
// 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
然而這樣簡陋的處理在復(fù)雜的四則運(yùn)算場景中使用會非常麻煩垃僚，我們可以實現(xiàn)一個簡單的計算引擎集绰，讓其可以處理基本的四則混合運(yùn)算（如 1 * ( 2 - 3 ) ）。
實現(xiàn)四則混合運(yùn)算
四則混合運(yùn)算涉及加谆棺、減栽燕、乘、除及括號的優(yōu)先級改淑，如果用正常的 中綴表達(dá)式 的計算思維來實現(xiàn)會比較復(fù)雜碍岔，所以我們引入逆波蘭表達(dá)式。
逆波蘭表達(dá)式
在 逆波蘭表達(dá)式 中朵夏，所有運(yùn)算符都被置于操作數(shù)后面蔼啦，因此也稱為后綴表示法。
// 正常算術(shù)式 -> 逆波蘭表達(dá)式
`a + b` -> `a b +`
`a - b + c` -> `a b - c +`
`a * ( b - c )` -> `a b c - *`
逆波蘭表達(dá)式的計算一般依賴堆棧結(jié)構(gòu)仰猖，過程非常簡單：
如為操作數(shù)則入棧捏肢，如為運(yùn)算符則把棧內(nèi)操作數(shù)彈出并計算，再重新入棧饥侵，遍歷直至棧內(nèi)只剩一個元素即為表達(dá)式的值鸵赫。
逆波蘭表達(dá)式不需要關(guān)心運(yùn)算符之間的優(yōu)先級問題，也不存在括號爆捞，可以極大限度地減小程序復(fù)雜度奉瘤。
調(diào)度場算法
借助 調(diào)度場算法 勾拉，我們可以簡單地把中綴表達(dá)式轉(zhuǎn)換成逆波蘭表達(dá)式煮甥。為了更好地描述調(diào)度場算法的流程盗温，這里初始化了三個對象：
-
Input queue：輸入隊列，一般是預(yù)處理表達(dá)式字符串后提取出的元素數(shù)組成肘； -
Operator stack：用于存儲操作符的棧卖局； -
Output queue：逆波蘭表達(dá)式元素隊列；
調(diào)度場算法流程如下双霍，其中簡稱
Output queue為隊列q砚偶，Operator stack為棧s：
- 從
Input queue中取出一個元素x；- 如果
x是操作數(shù)洒闸，直接添加到隊列q中染坯；- 如果
x是左括號(，直接壓入棧s中丘逸；- 如果
x是右括號)单鹿，從棧s中彈出運(yùn)算符添加到隊列q中，直至棧頂元素為左括號深纲，彈出左括號并丟棄掉（如果直至棧s清空依然找不到左括號仲锄，則表達(dá)式格式錯誤）；- 如果
x是除括號外的運(yùn)算符湃鹊，與棧s的棧頂元素o1比較：如果x的優(yōu)先級大于o1儒喊，則把x壓入棧s；反之币呵，從棧s中不斷彈出操作符并添加到隊列q中怀愧，直至棧頂元素的優(yōu)先級低于x，或棧頂元素為左括號(余赢，然后把x壓入棧s掸驱；- 重復(fù)步驟 1 - 5，當(dāng)
Input queue中已沒有元素時没佑，將棧s中的元素逐個彈出放入隊列q中毕贼。
JS 實現(xiàn)
function Calculate(options = {}) {
// 運(yùn)算符權(quán)重
this.weight = options.weight || {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
};
// 小數(shù)位精度
this.decimal = options.decimal || 2;
this.operatorStack = []; // 運(yùn)算符棧
this.outputQueue = []; // 逆波蘭表達(dá)式隊列
}
Calculate.prototype = {
/**
* @desc 四則運(yùn)算，浮點(diǎn)數(shù)處理
*/
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 調(diào)度場算法
*/
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('表達(dá)式格式錯誤：括號不閉合');
} 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 逆波蘭表達(dá)式求值
*/
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 校驗表達(dá)式合法性蛤奢，預(yù)處理等
* @todo 更詳細(xì)的格式校驗
*/
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
代碼實現(xiàn)已放在 github 上鬼癣，歡迎交流。
