本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题。分享给大家供大家参考,具体如下:
下面来谈一个比较经典的表达式求值问题,这个问题主要是设计到操作符的优先级。我们通常看到的表达式都是中缀表达式,存在很多优先级差别,而后缀表达式则没有这些优先级问题。下面先看看两种表达式的区别。
中缀表达式:a*b+c*d-e/f
后缀表达式:ab*cd*+ef/-
从中缀表达式转换到后缀表示式是很难实现的,我们这里可以通过栈的思想来实现。下面进行详细的介绍是什么样的思想:
在对一个中缀表示式进行转换的时候,遇到非操作符的字符则直接保存到后缀表示式的存储空间中。
遇到(,则压入栈,只有遇到对应的)才能被弹出。
遇到),就将(之前的操作符全部弹出,并保存到存储空间。
遇到*和/这样优先级高的,就判断栈中的操作符优先级是否低于当前操作符。
如果栈中的遇到的低,则将遇到的继续入栈;如果栈中的高,则将栈中的出栈,遇到的入栈。
最后,当字符串遍历完成,依次弹出操作符,保存到存储空间。
为了方便理解,将上面的例子再次讲解。a*b+c*d-e/f
首先是ab被保存到了存储空间,然后*入栈。现在栈中只有*。
遇到+之后,由于*比+优先级高,所以*出栈,+入栈,这样存储空间变为ab*,栈中变为+。
再时候遇到c,存储空间变为ab*c,栈中还是+。
接下来遇到*和d,由于+比*低,所以*继续入栈,栈中表为了+*,存储空间为ab*cd。
之后遇到-,由于*比-高,所以+*出栈,-入栈,存储空间变为ab*cd*+
……后面不用解释了,悟性再低也应该会了。
下面我们用JavaScript代码来实现下吧。
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <script type="text/javascript"> function midTOLast(a){ var a_len=a.length; var myArray=new Array(); b=''; for(var i=0;i<a_len;i++){ switch (a[i]){ case '(': { myArray.push(a[i]); break; } case ')'://如果是)则将栈中左括号之前的对象弹出 { if(myArray.length==0){ return false; } temp=myArray.pop();//非空,弹出对象 while(temp!='('){//只要不是左括号,则全部弹出 b+=temp;//并输出到后缀表达式中 if(myArray.length==0){//保证栈为空 break; } temp=myArray.pop(); } break; } case '*': case '/': { if(myArray.length==0){//如果栈为空则直接入栈 myArray.push(a[i]); }else{ temp=myArray[myArray.length-1]; if(temp=='+'||temp=='-'){//如果遇到高的,则遇到的继续入栈 myArray.push(a[i]);//遇到的入栈 } } break; } case '+': case '-': { if(myArray.length==0){//如果栈为空则直接入栈 myArray.push(a[i]); }else{ temp=myArray[myArray.length-1]; if(temp=='/'||temp=='*'){//如果遇到低的,则栈中的出栈,遇到的入栈 while(myArray.length!=0){ temp=myArray.pop();//栈中的出栈 b+=temp;//保存到存储空间 } myArray.push(a[i]);//遇到的入栈 } } break; } default: { b+=a[i]; break; } } } //最后将栈中剩下的操作符输出 while(myArray.length!=0){ temp=myArray.pop(); b+=temp; } return true; } var x="a*b+c*d-e/f"; midTOLast(x); alert(b);//ab*cd*+ef/- </script> </body> </html>
当然,以上程序还存在一点bug,但是思想应该就是这样子的。
下面,我们将讲解如何通过后缀表达式计算出表达式的结果。
那么,我们将中缀表达式转化为后缀表达式后,如何继续计算呢?还是以这个例子为例。
中缀表达式:a*b+c*d-e/f
后缀表达式:ab*cd*+ef/-
基本思路如下:
遍历后缀表达式,遇到非操作符的字符则直接进栈,遇到操作符则出栈两个元素,进行对应操作,然后将得到的结果再次入栈。依次直到遍历完成,此处栈中保存的值就是当前表达式的值。
实现的JavaScript代码如下:
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <script type="text/javascript"> function getValue(a){ var a_len=a.length, myArray=new Array(); for(var i=0;i<a_len;i++){ switch (a[i]) {//遇到数值则直接入栈 case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { myArray.push(a[i]); break; } case '+': {//遇到操作符则出栈两个元素进行对应操作 temp=myArray.pop()+myArray.pop(); myArray.push(temp);//再将结果入栈 temp=null; break; } case '-': { s=myArray.pop(); temp=myArray.pop()-s; myArray.push(temp); s=null;temp=null; break; } case '*': { temp=myArray.pop()*myArray.pop(); myArray.push(temp);//再将结果入栈 temp=null; break; } case '/': { s=myArray.pop(); temp=myArray.pop()/s; myArray.push(temp); s=null;temp=null; break; } } } return myArray.pop();//算出结果 } var a="12*34*+36/-";//1*2+3*4-3/6 var b=getValue(a);//13.5 alert(b); </script> </body> </html>
好啦,栈的应用场景还有很多,比如进制的转换,行编辑程序,迷宫求解等。这里就不一一介绍了。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- [雨果唱片]李冰《地方民歌·戏曲系列-爱的颂歌》WAV
- 《模拟人生》真人电影官宣!玛格特·罗比担任制片人
- 《星战绝地》系列玩家数超4000万!续作表现超预期
- EA称AI是其业务核心!能提高开发效率、节约成本
- 《十年经典成名好歌 高品质最佳音乐 2CD》[WAV/分轨][1GB]
- 《8个男人的故事 2CD》[WAV/分轨][1GB]
- 《粤语超白金 百听不厌的经典金曲 2CD》[WAV/分轨][1.3GB]
- 群星.1994-全世界精丫华星】【WAV+CUE】
- 杜德伟.1997-知.解2CD【滚石】【WAV+CUE】
- 群星.2022-一不小心喵上你原声大碟【TME影音】【FLAC分轨】
- 《战锤40K星际战士2》卡在正在加入服务器解决方法
- 《勇者斗恶龙怪物仙境3》玩法内容介绍
- 《幸福工厂》无限报错解决方法
- 交错战线原始交易所推荐角色一览
- 战锤40K星际战士2战术职业介绍|战术职业技能效果一览