《算法题讲解指南：优选算法-栈》--65.删除字符中的所有相邻重复项，66.比较含退格的字符串，67.基本计算器II，68.字符串解码，69.验证栈序列
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
65.删除字符中的所有相邻重复项
题目链接：
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
题目描述：
题目示例：
解法(栈)：
算法思路：
本题极像我们玩过的「开心消消乐」游戏，仔细观察消除过程，可以发现本题与我们之前做过的「括号匹配」问题是类似的。当前元素是否被消除，需要知道上一个元素的信息，因此可以用「栈」来保存信息。
但是，如果使用stack来保存的话，最后还需要把结果从栈中取出来。不如直接用「数组模拟一个栈」结构:在数组的尾部「尾插尾删」，实现栈的「进栈」和「出栈」。那么最后数组存留的内容，就是最后的结果。
C++算法代码：
class Solution { public: string removeDuplicates(string s) { string ret; for(int i = 0; i < s.size(); i++) { // if(ret.size() == 0) // { // ret.push_back(s[i]); // } // else // { // if(ret.back() == s[i]) // { // ret.pop_back(); // } // else // { // ret.push_back(s[i]); // } // } if(ret.size() && ret.back() == s[i]) { ret.pop_back(); } else { ret.push_back(s[i]); } } return ret; } };算法总结及流程解析：
66.比较含退格的字符串
题目链接：
844. 比较含退格的字符串 - 力扣（LeetCode）
题目描述：
题目示例：
解法(用数组模拟栈)：
算法思路：
由于退格的时候需要知道「前面元素」的信息，而且退格也符合「后进先出」的特性。因此我们可以使用「栈」结构来模拟退格的过程。
当遇到非 # 字符的时候，直接进栈;
当遇到 # 的时候，栈顶元素出栈。
为了方便统计结果，我们使用「数组」来模拟实现栈结构。
C++算法代码：
class Solution { public: bool backspaceCompare(string s, string t) { vector<char> stack1; vector<char> stack2; for(int i = 0; i < s.size(); i++) { if(s[i] == '#' && stack1.size()) { stack1.pop_back(); } else if(s[i] != '#') { stack1.push_back(s[i]); } } for(int i = 0; i < t.size(); i++) { if(t[i] == '#' && stack2.size()) { stack2.pop_back(); } else if(t[i] != '#') { stack2.push_back(t[i]); } } return stack1 == stack2; } };算法总结及流程解析：
67.基本计算器II
题目链接：
227. 基本计算器 II - 力扣（LeetCode）
题目描述：
题目示例：
题目解析：
一定要认真看题目的提示，从提示中我们可以看到这道题：
只有「加减乘除」四个运算;
没有括号;
并且每一个数都是大于等于0的;
这样可以大大的「减少」我们需要处理的情况。
解法(栈)：
算法思路：
由于表达式里面没有括号，因此我们只用处理「加减乘除」混合运算即可。根据四则运算的顺序，我们可以先计算乘除法，然后再计算加减法。由此，我们可以得出下面的结论：
当一个数前面是 '+' 号的时候，这一个数是否会被立即计算是「不确定」的，因此我们可以先压入栈中;
当一个数前面是 '-' 号的时候，这一个数是否被立即计算也是「不确定」的，但是这个数已经
和前面的-号绑定了，因此我们可以将这个数的相反数压入栈中;
当一个数前面是 '*' 号的时候，这一个数可以立即与前面的一个数相乘，此时我们让将栈顶的元素乘上这个数;
当一个数前面是 '/' 号的时候，这一个数也是可以立即被计算的，因此我们让栈顶元素除以这个数。
当遍历完全部的表达式的时候，栈中剩余的「元素之和」就是最终结果。
C++算法代码：
class Solution { public: int calculate(string s) { vector<int> stack; int sum = 0; char op = '+'; int i = 0; while(i < s.size()) { if(s[i] >= '0' && s[i] <= '9') { //提取数字 int num = 0; while(i < s.size() && s[i] >= '0' && s[i] <= '9') { num = 10 * num + (s[i] - '0'); i++; } if(op == '+') { stack.push_back(num); } else if(op == '-') { stack.push_back(-num); } else if(op == '*') { stack.back() *= num; } else { stack.back() /= num; } } else if(s[i] == ' ') { i++; } else { op = s[i]; i++; } } for(int i = 0; i < stack.size(); i++) { sum += stack[i]; } return sum; } };算法总结及流程解析：
68.字符串解码
题目链接：
394. 字符串解码 - 力扣（LeetCode）
题目描述：
题目示例：
解法(两个栈)：
算法思路：
对于3[ab2[cd]]，我们需要先解码内部的，再解码外部(为了方便区分，使用了空格)：
3[ab2[cd]] -> 3[abcd cd] -> abcdcd abcdcd abcdcd
在解码 cd 的时候，我们需要保存 3ab2 这些元素的信息，并且这些信息使用的顺序是从后往
前，正好符合栈的结构，因此我们可以定义两个栈结构，一个用来保存解码前的重复次数k(左括号
前的数字)，一个用来保存解码之前字符串的信息(左括号后的字符串信息)。
C++算法代码：
class Solution { public: string decodeString(string s) { stack<int> nums; stack<string> str; int i = 0; string tmp; while(i < s.size()) { if(s[i] >= '0' && s[i] <= '9') { //提取数字 int num = 0; while(s[i] >= '0' && s[i] <= '9') { num = num * 10 + (s[i++] - '0'); } nums.push(num); } else if(s[i] == '[') { string tmp; //将 [ 后面的字符串提取出来 i++; while(s[i] >= 'a' && s[i] <= 'z') { tmp += s[i++]; } str.push(tmp); } else if(s[i] == ']') { int k = nums.top(); nums.pop(); tmp = str.top(); str.pop(); while(k--) { //栈为空时则不能获取栈顶元素需要特判 if(str.empty()) { str.push(tmp); } else { str.top() += tmp; } } i++; } else { string tmp; //如果遇到字母(单独)则直接提取出来放入栈顶元素后面即可 while(i < s.size() && s[i] >= 'a' && s[i] <= 'z') { tmp += s[i++]; } //栈为空时则不能获取栈顶元素需要特判 if(str.empty()) { str.push(tmp); } else { str.top() += tmp; } } } return str.top(); } };算法总结及流程解析：
69.验证栈序列
题目链接：
946. 验证栈序列 - 力扣（LeetCode）
题目描述：
题目示例：
解法(栈)：
算法思路：
用栈来模拟进出栈的流程。
一直让元素进栈，进栈的同时判断是否需要出栈。当所有元素模拟完毕之后，如果栈中还有元素，那么就是一个非法的序列。否则，就是一个合法的序列。
C++算法代码：
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { vector<int> stack; int i = 0; for(auto e : pushed) { stack.push_back(e); while(stack.size() && i < popped.size() && stack.back() == popped[i]) { stack.pop_back(); i++; } } return stack.size() == 0 ? true : false; } };结束语
到此，65.删除字符中的所有相邻重复项，66.比较含退格的字符串，67.基本计算器II，68.字符串解码，69.验证栈序列 这五道算法题就讲解完了。删除字符串相邻重复项：使用数组模拟栈结构进行消消乐式消除；比较含退格的字符串：用栈模拟退格操作后比较结果；基本计算器II：利用栈处理加减乘除运算顺序；字符串解码：采用双栈分别存储重复次数和字符串信息；验证栈序列：直接模拟栈的进出过程进行验证。希望大家能有所收获！