JavaScript数据结构中栈的应用之表达式求值问题详解

2024-02-25 21:48:03 62

本文实例讲述了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代码来实现下吧。









functionmidTOLast(a){
vara_len=a.length;
varmyArray=newArray();
b='';
for(vari=0;i

当然，以上程序还存在一点bug，但是思想应该就是这样子的。

下面，我们将讲解如何通过后缀表达式计算出表达式的结果。

那么，我们将中缀表达式转化为后缀表达式后，如何继续计算呢？还是以这个例子为例。

中缀表达式：a*b+c*d-e/f
后缀表达式：ab*cd*+ef/-

基本思路如下：

遍历后缀表达式，遇到非操作符的字符则直接进栈，遇到操作符则出栈两个元素，进行对应操作，然后将得到的结果再次入栈。依次直到遍历完成，此处栈中保存的值就是当前表达式的值。

实现的JavaScript代码如下：









functiongetValue(a){
vara_len=a.length,
myArray=newArray();
for(vari=0;i

好啦，栈的应用场景还有很多，比如进制的转换，行编辑程序，迷宫求解等。这里就不一一介绍了。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

JavaScript数据结构中栈的应用之表达式求值问题详解

热门推荐

随机推荐