数据结构——逆波兰式
很久没有关注算法和数据结构,大部分知识都已经忘记了;是时间好好回炉一下了,说实话干读数据机构这本书还是挺枯燥而且这本书原理性比较多,有一定的难度。这不刚看到逆波兰式废了好大劲才搞懂,老了。。。
逆波兰式
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)
算法实现
代码程序
//'1 + 2 * 3 + (4 * 5 + 6) * 7' function ReversePolish() { this.operatorStack = []; // this.operator = ['+', '-', '*', '/', '(', ')']; this.operator = { '+': 1, '-': 1, '*': 2, '/': 2, '(': 10, ')': 10 }; this.rp = []; } ReversePolish.prototype.convert = function(str) { debugger; // ('15 + 2 * 3 + (4 * 5 + 6) * 7').trim().replace(/\s+/g, '').split(/([\+|\-|\*|\/|\(|\)])/) // ["15", "+", "2", "*", "3", "+", "", "(", "4", "*", "5", "+", "6", ")", "", "*", "7"] str .trim() .replace(/\s+/g, '') .split(/([\+|\-|\*|\/|\(|\)])/) .filter(e => !!e) .forEach(e => { if (/[0-9]/g.test(e)) { // 数字直接放入逆波兰式数组 this.rp.push(e); } else { if (this.operatorStack.length === 0) {// 操作符栈为空直接压入栈 this.operatorStack.push(e); } else { if (e === '(') { // 左括号直接入栈 this.operatorStack.push(e); } else if (e === ')') { // 右括号弹出所有的操作符进入逆波兰数组,直至遇到 (, (不进入逆波兰数组 let op = this.operatorStack.pop(); while(op !== '(') { this.rp.push(op); op = this.operatorStack.pop(); } // this.operatorStack.pop(); } else { // 遇到其他操作符则弹出所有栈顶元素,直至遇到优先级更低的操作符,但是不处理( let op = this.operatorStack.pop(); while(op && this.operator[op] >= this.operator[e] && op !== '(') { this.rp.push(op); op = this.operatorStack.pop(); } if (op) { this.operatorStack.push(op); } this.operatorStack.push(e); } } } }); // 运行结束后将所有的操作符栈弹出 let op = this.operatorStack.pop(); while(op) { this.rp.push(op); op = this.operatorStack.pop(); } console.log(this.rp.join(' ')); }; //15 2 3 * + 4 5 * 6 + 7 * + ReversePolish.prototype.eval = function(){ let numberStack = []; this.rp.forEach(e => { if (/[0-9]/g.test(e)) { numberStack.push(Number(e)); } else if (this.operator[e]) { let n2 = numberStack.pop(); let n1 = numberStack.pop(); switch(e) { case '+': numberStack.push(n1 + n2); break; case '-': numberStack.push(n1 - n2); break; case '*': numberStack.push(n1 * n2); break; case '/': numberStack.push(n1 / n2); } } }); return numberStack.pop(); } let rp = new ReversePolish(); rp.convert('15 + 2 * 3 + (4 * 5 + 6) * 7'); rp.eval();
感觉逆波兰式不仅是一种方法,更是一种思想,逆波兰式这种计算方法没有必要知道任何运算符优先规则。就像我们实际业务中有很多逻辑判断、各种优先级的场景,是否也可以使用逆波兰式的思想来解决?