中缀表达式转后缀表达式(用于求字符串表达式值)(js栈和队列的实现是通过数组的push和unshift方法插值,pop方法取值)
2023-09-27 14:20:23 时间
中缀表达式:就是我通常用的算术或逻辑公式;
后缀表达式:不包含括号,运算符放在两个运算对象后面,所有的计算按运算符出现的顺序,严格从左向右进行,不用考虑运算符优先级;
如,(2+1)*3 转换后,2 1 + 3 *
1、人工实现转换
如中缀表达式:a+b*c-(d+e)
(1)、按照运算符优先级对所有运算单位加括号,式子变成:((a+(b*c))-(d+e))
(2)、把运算符号移动到对应括号后面,变成:((a(bc)*)+(de)+)-
(3)、把括号去掉就变成后缀表达式了:abc*+de+-
2、中缀转后缀算法:
如中缀表达式:(1+2)*((8-2)/(7-4))
(1)、设立一个空栈,用于存放运算符
(2)、从左向右扫描,如果是操作数,直接输出;如果遇到左括号直接进栈,如果遇到右括号,则一直退栈,直到遇到左括号;如果是运算符,要和栈顶运算符比较(此处运算符比较就是+、-、*、/四则运算比较),比栈顶级别高,进栈,否则输出栈顶运算符(比较一次),然后运算符进栈
(3)、如果栈中剩有运算符,则依序出栈
例子:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
// var expression = '(1+2)*((8-2)/(7-4))'; var expression ='3+(2-5)*6/3' var obj = {'+': 0, '-': 0, '*': 1, '/': 1, '(': -1}; var arr = []; var str = ''; for (var i = 0; i < expression.length; i++) { var curChar = expression[i]; if (curChar == ' ') { continue; } var num = /^\d$/.test(curChar); if (num) { str = str + curChar + ' '; continue; } else if (curChar == '(') { arr.push(curChar); } else if (curChar == ')') { var len = arr.length; for (var j = 0; j < len; j++) { var pop = arr.pop(); if (pop != '(') { str = str + pop + ' '; } else { break; } } } else { if (arr.length > 0) { var top = arr[arr.length - 1]; if (obj[curChar] > obj[top]) { arr.push(curChar); } else { var pop = arr.pop(); arr.push(curChar); str = str + pop + ' '; } } else { arr.push(curChar); } } } for(var i=arr.length-1;i>=0;i--){ str = str + arr[i] + ' '; } console.log(str);
3、后缀表达式求职算法
(1)、设定一个空栈
(2)、从左向右扫描后缀表达式
(3)、如果是操作数入栈,如果是运算符,从栈中取出两个数,进行运算(如果使用js数组,pop方法弹栈,那么将先出的放在运算符右边,后出的在左边),再将结果入栈
直到后缀表达式扫描完毕,栈中仅有一个元素,即为运算结果
依然使用上面的表达式,console.log(calculatePostfix(str));
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
function calculatePostfix(postfixExp) { var arr = []; for (var i = 0; i < postfixExp.length; i++) { var curVal = postfixExp[i]; if(curVal==' '){ continue; } switch (curVal) { case '+': { var pop1 = arr.pop(); var pop2 = arr.pop(); var res=parseFloat(pop2)+parseFloat(pop1); arr.push(res); break; } case '-': { var pop1 = arr.pop(); var pop2 = arr.pop(); var res=parseFloat(pop2)-parseFloat(pop1); arr.push(res); break; } case '*': { var pop1 = arr.pop(); var pop2 = arr.pop(); var res=parseFloat(pop2)*parseFloat(pop1); arr.push(res); break; } case '/': { var pop1 = arr.pop(); var pop2 = arr.pop(); var res=parseFloat(pop2)/parseFloat(pop1); arr.push(res); break; } default : { arr.push(curVal); break; } } } return arr[0]; }
相关文章
- 用JS获取地址栏参数的方法
- js调用php和php调用js的方法举例
- js-第三个阶段的面试题
- vue.js:作用域插槽的使用案例
- 在JS中调用CS里的方法(PageMethods)
- [置顶] 在js中如何实现方法重载?以及函数的参数问题
- JS:指定FPS帧频,requestAnimationFrame播放动画
- 苹果ios使用js的日期时间处理时的问题
- js方法传入对象;js方法传入方法;js方法回调 callback
- js创建函数的方法
- JS判断Android、iOS或浏览器的多种方法(四种方法)【转】
- 【基于Html+CSS+JS的canvas赛车小游戏(效果+源码)】
- 一些 JS 代码片段(方法)
- 《JS原理、方法与实践》- canvas作图基础
- js刷新页面方法大全
- js数组格式转换成map数据格式的简单方法
- JS数组方法汇总
- js---换行自动填充分号
- js:可能是最全的js数组去重方法
- JS函数调用的四种方法
- 模拟jQuery中的ready方法及实现按需加载css,js实例代码
- JavaScript(JS) string.fixed( )
- JS面向对象,创建,继承
- js数组去重的三种常用方法总结
- 使用 sass + rem + flexible.js 实现大屏自适应
- 用JS获取地址栏参数的方法
- JS实现识别电脑浏览器和手机浏览器
- 常用JS方法整理