专题十一——栈
目录
1删除字符串中的所有相邻重复项
2比较含退格的字符串
3基本计算器Ⅱ
4字符串解码
5验证栈序列
6基本计算器
1删除字符串中的所有相邻重复项
oj链接：删除字符串中的所有相邻重复项
// stack
class Solution
{
public:
string removeDuplicates(string s)
{
stack<int> st;
for (auto &ch : s)
{
if (!st.empty() && ch == st.top())
st.pop();
else
st.push(ch);
}
string ret;
while (!st.empty())
{
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
// string
class Solution
{
public:
string removeDuplicates(string s)
{
string ret;
for (auto &ch : s)
{
if (ret.size() != 0 && ret.back() == ch)
ret.pop_back();
else
ret.push_back(ch);
}
return ret;
}
};2比较含退格的字符串
oj链接：比较含退格的字符串
class Solution
{
public:
bool backspaceCompare(string s, string t)
{
return ChangeStr(s) == ChangeStr(t);
}
string ChangeStr(string &s)
{
string ret;
for (auto &ch : s)
{
if (ch != '#')
ret += ch;
else if (ret.size())
ret.pop_back();
}
return ret;
}
};
//解法2：双栈->下题的思路
class Solution
{
public:
unordered_map<char, int> prior = {
{'+', 0},
{'-', 0},
{'*', 1},
{'/', 1}};
int calculate(string s)
{
stack<int> val;
stack<char> ops;
val.push(0);
int n = s.size(), i = 0;
while (i < n)
{
if (s[i] == ' ')
i++;
else 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');
val.push(tmp);
}
else
{
char op = s[i];
while (!ops.empty() && prior[op] <= prior[ops.top()])
cal(val, ops);
ops.push(op);
i++;
}
}
while (!ops.empty())
cal(val, ops);
return val.top();
}
void cal(stack<int> &val, stack<char> &ops)
{
int a = val.top();
val.pop();
int b = val.top();
val.pop();
char op = ops.top();
ops.pop();
if (op == '+')
val.push(b + a);
else if (op == '-')
val.push(b - a);
else if (op == '*')
val.push(b * a);
else
val.push(b / a);
}
};3基本计算器Ⅱ
oj链接：基本计算器 II
但此种解法不通用，如果有括号的加入就失效了！
class Solution {
public:
int calculate(string s) {
stack<int> st;
char oper='+';//初始化
int n=s.size(),i=0;
while(i<n)
{
if(s[i]==' ') i++;
else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
{
oper=s[i];
i++;
}
else
{
int tmp=0;
while(i<s.size()&&s[i]>='0'&&s[i]<='9')
{
tmp=tmp*10+(s[i]-'0');
i++;
}
if(oper=='+') st.push(tmp);
else if(oper=='-') st.push(-tmp);
else if(oper=='*'&&!st.empty()) st.top()*=tmp;
else st.top()/=tmp;
//此时i在下个位置
}
}
long long ret=0;
while(!st.empty())
{
ret+=st.top();
st.pop();
}
return ret;
}
};4字符串解码
oj链接：字符串解码
class Solution
{
public:
string decodeString(string s)
{
stack<int> val;
stack<string> op;
op.push(""); // 细节
int n = s.size(), i = 0;
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');
val.push(tmp);
}
else if (s[i] == '[')
{
i++; // 细节：i++不然后死循环
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
op.push(tmp);
}
else if (s[i] == ']')
{
Decode(val, op);
i++;
}
else
{
// 遇到单独字符(串)
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
op.top() += tmp;
}
}
return op.top();
}
void Decode(stack<int> &val, stack<string> &op)
{
int a = val.top();
val.pop();
string s = op.top();
op.pop();
string tmp;
for (int i = 0; i < a; i++)
tmp += s;
op.top() += tmp;
}
};5验证栈序列
oj链接：验证栈序列
class Solution
{
public:
bool validateStackSequences(vector<int> &pushed, vector<int> &popped)
{
stack<int> st;
int i = 0, n = popped.size();
for (auto &push_val : pushed)
{
st.push(push_val);
while (!st.empty() && st.top() == popped[i])
{
st.pop();
i++;
}
}
// if(st.empty()) return true;
// return false;
return i == n;
}
};
6基本计算器
oj链接：基本计算器
解法：双栈(通用解法)
使用两个栈 val 和 op 。val ： 存放所有的数字
op ：存放所有的数字以外的字符
2.从前往后遍历，对遍历到的字符进行分类讨论：a 空格 : 跳过
b ( : 直接加入 op 中
c ) : 使用现有的 val 和 op 进行计算(直到遇到左边最近的一个左括号为止)
d +/- : 需要将操作放入 op 中。在放入之前先把栈内可以算的都算掉，使用现有的 val 和 op 进行计算(直到栈内没有操作符或者遇到左括号后停止)e 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 val 中
细节：1） 由于第一个数可能是负数，为了减少边界判断：遍历之前先往 nums 添加一个 0
2） 为防止 () 内出现的首个字符为运算符，(遍历之前)将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (0+（这个处理逻辑可以放到遍历字符串里去做）
class Solution
{
public:
void ClearSpace(string &s)
{
int pos = s.find(" ");
while (pos != string::npos)
{
// s.replace(pos, 1, "");
s.erase(pos, 1);
pos = s.find(" ");
}
}
int calculate(string s)
{
stack<int> val;
stack<char> op;
// 细节1:防止第一个字符为'-',先往val里加0
val.push(0);
// 细节2：在遍历前清除空格
// 为什么不能再遍历中:判断是空格后i++呢？-> 要保证 (+ 或 (- 能判断得出来 -> s[i-1]==')'?
ClearSpace(s);
int n = s.size(), i = 0;
while (i < n)
{
if (s[i] == '(')
op.push(s[i++]);
else if (s[i] == ')')
{
while (op.top() != '(')
{
cal(val, op);
}
op.pop();
i++;
}
else if (s[i] == '+' || s[i] == '-')
{
// 防止出现 ‘(-’ 或 ‘(+’ 时计算出错 -> 参考用例："1-( -2)"
if (!op.empty() && (s[i - 1] == '('))
val.push(0);
while (!op.empty() && op.top() != '(')
cal(val, op);
op.push(s[i++]);
}
else
{
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9')
tmp = tmp * 10 + (s[i++] - '0');
val.push(tmp);
}
}
while (!op.empty())
cal(val, op);
return val.top();
}
// 两个数相+/-的逻辑
void cal(stack<int> &val, stack<char> &op)
{
int a = val.top();
val.pop();
int b = val.top();
val.pop();
char tmp = op.top();
op.pop();
if (tmp == '+')
val.push(a + b);
else
val.push(b - a);
}
};以上便是全部内容：有问题欢迎在评论区指正，感谢观看！