栈的应用妙招：五道题秒解字符串难题

栈是我们之前学过的一种容器，针对特定的题型，这种容器能让我们更快地解决问题

1.删除字符串中的所有相邻重复项

题目来源：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

这道题有点像俄罗斯方块那个游戏，可以消除的版本，可以将字符串竖着看

就像这样，将相邻的元素都删掉

可以发现，题目完美符合栈这个数据结构，可以在这里使用栈，但没必要，用一个字符串来模拟栈就足够了

具体代码如下：

2.比较含退格的字符串

题目来源：844. 比较含退格的字符串 - 力扣（LeetCode）

题目的意思很简单，把'#'当做删除键，对字符串进行处理，最后比较处理完的字符串相不相等

可以发现，这道题和上一道题基本上是一模一样的，只不过删除的规则不一样

上道题删除的规则是有相邻的相同字母就删除

这道题是遇到‘#’就删除

具体代码如下：

3.基本计算器II

题目来源：227. 基本计算器 II - 力扣（LeetCode）

先来看题目是什么意思

题目给了我们一个字符串，这个字符串的内容表示一个计算式

需要我们将计算的结果返回

字符串中的字符大致可以分为三类

1：数字

2：运算符号

3：空格

因为空格很好处理，所以我们这里只需要考虑数字和运算符号怎么处理就好了

按照计算式来看，每一个数字都对应着一个计算符号

由于运算符号优先级的关系

这里‘*’ ，‘/’和'+','-'之间需要采取不同的处理方式

运算符号是‘*’,'/'时可以直接与前一个数字进行运算

运算符号是‘+’，‘-’时需要考虑后面的符号是否是‘*’，‘/’

所以我们需要一个整形数组来管理结果

数组中的每一个元素都是进行完乘除操作或者是不需要乘除操作的数字

最后将这些元素都加起来，就得到了最终的结果

具体代码如下：

还有一个需要注意的点，在统计每一个数字时，我们需要考虑这个数字是几位数

并且因为for循环本身会进行++，所以我们需要先检查下一个字符是否是数字再决定是否要进行++

这样的好处是不会跳过运算符号

4.字符串解码

题目来源：394. 字符串解码 - 力扣（LeetCode）

根据题目的意思，我们可以知道，字符的类型共有四种

1.数字

2.字母

3.'['

4.‘]’

根据这四种情况，我们需要采取不同的处理方法

以下面这个例子来分析

根据题目的意思我们能够知道

每一个括号前都有一个数字，代表括号里面的内容要重复出现几次

所以出现一个数字时，我们需要将这个数字记录下来，又因为数字后面可能还有其他括号内容对应的数字，并且内部的内容是先进行复制的，这种先后顺序完美符合栈这个数据结构

所以我们可以定义一个栈来管理数字

同样的，我们可以定义一个栈来管理字符串

当遇到数字时，我们将数字记录下来

当遇到‘[’时，我们让i++，根据‘[’后面是什么字符来考虑进行什么操作

如果后面是数字，就再次将数字记录下来

如果是字母那就将字母记录下来

当遇到']'时，我们将字符串的栈顶元素和数字的栈顶元素拿出来解析

加到字符的栈顶元素的后面

当遇到字母时

将字母加到栈顶元素的后面就好了

具体代码如下：

5.验证栈序列

题目来源：946. 验证栈序列 - 力扣（LeetCode）

这道题的意思很简单，让我们用那两个数组来模拟栈的进栈，出栈，看操作是否合法

我们直接创建一个栈来进行模拟就好了

具体代码如下：

以上就是本篇文章的全部内容了，如果对你有帮助，可以点个赞支持一下，感谢各位的观看

TA 关注的仓库 - 陌染青云 (mo-ran-qingyun) - Gitee.com

这是我个人的gitee 仓库,账号上文章的代码都会发到仓库里，有兴趣可以看一下