前言

上篇我们介绍了栈算法的基本原理和应用，本题将结合进阶题目进行讲解。进一步深化对于栈算法的理解运用。

第一章：比较含退格的字符串

1.1 题目链接：https://leetcode.cn/problems/backspace-string-compare/description/

1.2 题目分析：

• 现给定字符串s和t，比较其经过内部的回退字符编辑后，两字符串是否相等
• 当文本为空时，遇到回退字符仍保持为空

1.3 思路讲解：

由于退格的时候需要知道「前⾯元素」的信息，⽽且退格也符合「后进先出」的特性。因此我们可以使⽤「栈」结构来模拟退格的过程。
• 当遇到⾮ # 字符的时候，直接进栈；
• 当遇到 # 的时候，栈顶元素出栈。

为了⽅便统计结果，我们使⽤「数组」来模拟实现栈结构

1.4 代码实现：

class Solution {
public:
string change(string& r)
{int n=r.size();string ret="";for(auto ch:r){if(ch=='#'){if(ret.size()){ret.pop_back();}}//回退操作，如果ret元素为空则无需删除else{ret+=ch;}}return ret;
}bool backspaceCompare(string s, string t) {s=change(s);t=change(t);return s==t;}
};

第二章：基本计算器||

2.1 题目链接：https://leetcode.cn/problems/basic-calculator-ii/description/

2.2 题目分析：

• 给出一只包含数字和+,-,*,/的字符串
• 其中不包含括号
• 所有数字均大于等于0
• 要求设计一个计算器，计算该字符串最终的结果

2.3 思路讲解：

由于表达式⾥⾯没有括号，因此我们只⽤处理「加减乘除」混合运算即可。根据四则运算的顺序，我们可以先计算乘除法，然后再计算加减法。由此，我们可以得出下⾯的结论：

• 当⼀个数前⾯是 ‘+’ 号的时候，这⼀个数是否会被⽴即计算是「不确定」的，因此我们可以先压⼊栈中；
• 当⼀个数前⾯是 ‘-’ 号的时候，这⼀个数是否被⽴即计算也是「不确定」的，但是这个数已经和前⾯ 的 - 号绑定了，因此我们可以将这个数的相反数压⼊栈中；
• 当⼀个数前⾯是 ‘*’ 号的时候，这⼀个数可以⽴即与前⾯的⼀个数相乘，此时我们让将栈顶的元素乘上这个数；
• 当⼀个数前⾯是 ‘/’ 号的时候，这⼀个数也是可以⽴即被计算的，因此我们让栈顶元素除以这个数。

当遍历完全部的表达式的时候，栈中剩余的「元素之和」就是最终结果。

2.4 代码实现：

class Solution {
public:int calculate(string s) {vector<int> nums;//存储数字char op='+';int n=s.size();int i=0;while(i<n){//如果为数字if('0'<=s[i]&&s[i]<='9'){//多位数的情况int temp=0;while(i<n&&'0'<=s[i]&&s[i]<='9'){temp=temp*10+(s[i++]-'0');}if(op=='+'){nums.push_back(temp);}else if(op=='-'){nums.push_back(-temp);}else if(op=='*'){nums.back()*=temp;}else {nums.back()/=temp;}}//如果为空格else if(s[i]==' '){i++;}//如果为其他符合else {op=s[i];i++;}}int ret=0;for(auto e:nums){ret+=e;}return ret;}
};

第三章：字符串解码

3.1 题目链接：https://leetcode.cn/problems/decode-string/description/

3.2 题目分析：

• 给出字符串，其中只包含小写字母，数字，[和]
• []内表示需要重复的内容，数字表示需要重复的次数
• 注意嵌套情况

3.3 思路讲解：

对于 3[ab2[cd]] ，我们需要先解码内部的，再解码外部（为了⽅便区分，使⽤了空格）：

• 3[ab2[cd]] -> 3[abcd cd] -> abcdcd abcdcd abcdcd
• 在解码 cd 的时候，我们需要保存 3 ab 2 这些元素的信息，并且这些信息使⽤的顺序是从后往前，正好符合栈的结构.

因此我们可以定义两个栈结构，⼀个⽤来保存解码前的重复次数 k （左括号前的数字），⼀个⽤来保存解码之前字符串的信息（左括号前的字符串信息）。

3.4 代码实现：

class Solution {
public:string decodeString(string s) {stack<int> nums;  // 栈用于存储重复次数的数字stack<string> st; // 栈用于存储当前的字符串st.push("");      // 初始化栈顶为一个空字符串，用于存储最外层的解码结果int n = s.size(), i = 0;while (i < n) {// 如果当前字符是数字，则处理数字（可能是多位数）if ('0' <= s[i] && s[i] <= '9') {int temp = 0;while (i < n && '0' <= s[i] && s[i] <= '9') {temp = temp * 10 + (s[i] - '0'); // 将字符转为整数i++;}nums.push(temp); // 将处理好的数字压入数字栈}// 如果当前字符是左括号 '['else if (s[i] == '[') {i++; // 跳过左括号string temp;while (i < n && 'a' <= s[i] && s[i] <= 'z') {temp += s[i++]; // 记录括号中的字符串}st.push(temp); // 将当前字符串压入字符串栈}// 如果当前字符是右括号 ']'else if (s[i] == ']') {i++; // 跳过右括号int k = nums.top(); // 获取数字栈顶元素（重复次数）nums.pop();         // 弹出数字栈顶string temp = st.top(); // 获取当前字符串栈顶的字符串st.pop();               // 弹出字符串栈顶// 将字符串重复 k 次并追加到上一级的字符串while (k--) {st.top() += temp; // 将重复的结果追加到栈顶的字符串}}// 如果当前字符是字母else {string temp;while (i < n && 'a' <= s[i] && s[i] <= 'z') {temp += s[i++]; // 累加连续的字母}st.top() += temp; // 追加到当前的栈顶字符串}}return st.top(); // 返回最外层的解码结果}
};

为什么在 st 中先推入一个空字符串 ""？
处理最外层字符串的特殊情况：

• 如果字符串 s 中没有嵌套的括号（如 “abc3[de]”），整个字符串的解析结果直接存在 st 栈顶。
• 初始的空字符串 “” 用于存储这些最外层的字符串部分。
  例如，处理 “3[a]” 时：初始栈中为 [“”]。最终在 nums 和 st 处理完毕后，栈顶 “” 会追加最终结果 “aaa”。
• 避免逻辑复杂性：
  如果不提前推入空字符串，则需要在代码中专门处理第一次拼接或栈为空的特殊情况，增加了代码复杂性。
  通过初始化空字符串，简化了逻辑，可以将所有拼接操作统一处理为 st.top() += …。
• 递归式嵌套的正确性：
  在解码过程中，可能会遇到嵌套字符串（如 “2[3[a]b]”），栈用于分层管理。
  初始的 “” 保证了最外层的结果存储有地方承接，而不需要额外的变量来保存结果。

示例解释 以输入字符串 “3[a2[bc]]” 为例：

初始化：st = [“”]，nums = []。
解析 3：将 3 压入 nums，nums = [3]。
遇到 [：推入空字符串到 st，st = [“”, “”]。 解析 a：将 a 追加到 st.top()，st = [“”, “a”]。
解析 2：将 2 压入 nums，nums = [3, 2]。
遇到 [：推入空字符串到 st，st = [“”, “a”, “”]。
解析 bc：将 bc 追加到st.top()，st = [“”, “a”, “bc”]。
遇到 ]：弹出 2 和 bc，重复 bc 两次，st = [“”, “a”,“bcbc”]。
遇到 ]：弹出 3 和 a + bcbc，重复结果三次，st = [“”]。 返回最终结果 st.top() 为"abcbcabcbcabcbc"。

第四章：验证栈序列

4.1 题目链接：https://leetcode.cn/problems/validate-stack-sequences/description/

4.2 题目分析：

• 题目给出push和pop两个数组，判断是否为一对匹配的出入栈序列
• 栈内每一个数字的值都不相同

4.3 思路讲解：

⽤栈来模拟进出栈的流程。

• ⼀直让元素进栈，进栈的同时判断是否需要出栈。
• 当所有元素模拟完毕之后，如果栈中还有元素，那么就是⼀个⾮法的序列。
• 否则，就是⼀个合法的序列

4.4 代码实现：

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int m=pushed.size();int n=popped.size();int i=0;if(m!=n){return false;}//如果元素个数不相等一定不匹配for(auto e:pushed){st.push(e);while(!st.empty()&&st.top()==popped[i]){st.pop();i++;}}return st.empty();}
};

结语

在信息的海洋中，栈是一叶扁舟，承载着计算的重量，也承载着思想的深邃。它的操作简单而纯粹，却蕴含着无限的可能性。或许，这正是栈的魅力所在——在有限中追寻无限，在简单中窥见复杂。在这座无形的山峰上，我们每一步都通向更高的远方。

本篇关于栈算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！