stack

栈（stack）

栈在计算机科学中，是一种特殊的串列形式的数据结构，它的特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标 top）进行加入数据（push）和输出数据（pop）的运算。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

stack的golang实现

栈的应用

平衡符号

应用场景：

检测括号是否能够成对出现，如序列[()]是合法的，[(])是非法的。

实现思路：

创建一个空栈，读入所有字符，如果字符是一个开放符号，则入栈； 如果是一个封闭符号，则当栈空时报错，否则，将栈弹出； 如果弹出的符号不是对应的开放符号，则报错。 在字符末尾，如果栈非空，则报错。

前缀、中缀、后缀表达式

例如一个计算式：4.99 * 1.06 + 5.99 + 6.99 * 1.06

前缀表达式为：+ + * 4.99 1.06 5.99 * 6.99 1.06

中缀表达式为：4.99 * 1.06 + 5.99 + 6.99 * 1.06

后缀表达式为：4.99 1.06 * 5.99 + 6.99 1.06 * +

与二叉树的关系

前缀表达式对应于二叉树的前序遍历；中缀表达式对应于二叉树的中序遍历；后缀表达式对应于二叉树的后序遍历；

中缀表达式（Infix Notation）

中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表达式（前缀记法、波兰式 Polish notation, PN）

前缀表达式的运算符位于操作数之前。

中缀表达式转换为前缀表达式

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
   3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是右括号“)”，则直接压入S1；
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

后缀表达式（后缀记法、逆波兰式 Reverse Polish notation, RPN）

后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

对应以上例子。我们的自然计算顺序为首先计算4.99*1.06存为a1，然后a1+5.99存为a1，将6.99*1.06存为a2，a1+a2存为a1。

中缀表达式转换为后缀表达式

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
   3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是左括号“(”，则直接压入S1；
   2. 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最右边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。