最近徘徊在找工作和繼續留任的糾結之中，在朋友的慫恿下去參加了一次面試，最後一道題目是： 寫一個函數，輸入一個字元串的運算式，返回計算之後的結果。例如這樣的： '1 + (5 2) 3'，計算出結果為10 最開始看到這個題目的時候，我腦中的第一反應就是 ，真的太直接了。但是我就不明白為什麼這竟然是最後 ...
最近徘徊在找工作和繼續留任的糾結之中，在朋友的慫恿下去參加了一次面試，最後一道題目是：
寫一個函數，輸入一個字元串的運算式，返回計算之後的結果。例如這樣的： '1 + (5 - 2) * 3'，計算出結果為10
最開始看到這個題目的時候，我腦中的第一反應就是eval，真的太直接了。但是我就不明白為什麼這竟然是最後一道題目，我也不知道為什麼還會考eval的運用，因此當時也很猶豫要不要用eval。因為eval有一系列的問題：
- eval會改變當前的作用域，除非函數直接調用，並且是
eval本身執行 - eval可能會造成xss攻擊，除非你對其中的字元串特別放心
當時只是覺得可以使用正則匹配運算符，然後使用遞歸計算，就只寫了個思路，回來之後就按照這個方式實現一下。這裡作為自己的解決方式，測試用例設計的也不夠全面，如果各位有更好的方法，可以拿出來分享。
PS: 這是之後採用了各位大大們的指點寫出來的尾碼表達式解決辦法，但是被博客園移除了首頁，暫時還不知道為什麼。
如果我拿個'1 + (5 - 2) * 3'這個式子我是怎麼想的：
- 看成 1 + x * 3
- 算出x，x的計算就需要匹配括弧，這個倒不是很難
- 計算出x之後，替換成 1 + 3 * 3
- 之後按照
/%*的優先順序要大於+-，先匹配計算出 3 * 3 - 替換成 1 + 9
- 最後得出 10
講白了就是有括弧，先計算括弧中的算是，然後進行結果替換之後再進行後面的運算，整體而言就是一系列的'遞歸 + 匹配'。
/**
* myEval
* @param string str 字元串
* @return 返回計算後的值 [description]
*/
function myEval(str) {
// 如果包含括弧，則先進括弧中的計算
// 計算規則為：先進行括弧匹配拆開，單個計算之後再進行拼接
// 例如：((1 + 2) + 3 / (4 % 6)) * 6的計算順序是：
// -> ((1 + 2) + 3 / (4 % 6)) * 6
// -> (1 + 2) + 3 / (4 % 6)
// -> 1 + 2
// -> 3 + 3 / (4 % 6)
// -> 4 % 6
// -> 3 + 3 / 4
// -> 3 / 4
// -> (3 + 0.75) * 6
// -> 3 + 0.75
// -> 3.75 * 6
// -> 22.5
if (exists(str, '(')) {
const bracketStr = getMatchStr(str);
const nextResult = myEval(bracketStr);
const replaceStr = str.replace(`(${bracketStr})`, nextResult)
// 如果子字元串中存在'3 + 3 / (4 % 6)' 這樣的式子，說明第一個括弧中的內容計算完成了
// 這樣就可以接著遞歸進行第二個括弧中的算式計算
if (exists(replaceStr, '(')) {
return myEval(replaceStr);
} else {
// 如果是類似於'1 + 2 / 3'的式子，則直接進行計算返回結果
return innerBracketCacl(replaceStr);
}
} else {
return innerBracketCacl(str);
}
}取一個叫做myEval的函數，主要進行流程的控制，如果遇到的是括弧中的內容，則先進行括弧中的運算，否則，直接進行常規表達式計算。
/**
* 獲取匹配的字元串
* @param string str
* @return string 返回的匹配結果
*/
function getMatchStr(str) {
// 匹配類似於這樣的式子:
// '((1 + 2) / 3) * 4' -> ((1 + 2) / 3)
// '1 * (2 + 3) / (5 - 6)' -> 2 + 3
const regexp = /\([^\)]+\)[^\(]+\)|\((.*?)\)/;
const regexp2 = /\((.*)\)/;
let matches = str.match(regexp);
let bracketStr = matches[1] || matches[0];
if (exists(bracketStr, '(') && !exists(bracketStr, ')')) {
// 類似於這樣的式子'((1 + 2) / (3 - 7)) * 4'
// 那麼匹配出來的就是'(1 + 2'
// 顯然不是我想要的結果，我只需要解掉第一層的括弧就可以按照之前的方式計算了
// 用第二個正則匹配的就是'(1 + 2) / (3 - 7)'
// 我只需要按照之前的方式先計算這個式子就好
bracketStr = str.match(regexp2)[1];
} else if(bracketStr.indexOf('(') === 0) {
bracketStr = bracketStr.slice(1, -1);
}
return bracketStr;
}獲取匹配字元子串，主要是進行規則匹配，分佈計算。
/**
* 計算表達式
* 例如有這樣的式子: '1 + 2 / 3'
* 那麼會先計算'2 / 3'
* @param string str
* @return string 結果
*/
function innerBracketCacl(str) {
const matches = str.match(/[\/\*%]/g);
let firstPriorityResult = str;
if (matches) {
firstPriorityResult = stepFirstPriority(str);
}
return stepSecondPriority(firstPriorityResult);
}簡單的運算式計算，即不包含括弧的計算，先計算*/%的運算符，然後計算+-
/**
* 第一優先順序的運算
* 這裡的第一優先順序為'%/*'
* @param string str
* @return number 返回計算結果
*/
function stepFirstPriority(str) {
const matches = str.match(/[\/\*%]/g);
if (!matches) {
return str;
} else {
const newStr = caclPart('/%*', str);
return stepFirstPriority(newStr);
}
}
/**
* 第二優先順序的運算
* 這裡的第一優先順序為'+-'
* @param string str
* @return number 返回計算結果
*/
function stepSecondPriority(str) {
if (!isNaN(Number(str))) {
return str;
} else {
const newStr = caclPart('+-', str);
return stepSecondPriority(newStr);
}
}這上面是運算優先順序的計算方式，先乘除後加減，計算之後進行字元串替換，然後遞歸計算。
/**
* 計算類似於 '1 + 2', '3 / 4'的子算式
* @param string shouldOprs 包含的運算符，例如('/%*', '+-')
* @param string str 計算的子字元串，例如( 1 + 2 / 4 )
* @return string 返回計算後的子字元串，例如( 1 + 0.5 )
*/
function caclPart(shouldOprs, str) {
let newStr = '';
for (let i = 0; i < str.length; i++) {
let s = str[i];
if (exists(shouldOprs, s)) {
// 截取字元串的左側
// 例如字元串為'3 + 3 / 4', 那麼左側就是'3 + 3 /'，右側則是 / 4
// 目的是為了接下來的匹配左右兩側的數字
let leftStr = str.slice(0, i + 1);
let rightStr = str.slice(i);
// 左側的正則為/((\d\.)*\d+)\s*\+$/，其中最後一個'+'是動態匹配的字元串
// 右側的正則為/\+\s*((\d\.)*\d+)/，其中最後一個'+'是動態匹配的字元串
const leftNum = new RegExp('\((\\d\\.)*\\d+\)\\s\*\\' + s + '$', 'g').exec(leftStr)[1];
const rightNum = new RegExp('\\' + s + '\\s\*\((\\d\\.)*\\d+\)').exec(rightStr)[1];
// 計算出值後進行字元串替換
// 比如'3 + 3 / 4' -> '3 + 0.75'
// 單個計算完成之後跳出迴圈，之後繼續進行後面的操作
const result = cacl(leftNum, rightNum, s);
newStr = str.replace(new RegExp('(\\d\\.)*\\d+\\s\*\\' + s + '\\s\*(\\d\\.)*\\d+'), result);
break;
}
}
return newStr;
}至此，這就是我的全部思路以及實現方式。
其中有一些正則表達式寫不出，想來正則學得還是不夠，只能用一些取巧的辦法。測試用例也設計得不是太全面，可能會存在一些問題，但是就目前的測試來說，簡單的算是是能通過的。
性能問題上：因為頻繁的調用遞歸，致使複雜度大大增大，時間運行得也比原生eval時間要長。以下是我的測試例子：
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';
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')
關於js實現eval的方式：
//計算表達式的值
function evil(fn) {
var Fn = Function; //一個變數指向Function，防止有些前端編譯工具報錯
return new Fn('return ' + fn)();
}
// jquery2.0.3實現方式：
// Evaluates a script in a global context
globalEval: function( code ) {
var script,
indirect = eval;
code = jQuery.trim( code );
if ( code ) {
// If the code includes a valid, prologue position
// strict mode pragma, execute code by injecting a
// script tag into the document.
if ( code.indexOf("use strict") === 1 ) {
script = document.createElement("script");
script.text = code;
document.head.appendChild( script ).parentNode.removeChild( script );
} else {
// Otherwise, avoid the DOM node creation, insertion
// and removal by using an indirect global eval
indirect( code );
}
}
}參考資料：
