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

前端之家收集整理的这篇文章主要介绍了JavaScript数据结构中栈的应用之表达式求值问题详解前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题。分享给大家供大家参考,具体如下:

下面来谈一个比较经典的表达式求值问题,这个问题主要是设计到操作符的优先级。我们通常看到的表达式都是中缀表达式,存在很多优先级差别,而后缀表达式则没有这些优先级问题。下面先看看两种表达式的区别。

从中缀表达式转换到后缀表示式是很难实现的,我们这里可以通过栈的思想来实现。下面进行详细的介绍是什么样的思想:

在对一个中缀表示式进行转换的时候,遇到非操作符的字符则直接保存到后缀表示式的存储空间中。

遇到(,则压入栈,只有遇到对应的)才能被弹出。 遇到),就将(之前的操作符全部弹出,并保存到存储空间。 遇到*和/这样优先级高的,就判断栈中的操作符优先级是否低于当前操作符。 如果栈中的遇到的低,则将遇到的继续入栈;如果栈中的高,则将栈中的出栈,遇到的入栈。 最后,当字符串遍历完成,依次弹出操作符,保存到存储空间。

为了方便理解,将上面的例子再次讲解。a*b+c*d-e/f

首先是ab被保存到了存储空间,然后*入栈。现在栈中只有*。 遇到+之后,由于*比+优先级高,所以*出栈,+入栈,这样存储空间变为ab*,栈中变为+。 再时候遇到c,存储空间变为ab*c,栈中还是+。 接下来遇到*和d,由于+比*低,所以*继续入栈,栈中表为了+*,存储空间为ab*cd。 之后遇到-,由于*比-高,所以+*出栈,-入栈,存储空间变为ab*cd*+ ……后面不用解释了,悟性再低也应该会了。

下面我们用JavaScript代码来实现下吧。

<Meta charset="utf-8">

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

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《》、《》、《》、《》、《》及《错误与调试技巧总结》

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

原文链接:https://www.f2er.com/js/40055.html

猜你在找的JavaScript相关文章