目录
61 力扣 1042 删除字符串中的所有相邻重复项
61.1 题目解析：
这个题目的本意其实跟那个消消乐游戏比较像。就是两个相同的直接消除。并且，从这道题开始一直到咱们今天的博客结束，使用的都是栈这个算法。
61.2 算法思路：
61.3 代码演示：
//删除字符串中的所有相邻重复项
string removeDuplicates(string s) {
string ret;//使用数组来模拟栈结构
for (auto& ch : s)
{
if (ret.size() && ret.back() == ch) ret.pop_back();//前提是这个ret里面得有元素，才可以进行ret.back()==ch的这判断
else ret += ch;
}
return ret;
}
int main()
{
string s("abbaca");
cout << removeDuplicates(s) << endl;
return 0;
}61.4 总结反思
理解这个题目的解法，咱们下一道题目还得用到这个解法。
62. 力扣844 比较含退格的字符串
62.1 题目解析：
这道题目也很好理解。就是遇到#的话，直接将栈顶元素弹出即可
62.2 算法思路：
这道题目的解法我可以说与上一道题几乎一样的，待会大家看代码就知道了。不过这道题目需要处理一下边界情况。并且这道题目的边界情况只有一种。待会代码分析
62.3 代码演示：
//比较含退格的字符串
bool backspaceCompare(string s, string t) {
string ret1;
for (auto& ch : s)
{
if (ret1.size() && ch == '#') ret1.pop_back();
else if (ret1.size() == 0 && ch == '#')
{
;
}
else ret1 += ch;
}
string ret2;
for (auto& x : t)
{
if (ret2.size() && x == '#') ret2.pop_back();
else if (ret2.size() == 0 && x == '#')
{
;
}
else ret2 += x;
}
return ret1 == ret2;
}
int main()
{
string s("y#fo##f");
string t("y#f#o##f");
cout << backspaceCompare(s, t) << endl;
return 0;
}那么这道题目需要处理的边界情况就是s:"y#fo##f".t:"y#f#o##f".
那么这种情况就需要加上栈为空，并且此时的字符是#，这种情况，否则就会导致返回的结果是错误的。
62.4 总结反思
这道题目很是巧妙地运用了上一题的解法，大家可以仔细的研读一下
63 力扣227 基本计算器
63.1 题目解析：
这道题目可以说也是有点难度的，边界情况很多。所以下面要仔细的听我讲解这道题目。
63.2 算法思路：
一般表达式求值类的题目，就是利用栈来模拟计算过程。并且，用数组模拟栈。
且，这道题目需要用到双栈，一个栈来维护nums，另外一个栈用来维护，符号op
咱们先来看一下模拟的过程：
OK，再来总结一下：
63.3 代码演示：
//基本计算器II
int calculate(string s) {
vector<int> ret;//用数组来模拟栈结构
int i = 0;
int n = s.size();
char op = '+';//初始化为加法符号
while (i < n)
{
if (s[i] == ' ') i++;//如果说这个位置为空格，那么直接跳过这个位置即可
else if (s[i] >= '0' && s[i] <= '9')//这个i此时的位置是1到9之间的数字
{
int tmp = 0;//tmp来存储数字
while (i < n && s[i] >= '0' && s[i] <= '9')//确保不越界，并且最基本的i这个位置还必须得是数字才可以
{
tmp = tmp * 10 + (s[i] - '0');//字符转为数字
i++;
}
if (op == '+') ret.push_back(tmp);
else if (op == '-') ret.push_back(-tmp);
else if (op == '*') ret.back() *= tmp;//这个vector数组的最后一个元素，用.back()来表示
else ret.back() /= tmp;
//最后不需要再i++了，因为上面已经加加过了，此时的这里就是乘除号的位置了（如果后面不是数字的话）
}
else {
op = s[i];//更新一下操作符，这个可不是再往ret这个栈里面加了，双栈
i++;
}
}
int outcome = 0;
for (auto& e : ret)
{
outcome += e;//此时，这个ret中已经全部是数字了，不是字符了，因为上面已经转换过了
}
return outcome;
}
int main()
{
string s(" 3+5 / 2 ");
cout << calculate(s) << endl;
return 0;
}63.4 总结反思
这道题目，就是基本计算器II还是比较简单的，那个计算器I才是真的难，那个还得掌握逆波兰表达式等等的知识。等有时间出个专题再讲讲吧
64 力扣394 字符串解码
64.1 题目解析：
大家看这个图是不是就清楚多了呢。并且，咱们需要涉及到细节的处理。有的是整体的处理或者是分类讨论。不过本题使用的是分类讨论这些边界情况
64.2 算法思路：
咱们先来模拟一下：
最后再总结一下这个讨论情况：
64.3 代码演示：
//字符串解码
string decodeString(string s) {
stack<int> nums;
stack<string> ret;
ret.push("");//先放入一个空的字符串，防止访问越界
int i = 0; int n = s.size();
while (i < n)//从头开始遍历
{
if (s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9')
{
tmp = tmp * 10 + s[i] - '0';
i++;
}
nums.push(tmp);//将tmp放到数字栈中
}
else if (s[i] == '[')
{
i++;//先跳过这个左括号，
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z')
{
tmp += s[i];
i++;
}
ret.push(tmp);//将这个tmp放到字符串栈中去
}
else if (s[i] == ']')
{
string tmp = ret.top();
ret.pop();//别忘了删除这个栈顶的元素
int kk = nums.top();
nums.pop();
while (kk--)
{
ret.top() += tmp;
}
i++;//跳过这个右括号
}
else
{
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z')//这个的i<n是必须得加的，因为若最后两个是de这个字符串的话，不加i<n，就越界访问了
{
tmp += s[i];
i++;
}
ret.top() += tmp;;//将这个tmp放到字符串栈的栈顶元素的后面去中去
}
}
return ret.top();//注意是返回栈顶元素。不可以返回ret。因为返回类型与返回值不匹配
}
int main()
{
string s("2[abc]3[cd]ef");
cout << decodeString(s) << endl;
return 0;
}64.4 总结反思
本题也是用到了相当多的知识，不过最重要的莫过于这个栈
65 力扣946 验证栈序列
65.1 题目解析：
这个问题，我依稀记得，我在牛客网上面也做过，但是当时我可没有这么清晰的思路。不过今天，我可以以一种很好的思维讲解出来。
65.2 算法思路：
65.3 代码演示：
//验证栈序列
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> ret;
int i = 0; int n = pushed.size();
int j = 0;
while (j < n)//这里你如果说要写while的话，不能使用i<n,因为你的i遍历的主要是popped，而这个是入栈的元素，应该再定义一个指针去遍历pushed这个数组。或者直接使用范围for也可以
{
ret.push(pushed[j]);
while (ret.size() && ret.top() == popped[i])//栈不能为空，并且，栈顶元素正好等于popped数组的i位置的元素
{
ret.pop();
i++;//出栈后，判断是否还继续相等，若还继续相等，则继续出栈
}
j++;
}
return ret.empty();//判断i是否越界了即可。或者是判断栈是否为空都可以
//return n==i;
}
int main()
{
vector<int> pushed = { 1,2,3,4,5 };
vector<int> popped = { 4,5,3,2,1 };
cout << validateStackSequences(pushed, popped) << endl;
return 0;
}65.4 总结反思
那么咱们今天的题目就讲解完了。关于栈这方面的，题目博主总结的并不是很完整。大家可以补充
本篇完...................