数据结构栈实战(数据结构实验栈的实现及应用)
数据结构栈实战
栈很少用于需要长期保留数据的场景,却常用于各种处理临时数据的算法。
下面我们来写一个初级的JavaScript分析器——一种用来检查JavaScript代码的语法是否正确的工具。因为JavaScript的语法规则很多,所以它可以做得很复杂。简单起见,我们就只专注于检查括号的闭合情况吧,包括圆括号、方括号、花括号,这些地方搞错的话是很令人郁闷的。
在写之前,先分析一下括号的语法错误会有哪些情况。分类就是以下3种。
首先是有左括号没有右括号的情况。
(var x=2;复制代码
这种归为第1类。
接着是没有左括号但有右括号的情况。
var x=2;)复制代码
这种归为第2类。
还有第3类,右括号类型与其前面最近的左括号不匹配,例如:
(var x=[1, 2, 3)];复制代码
此例中,虽然圆括号和方括号都左右成对出现,但位置不对,右圆括号前面最近的竟是左方括号。
那么怎样才能实现一种能检查一行代码里括号写得对不对的算法呢?用栈就好办了。
先准备一个空栈,然后从左至右读取代码的每一个字符,并执行以下规则。
(1)如果读到的字符不是任一种括号(圆括号、方括号、花括号),就忽略它,继续下一个。
(2)如果读到左括号,就将其压入栈中,意味着后面需要有对应的右括号来做闭合。
(3)如果读到右括号,就查看栈顶的元素,并做如下分析。
如果栈里没有任何元素,也就是遇到了右括号但没有左括号,即第2类语法错误。
如果栈里有数据,但与刚才读到的右括号类型不匹配,那就是第3类语法错误。
如果栈顶元素是匹配的左括号,则表示它已经闭合。那么就可以将其弹出,因为已经不需要再记住它了。
(4)如果一行代码读完,栈里还留有数据,那就表示存在左括号,没有右括号与之匹配,即第1类语法错误。
让我们用以下代码作为例子来演示一遍。
备好一个空栈之后,就可以开始从左至右读取代码的每个字符了。
第1步:首先是第一个字符,它是一个左圆括号。
第2步:因为它是一个左括号,所以将其压入栈中。
接下来的var x =,没有一个是括号,因此会被忽略。
第3步:遇到一个左花括号。
第4步:将其压入栈中。
然后忽略y:。
第5步:遇到一个左方括号。
第6步:同样把它压入栈中。
然后忽略1, 2, 3。
第7步:这时我们第一次看到了右括号,是一个右方括号。
第8步:于是检查栈顶的元素,发现那是一个左方括号。因为刚才读到的右方括号能与其配对,所以将左方括号弹出。
第9步:继续,下一个读到的是右花括号。
第10步:检查栈里的最后一个元素,刚好是可以配对的左花括号。于是将其弹出。
第11步:读到一个右圆括号。
第12步:检查栈里的最后一个元素,刚好是可以配对的左圆括号。于是将其弹出,剩下一个空栈。
至此,代码读完了,栈也空着,所以我们的分析器可以定论,这段代码在括号方面没有语法错误。
作者:有出路
链接:https://juejin.cn/post/7068256330934386719