昨天發了一個面試題： "關於一道面試題【字元串 '1 + (5 2) 3'，怎麼算出結果為10，'eval'除外】" ，受到了各位大大的指點，用一個比較簡單的解法就能夠計算出來，因此自己在下班後按照各位的指點又實現了一遍，這裡貼出來供大家參考。 瞭解首碼、中綴、尾碼表達式 關於概念這裡簡單貼一下，想 ...
昨天發了一個面試題：關於一道面試題【字元串 '1 + (5 - 2) * 3'，怎麼算出結果為10，'eval'除外】，受到了各位大大的指點，用一個比較簡單的解法就能夠計算出來，因此自己在下班後按照各位的指點又實現了一遍，這裡貼出來供大家參考。
瞭解首碼、中綴、尾碼表達式
關於概念這裡簡單貼一下，想瞭解更多的可以自行Google
- 首碼表達式：是一種沒有括弧的算術表達式，與中綴表達式不同的是，其將運算符寫在前面，操作數寫在後面。為紀念其發明者波蘭數學家Jan Lukasiewicz，首碼表達式也稱為“波蘭式”。例如，- 1 + 2 3，它等價於1-(2+3)。
- 中綴表達式：是一個通用的算術或邏輯公式表示方法， 操作符是以中綴形式處於操作數的中間（例：3 + 4），中綴表達式是人們常用的算術表示方法。
- 尾碼表達式：指的是不包含括弧，運算符放在兩個運算對象的後面，所有的計算按運算符出現的順序，嚴格從左向右進行，尾碼表達式也稱為“逆波蘭式”。例如：1 2 3 4 + * + 5 +
註： 與首碼表達式（例：+ 3 4）或尾碼表達式（例：3 4 +）相比，中綴表達式不容易被電腦解析，但仍被許多程式語言使用，因為它符合人們的普遍用法。
中綴表達式如何轉換為尾碼表達式以及運算
一、 將中綴表達式轉換成尾碼表達式演算法：
- 從左至右掃描一中綴表達式。
- 若讀取的是操作數，則判斷該操作數的類型，並將該操作數存入操作數堆棧
- 若讀取的是運算符
- 該運算符為左括弧"("，則直接存入運算符堆棧。
- 該運算符為右括弧")"，則輸出運算符堆棧中的運算符到操作數堆棧，直到遇到左括弧為止。
- 該運算符為非括弧運算符：
- 若運算符堆棧棧頂的運算符為括弧，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序高或相等，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序低或者優先順序相等，則輸出棧頂運算符到操作數堆棧，直到比運算符堆棧棧頂的運算符優先順序低或者為空時才將當前運算符壓入運算符堆棧。
- 當表達式讀取完成後運算符堆棧中尚有運算符時，則依序取出運算符到操作數堆棧，直到運算符堆棧為空。
二、逆波蘭表達式求值演算法：
- 迴圈掃描語法單元的項目。
- 如果掃描的項目是操作數，則將其壓入操作數堆棧，並掃描下一個項目。
- 如果掃描的項目是一個二元運算符，則對棧的頂上兩個操作數執行該運算。
- 如果掃描的項目是一個一元運算符，則對棧的最頂上操作數執行該運算。
- 將運算結果重新壓入堆棧。
- 重覆步驟2-5，堆棧中即為結果值。
看上面的概念我都看暈了，接下來以一個例子講解：
1 + 2 * (3 + 4) + 5
originArr 代表字元串轉化為數組之後的數組
operatorArr 代表運算符數組
reverseArr 代表尾碼表達式數組
下麵是一步一步的過程
originArr: ["1","+","2","*","(","3","+","4",")","+","5"]
operatorArr: []
reverseArr: ["1"]
operatorArr: ["+"]
reverseArr: ["1"]
operatorArr: ["+"]
reverseArr: ["1","2"]
operatorArr: ["+","*"]
reverseArr: ["1","2"]
operatorArr: ["+","*","("]
reverseArr: ["1","2"]
operatorArr: ["+","*","("]
reverseArr: ["1","2","3"]
operatorArr: ["+","*","(","+"]
reverseArr: ["1","2","3"]
operatorArr: ["+","*","(","+"]
reverseArr: ["1","2","3","4"]
operatorArr: ["+","*"]
reverseArr: ["1","2","3","4","+"]
operatorArr: ["+"]
reverseArr: ["1","2","3","4","+","*","+"]
operatorArr: ["+"]
reverseArr: ["1","2","3","4","+","*","+","5"]
operatorArr: []
reverseArr: ["1","2","3","4","+","*","+","5","+"]實現過程
這裡直接貼代碼，在代碼中有詳細的解析
const ADD = '+'; // 加常量
const SUB = '-'; // 減常量
const MUL = '*'; // 乘常量
const DIV = '/'; // 除常量
const MOD = '%'; // 取餘常量
const priorityMap = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'%': 2
};
const str = '1 + 2';
const str2 = '1 + 2 - 3';
const str3 = '1 + 2 + 3 / 4';
const str4 = '1 + 2 + 3 / 4 % 5';
const str5 = '1 + 2 * (3 + 4) + 5';
const str6 = '(1 + 2) * (3 + 4) + 5';
const str7 = '((1 + 2) + 3 / (4 % 6)) * 6';
/**
* 獲取逆波蘭數組
* @param string str 運算字元串
* @return Array 逆波蘭數組
*/
function reversePolish(str) {
str = str.replace(/\s*/g, '');
const originArr = str.split('');
// 保存最終逆波蘭數組的數組
let reverseArr = [];
// 保存運算符的數組
let operatorArr = [];
originArr.forEach(origin => {
// 如果是數字，則直接push最終逆波蘭的數組
if (!isNaN(Number(origin))) {
reverseArr.push(origin);
} else {
// 如果運算符數組為空，說明還沒有遇到運算符
// 直接push進棧
if (operatorArr.length === 0) {
operatorArr.push(origin);
} else {
// 進行比較，決定是入棧還是出棧
// 1. '*/%'這三類因為具有最高優先順序，所以直接push
// 2. '('因為不和誰進行比較，也可以直接push
const originPriority = priorityMap[origin];
if (originPriority === 2 || origin === '(') {
operatorArr.push(origin);
} else {
// 獲取運算符中是否存在了'('，為後面的判斷作准備
const lastBracketIndex = operatorArr.lastIndexOf('(');
// 如果迴圈到了')'，說明運算數組中必定存在一個'('
// 則直接截取從最後到'('的數組，直接push進返回結果的數組中
if (origin === ')') {
const includeLeftBracketArr = operatorArr.splice(lastBracketIndex).slice(1).reverse();
reverseArr = reverseArr.concat(includeLeftBracketArr);
} else {
// 否則，我只需要比較運算數組中最後一個運算符就好
// 如果迴圈出的運算符的優先順序大於或者等於最後一個運算符的優先順序，那麼直接push
const topOperator = operatorArr[operatorArr.length - 1];
if (originPriority >= priorityMap[topOperator]) {
operatorArr.push(origin);
} else {
// 否則，就需要判斷運算符數組中是否已經存在了'('
// 如果存在'('， 則我只需要截取到'('的數組就可以了
// 如果不存在，我只需要將整個運算符數組進行拼接就好，因為迴圈出來的運算符的優先順序肯定是小於或者等於運算符數組中的優先順序的
if (lastBracketIndex !== -1) {
const includeLeftBracketArr = operatorArr.splice(lastBracketIndex + 1).reverse();
reverseArr = reverseArr.concat(includeLeftBracketArr);
} else {
reverseArr = reverseArr.concat(operatorArr.reverse());
operatorArr = [];
}
// 最後，把這個運算符push進棧
operatorArr.push(origin);
}
}
}
}
}
});
// 最後，如果運算符中還有運算符，進行拼接就好了
if (operatorArr.length > 0) {
reverseArr = reverseArr.concat(operatorArr.reverse());
operatorArr = [];
}
return reverseArr;
}
/**
* 真正的計算過程
* @param string left 左邊的數字字元串
* @param string right 右邊的數字字元串
* @param string opr 運算符
* @return number 結果
*/
function cacl(left, right, opr) {
left = Number(left);
right = Number(right);
switch(opr) {
case MUL:
return left * right;
case DIV:
return left / right;
case MOD:
return left % right;
case ADD:
return left + right;
case SUB:
return left - right;
default:
return 0;
}
}
/**
* 計算逆波蘭數組中的值
* @param string str 運算字元串
* @return number 結果
*/
function myEval(str) {
const reversePolishArr = reversePolish(str);
const tempArr = [];
reversePolishArr.forEach(origin => {
// 數字直接push
if (!isNaN(Number(origin))) {
tempArr.push(origin);
} else {
// 如果遇到運算符，則pop出前兩個數
// 根據運算符得出結果後再push
const num1 = tempArr.pop();
const num2 = tempArr.pop();
const result = cacl(num2, num1, origin);
tempArr.push(result);
}
});
return tempArr[0];
}
console.time('myEval');
console.log('myEval: ', myEval(str));
console.log('myEval: ', myEval(str2));
console.log('myEval: ', myEval(str3));
console.log('myEval: ', myEval(str4));
console.log('myEval: ', myEval(str5));
console.log('myEval: ', myEval(str6));
console.log('myEval: ', myEval(str7));
console.timeEnd('myEval')
console.time('eval');
console.log('eval: ', eval(str));
console.log('eval: ', eval(str2));
console.log('eval: ', eval(str3));
console.log('eval: ', eval(str4));
console.log('eval: ', eval(str5));
console.log('eval: ', eval(str6));
console.log('eval: ', eval(str7));
console.timeEnd('eval')運行時間：
因為換了臺電腦，所以原生eval對比上一篇文章中有比較大的影響，但是就時間的對比來說還是有接近3倍左右的差距。
