栈算法篇——LIFO后进先出，数据与思想的层叠乐章（下）
栈算法篇——LIFO后进先出，数据与思想的层叠乐章（下）
前言
上篇我们介绍了栈算法的基本原理和应用，本题将结合进阶题目进行讲解。进一步深化对于栈算法的理解运用。
第一章：比较含退格的字符串
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();
}
};结语
在信息的海洋中，栈是一叶扁舟，承载着计算的重量，也承载着思想的深邃。它的操作简单而纯粹，却蕴含着无限的可能性。或许，这正是栈的魅力所在——在有限中追寻无限，在简单中窥见复杂。在这座无形的山峰上，我们每一步都通向更高的远方。
本篇关于栈算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
腾讯云开发者
