目录
1.删除字符串中的所有相邻重复项
2.比较含退格的字符串
3.基本计算器2
4.字符串解码
5.验证栈序列
1.删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
我们只需要用一个string的字符串模拟一下这个栈就可以了
如果ret为空则入栈，否则进行判断，如果遍历到的那个字母与栈顶字母相同，就把栈顶那个字母出栈，否则就继续入栈
class Solution {
public:
string removeDuplicates(string s) {
int n = s.size();
string ret;
for(int i = 0; i < n; i++)
{
if(ret.empty())
{
ret.push_back(s[i]);
}
else
{
if(s[i] == ret.back())
{
ret.pop_back();
}
else
{
ret.push_back(s[i]);
}
}
}
return ret;
}
};2.比较含退格的字符串
844. 比较含退格的字符串 - 力扣（LeetCode）
class Solution {
public:
bool backspaceCompare(string s, string t) {
string ret1;
string ret2;
int m = s.size();
int n = t.size();
for(int i = 0; i < m; i++)
{
if(s[i] == '#' && !ret1.empty())
{
ret1.pop_back();
}
else if(s[i] != '#')
{
ret1.push_back(s[i]);
}
}
for(int i = 0; i < n; i++)
{
if(t[i] == '#' && !ret2.empty())
{
ret2.pop_back();
}
else if(t[i] != '#')
{
ret2.push_back(t[i]);
}
}
if(ret1 == ret2)return true;
else return false;
}
};3.基本计算器2
227. 基本计算器 II - 力扣（LeetCode）
这题我们用一个数组模拟栈，再创建一个字符变量 op来 保存 + - * /。因为这道题比较简单，没有引入括号，因此算数符的优先级是确定的。
当我们遇到 + - 的符号的时候，我们先要把接下来的数字入栈，因为如果后面有 * /运算符，这个数就要和后面的数进行运算。当遇到* / 符号的时候，直接把这个数和栈顶的数进行运算。
对于计算数，我们用一个while循环即可每次 把我们已经存下的数 * 10 再加上新的一位即可。
值得注意的是，我们需要更改一下计算顺序tmp = tmp * 10 + (s[i] - '0');先计算后面的，防止溢出，因为字符的阿斯克码值比较大
class Solution {
public:
int calculate(string s) {
vector<int> st;
char op = '+';
int n = s.size();
for(int i = 0; i < n; )
{
if((s[i] > '9' || s[i] < '0'))
{
if(s[i] != ' ')
{
op = s[i];
}
i++;
}
else
{
int tmp = 0;
while(i < n && s[i] >= '0' && s[i] <= '9')
{
tmp = tmp * 10 + (s[i] - '0');
i++;
}
if(op == '+')
{
st.push_back(tmp);
}
else if(op == '-')
{
st.push_back(-tmp);
}
else if(op == '*')
{
tmp = st.back() * tmp;
st.pop_back();
st.push_back(tmp);
}
else if(op == '/')
{
tmp = st.back() / tmp;
st.pop_back();
st.push_back(tmp);
}
}
}
int ret = 0;
for(int i = 0; i < st.size(); i++)
{
ret += st[i];
}
return ret;
}
};4.字符串解码
394. 字符串解码 - 力扣（LeetCode）
这种括号改变运算优先级的题目一般都是用栈解决
我们先准备两个栈，一个存数字，一个存字符串
这道题目需要我们分情况讨论：
1.如果遇到数字，提取出这个数字，放入数字栈
2.如果遇到‘[’：把后面的字符提取出来，放到字符串栈中
3.如果遇到‘]’：把数字栈栈顶的元素和字符串栈栈顶的元素分别出栈，并且拿出来进行运算，然后把运算出来的结果插入到新的字符串栈栈顶元素的后面（因为我们得出的运算结果可能是在另一对括号中的）
4.如果遇到单独的字符，一个一个放在字符串栈栈顶元素的后面，形成一个新的栈顶元素。
值得注意的点是，我们需要事先把字符串栈中加入一个空字符串，避免当栈里面只有一个元素的时候，把原栈顶元素加入新栈顶元素的时候栈为空。例如3[a]这种情况。
class Solution {
public:
string decodeString(string s) {
vector<int> ist;
vector<string> sst;
sst.push_back("");
int n = s.size();
for(int i = 0; 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++;
}
ist.push_back(tmp);
}
else if(s[i] == '[')
{
i++;
string tmpstring1;
while(i < n && s[i] >= 'a' && s[i] <= 'z')
{
tmpstring1 += s[i];
i++;
}
sst.push_back(tmpstring1);
}
else if(s[i] ==']')
{
i++;
string tmpstring2;
for(int k = 0; k < ist.back(); k++)
{
tmpstring2 += sst.back();
}
ist.pop_back();
sst.pop_back();
tmpstring2 = sst.back() + tmpstring2;
sst.pop_back();
sst.push_back(tmpstring2);
}
else
{
string tmpstring3;
while( i < n && s[i] >= 'a' && s[i] <= 'z')
{
tmpstring3 += s[i];
i++;
}
tmpstring3 = sst.back() + tmpstring3;
sst.pop_back();
sst.push_back(tmpstring3);
}
}
return sst.back();
}
};5.验证栈序列
946. 验证栈序列 - 力扣（LeetCode）
这题我们让push里面的元素一直进栈，同时pop中的元素也一直进行出栈判断。
等到循环结束判断其是否为空即可。
不过出栈之前要判断栈是否为空，如果为空就不要出栈。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int n = pushed.size();
stack<int> st;
int i = 0;
int j = 0;
while(i < n)
{
st.push(pushed[i]);
while(st.size() && popped[j] == st.top())
{
st.pop();
j++;
}
i++;
}
if(st.empty())return true;
else return false;
}
};
