数据结构-栈

栈（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被读入并输出。

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png