数据结构-栈

2017-11-28  本文已影响0人  灰s

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶(top)。对栈的基本操作有Push(进栈)和Pop(出栈),前者相当于插入,后者则是删除最后插入的元素。

1. 平衡符号

编译器检查你的程序的语法错误,但是常常由于少一个符号(如遗漏一个花括号或是注释起始符)引起编译器列出上百行的诊断,而真正的错误并没有找出。
在这种情况下一个有用的程序就是检验是否每件事情都能成对出现。于是,每一个右花括号、右方括号及右圆括号必然对应其相应的左括号。序列[()]是合法的,但[(])是错误的。
这里可以使用一个简单的栈算法,叙述如下:
做一个空栈。读入字符直到文件尾。如果字符是一个开放符号,则将其推入栈中。如果字符是一个封闭符号,则当栈空时报错。否则,将栈元素弹出。如果弹出的符号不是对应的开放符号,则报错。在文件尾,如果栈非空则报错。

2. 函数调用

检测平衡符号的算法提供一种实现函数调用的方法。函数调用和函数返回基本上类似于开括号和闭括号。只不过多了函数执行位置和局部变量的储存问题。这里就不进行详细描述了。

3. 后缀记法(同时也叫做逆波兰记法)

正常表达式:4.99 * 1.06 + 5.99 + 6.99 * 1.06
后缀表达式:4.99 1.06 * 5.99 + 6.99 1.06 * +

例子:6 5 2 3 + 8 * + 3 + *
首先,将四个字符放入栈中,此时栈变成


image.png

下面读到一个" + "号,所以3和2从栈中弹出,并且它们的和5被压入栈中。


image.png

接着,8进栈。


image.png

现在见到一个" * "号,因此8和5弹出,并且5 * 8 = 40 进栈。


image.png

接着又见到一个" + "号,因此40和5被弹出,并且5 + 40 = 45进栈。


image.png

现在将3压入栈中。


image.png

然后" + "使得3和45从栈中弹出,并将45 + 3 = 48压入栈中。


image.png

最后,遇到一个" * "号,从栈中弹出48和6,将结果6 * 48 = 288压进栈中。


image.png

4. 中缀到后缀的转换

原则:

这时*号读入。操作符栈的栈顶元素比*的优先级低,故没有输出,*进栈。接着c被读入并输出。

image.png

后面的符号是一个+号。需要将*从栈弹出并放到输出中;弹出栈中剩下的+号,该符号不比刚刚遇到的+号优先级低而是有相同的优先级;然后,将刚刚遇到的+号压入栈中。

image.png

下一个被读到的符号是一个(,由于有最高的优先级,因此它被放进栈中。然后,d读入并输出。

image.png

继续进行,我们又读到一个*。除非正在处理闭括号,否则开括号不会从栈中弹出,因此没有输出。下一个是e,它被读入并输出。

image.png

再往后读到的符号是+。我们将*弹出并输出,然后将+压入栈中。这以后,我们读到f并输出。

image.png

现在,我们读到一个),因此将栈元素直到(弹出,我们将一个+号输出。

image.png

下面又读到一个*,该符号被压入栈中。然后,g被读入并输出。

image.png

现在输入为空,因此我们将栈中的符号全部弹出并输出,直到栈变成空栈


image.png
上一篇下一篇

猜你喜欢

热点阅读