昨天发了一个面试题:,受到了各位大大的指点,用一个比较简单的解法就能够计算出来,因此自己在下班后按照各位的指点又实现了一遍,这里贴出来供大家参考。
关于概念这里简单贴一下,想了解更多的可以自行Google
注: 与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。
一、 将中缀表达式转换成后缀表达式算法:
二、逆波兰表达式求值算法:
看上面的概念我都看晕了,接下来以一个例子讲解:
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倍左右的差距。
如对本文有疑问, 点击进行留言回复!!
【第138期】 游戏策划:应聘前HR要求把游戏玩到30级,怎么玩?
网友评论