数据结构-栈
栈(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. 中缀到后缀的转换
原则:
- 读到操作数的时候,立即把它放到输出中。操作符则是放入栈中。当遇到左圆括号时我们也要将其推入栈中。
- 如果遇到一个右括号,那么就将栈元素弹出,将弹出的符号放到输出中,反复执行,直到我们遇到一个(对应的)左括号,但是这个左括号只被弹出,并不输出。
- 如果我们见到任何其他的符号(
+
,*
,(
),那么我们从栈中弹出栈元素直到发现优先级更低的元素为止。 - 这里有一个例外:除非是在处理一个
)
的时候,否则我们绝不从栈中移走(
。对于这种操作,+
的优先级最低,而(
的优先级最高。 - 最后,如果我们读到了输入的末尾,我们将栈元素弹出直到该栈变成空栈,将符号写到输出中。
例子:
a + b * c + (d * e + f) * g
转为a b c * + d e * f + g * +
首先,a被读入,于是它流向输出。然后,+
被读入并被放入栈中。接着是b读入并流向输出。
image.png
这时*
号读入。操作符栈的栈顶元素比*
的优先级低,故没有输出,*
进栈。接着c
被读入并输出。
后面的符号是一个+
号。需要将*
从栈弹出并放到输出中;弹出栈中剩下的+
号,该符号不比刚刚遇到的+
号优先级低而是有相同的优先级;然后,将刚刚遇到的+
号压入栈中。
下一个被读到的符号是一个(
,由于有最高的优先级,因此它被放进栈中。然后,d读入并输出。
继续进行,我们又读到一个*
。除非正在处理闭括号,否则开括号不会从栈中弹出,因此没有输出。下一个是e,它被读入并输出。
再往后读到的符号是+
。我们将*
弹出并输出,然后将+
压入栈中。这以后,我们读到f并输出。
现在,我们读到一个)
,因此将栈元素直到(
弹出,我们将一个+
号输出。
下面又读到一个*
,该符号被压入栈中。然后,g被读入并输出。
现在输入为空,因此我们将栈中的符号全部弹出并输出,直到栈变成空栈
image.png