算法思想总结：栈

一、栈的经典应用：波兰表达式与逆波兰表达式

我们平时看到的 1+2*（3-4*5）+6/7 叫做中缀表达式，平时我们习惯用这个计算的原因是我们可以整体地去看到这个表达式并且清楚地知道各个运算符的优先级，但是计算机并不一定知道，因为他总是从前往后去遍历这个表达式。如上面这个例子，当按照计算机的逻辑去扫描了1+2的时候，并不敢直接去进行运算，因为可能后面存在一个优先级更高的操作符会优先进行计算。甚至有些时候还会出现括号这一种可以改变操作符优先级的符号！！所以这个时候，为了能够解决这个问题，就有了波兰表达式（前缀表达式）和逆波兰表达式（后缀表达式）。

前缀表达式：操作符+操作数+操作数

中缀表达式：操作数+操作符+操作数

后缀表达式：操作数+操作数+操作符

1.1 后缀表达式转中缀表达式

1.2 中缀表达式转后缀表达式

二、逆波兰表达式求值

. - 力扣（LeetCode）

三、基本计算器II

. - 力扣（LeetCode）

四、基本计算器I

. - 力扣（LeetCode）

五、有效的括号

. - 力扣（LeetCode）

六、删除字符串中所有相邻重复项

. - 力扣（LeetCode）

七、比较含退格的字符串

. - 力扣（LeetCode）

八、字符串解码

. - 力扣（LeetCode）

该题也是利用到基本计算器的解题思想

九、最小栈

. - 力扣（LeetCode）

策略3解题：

策略4解题：存键值对

十、验证栈序列

. - 力扣（LeetCode）

十一、1-n所有可能的出栈序列

如果入栈序列是1-n 将所有可能的出栈序列存储起来并返回。

我们来测试一下：

十二、利用栈实现基本计算器

目标：实现一个基本计算器，能够满足以下条件的运算：

1. 操作数：支持正数、负数、多位数计算
2. 操作符：支持（ ） + - * / % ^ 这些操作符

设计思路来源：中缀表达式和后缀表达式

具体的设计思路：

1. 所需要的数据结构——双栈+哈希表（设为全局变量）。其中一个存储整型的栈帮助我们存储操作数，另一个存储字符类型的栈帮助我们存储操作符，然后哈希表帮我们确立操作符的优先级。
2. + -的映射关系为1,* / %的映射关系为2，^的映射关系为3，按照上述方式存进哈希表来映射操作符优先级。然后对于左括号和右括号，我们进行特殊处理。
3. 因为我们输入的是字符串，所以有些时候需要用空格分割操作符和操作数，所以我们在计算前的第一步就是封装一个replace函数来帮助我们删除字符串中的所用空格。
4. 封装一个calc函数，帮助我们在满足计算条件的时候，取出数字栈的头两个元素分别作为右操作数和左操作数，再取出字符栈的栈顶操作符进行计算，用一个swtich语句根据不同的操作符类型执行不同的运算逻辑
5. 进行分类讨论：
6. 如果遇到(，无脑进栈
7. 如果遇到 ),不断进行calc直到遇到( ,并将(弹出
8. 如果遇到数字，因为要实现的是多位数的计算，所以可能后面的数字是挨着连在一起的，此时我们要想将该数提取出来，如果下一位也是数字，就将当前的数*10+下一个数字，当不再是数字的时候，将提取出来的数字入数字栈。
9. 如果遇到操作符，首先要处理一个特殊情况就是，如果当前操作符是- 并且前一个操作符时( 说明该-表示的是负数而不是减，所以为了运算的合理性，我们要在数字中压个0进去。 然后我们的新操作符要跟栈顶的操作符进行比较，如果运算的优先级较低或相等，就得将栈顶的操作符弹出来进行计算，即进行calc，不断重复该过程，直到新加入的操作符优先级比栈顶元素高，此时再将新操作符入栈
10. 细节处理：第一个数可能是负数，所以我们也要按照（4）中的逻辑一样，再数字栈上先压个0进去。
11. 最后当整个字符串遍历结束之后，我们将栈中剩余的操作数和操作符拿出来运算，最后留在数字栈顶的元素。就是我们的最终结果。
12. 该计算器的小缺陷：（1）不支持浮点数（2）整型除不尽会舍去。

十三、利用栈实现十进制转任意进制