算法—栈系列

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

class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(int i = 0; i < s.size(); i++){char target = s[i];if(!st.empty() && target == st.top())st.pop();elsest.push(s[i]);}string ret;while(!st.empty()){ret.insert(ret.begin(), st.top());st.pop();}return ret;}
};

二：比较含退格的字符串

class Solution {
public:bool backspaceCompare(string s, string t) {stack<char> st_s;stack<char> st_t;for(auto& es : s){if(!st_s.empty() && es == '#')st_s.pop();else if(st_s.empty() && es == '#');elsest_s.push(es);}for(auto& et : t){if(!st_t.empty() && et == '#')st_t.pop();else if(st_t.empty() && et == '#');elsest_t.push(et);}return st_s == st_t;}
};

三：基本计算器II

class Solution {
public:int calculate(string s) {vector<int> st;     // 使用数组来模拟栈结构int i = 0, n = s.size();char op = '+';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');if(op == '+')st.push_back(tmp);else if(op == '-')st.push_back(-tmp);else if(op == '*')st.back() *= tmp;elsest.back() /= tmp;}else{op = s[i];i++;}}int ret = 0;for(auto& x : st)ret += x;return ret;}
};

四：字符串解码

class Solution {
public:string decodeString(string s) {stack<int> nums;stack<string> st;st.push("");int i = 0, n = s.size();while(i < n){if(s[i] >= '0' && s[i] <= '9'){// 先把这个数字提取出来int tmp = 0;while(s[i] >= '0' && s[i] <= '9'){tmp = tmp*10 + (s[i] - '0');i++;}nums.push(tmp);}else if(s[i] == '['){// 提取 [] 内的stringstring tmp;i++;while(s[i] >= 'a' && s[i] <= 'z'){tmp += s[i];i++;}st.push(tmp);}else if(s[i] == ']'){string tmp = st.top();st.pop();int k = nums.top();nums.pop();while(k--){st.top() += tmp;}i++;    // 跳过这个右括号}else{string tmp;while(i < n && s[i] >= 'a' && s[i] <= 'z'){tmp += s[i];i++;}st.top() += tmp;}}return st.top();}
};

五：验证栈序列

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