【C++算法】栈

删除字符中的所有相邻重复项

• 题目链接

删除字符中的所有相邻重复项https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

• 算法原理

• 代码展示

class Solution 
{
public:string removeDuplicates(string s) {string ret;for(int i = 0; i < s.size(); i++){if(!ret.empty() && ret.back() == s[i]){ret.pop_back();}else{ret += s[i];}}return ret;}
};

比较含退格的字符串

• 题目链接

比较含退格的字符串https://leetcode.cn/problems/backspace-string-compare/description/

• 算法原理

解法：用栈思想模拟即可

• 代码展示

class Solution 
{
public:bool backspaceCompare(string s, string t) {return comString(s) == comString(t);}string comString(string s){string ret;for(auto ch : s){if(ch != '#') {ret += ch;} else{if(!ret.empty()){ret.pop_back();}}}return ret;}
};

基本计算器

• 题目链接

基本计算器https://leetcode.cn/problems/basic-calculator-ii/description/

• 算法原理

• 代码展示

class Solution 
{
public:int calculate(string s) {stack<int> st;char op = '+';int i = 0, n = s.size();while(i < n){if(s[i] == ' '){i++;}else if(i < n && s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(i < n && s[i] >= '0' && s[i] <= '9'){tmp *= 10;tmp += s[i++] - '0';}if(op == '+'){// 直接入栈st.push(tmp);}else if(op == '-'){// -tmp入栈st.push(-tmp);}else if(op == '*'){// tmp乘栈顶元素，并放在栈顶st.top() *= tmp;}else{// 栈顶元素除tmp，并放在栈顶st.top() /= tmp;}}else{op = s[i++];}}int ret = 0;while(st.size()){ret += st.top();st.pop();}return ret;}
};

字符串解码

• 题目链接

字符串解码https://leetcode.cn/problems/decode-string/description/

• 算法原理

• 代码展示

class Solution 
{
public:string decodeString(string s) {stack<string> str;stack<int> num;str.push("");int i = 0, n = s.size();while(i < n){if(i < n && s[i] >= '0' && s[i] <= '9'){int tmp = 0;while(i < n && s[i] >= '0' && s[i] <= '9'){tmp *= 10;tmp += s[i++] - '0';}num.push(tmp);}else if(i < n && s[i] == '['){i++;string tmp;while(i < n && s[i] >= 'a' && s[i] <= 'z'){tmp += s[i++];}str.push(tmp);}else if(i < n && s[i] == ']'){i++;int tmpNum = num.top();num.pop();string tmpString = str.top();while(--tmpNum){str.top() += tmpString;}tmpString = str.top();str.pop();str.top() += tmpString;}else{str.top() += s[i++];}}return str.top();}
};

验证栈序列

• 题目链接

验证栈序列https://leetcode.cn/problems/validate-stack-sequences/description/

• 算法原理

• 代码展示

class Solution 
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> ret;int i = 0, n = popped.size();for(auto x : pushed){ret.push(x);while(i < n && ret.size() && popped[i] == ret.top()){ret.pop();i++;}}return i == n;}
};