算法12--栈

栈 原理经典例题[1047. 删除字符串中的所有相邻重复项]( leetcode /problems/remove-all-adjacent-duplicates-in-string/description/)[844. 比较含退格的字符串]( leetcode /problems/backspace-string-compare/description/)[227. 基本计算器 II]( leetcode /problems/basic-calculator-ii/description/)[394. 字符串解码]( leetcode /problems/decode-string/description/)[946. 验证栈序列]( leetcode /problems/validate-stack-sequences/description/)

原理

利用栈后进先出的特点解决问题，有时我们只是需要模拟栈的思路即可，不需要真正使用到栈。

经典例题 1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 s 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

class Solution { public: string removeDuplicates(string s) { string ans; int i=0; for(i=0;i<s.size();++i){ if(!ans.empty()&&ans.back()==s[i]){ ans.pop_back(); continue; } ans.push_back(s[i]); } return ans; } }; 844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。 注意：如果对空文本输入退格字符，文本继续为空。

class Solution { public: bool backspaceCompare(string s, string t) { stack<char> s1; stack<char> s2; int i=0; for(i=0;i<s.size();++i){ if('#'!=s[i]){ s1.push(s[i]); }else if(!s1.empty()){ s1.pop(); } } for(i=0;i<t.size();++i){ if('#'!=t[i]){ s2.push(t[i]); }else if(!s2.empty()){ s2.pop(); } } return s1==s2; } }; 227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

class Solution { public: int GetNumber(string& s, int& pos) { string tmp; while (pos < s.size()) { if (!isdigit(s[pos])) { break; } tmp.push_back(s[pos++]); } return stoi(tmp); } char GetOperator(string& s, int& pos) { return s[pos++]; } int Compare(char operator1, char operator2) { map<char, int> mp; mp['+'] = 0; mp['-'] = 1; mp['*'] = 2; mp['/'] = 3; vector<vector<int>> com = { {0, 0, -1, -1}, {0, 0, -1, -1}, {1, 1, 0, 0}, {1, 1, 0, 0}}; return com[mp[operator1]][mp[operator2]]; } int Calculate(int num1, int num2, char oper) { switch (oper) { case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; case '/': return num1 / num2; } return 0; } int calculate(string s) { //处理空格 string tmp; int i=0; for(;i<s.size();++i){ if(' '!=s[i]){ tmp.push_back(s[i]); } } s=tmp; cout<<s; int pos = 0; stack<int> numbers; stack<char> operators; while (pos < s.size()) { int num = 0; if (!isdigit(s[pos])) { num = numbers.top(); numbers.pop(); } else { num = GetNumber(s, pos); } if (pos == s.size()) { numbers.push(num); break; } char operator1 = GetOperator(s, pos); if (operators.empty()) { numbers.push(num); operators.push(operator1); continue; } char operator2 = operators.top(); int com = Compare(operator1, operator2); if (-1 == com || 0 == com) { int num1 = numbers.top(); int num2 = num; numbers.pop(); operators.pop(); operators.push(operator1); numbers.push(Calculate(num1, num2, operator2)); } else { int num1 = num; int num2 = GetNumber(s, pos); numbers.push(Calculate(num1, num2, operator1)); } } if (!operators.empty()) { int num2 = numbers.top(); numbers.pop(); int num1 = numbers.top(); numbers.pop(); char oper = operators.top(); operators.pop(); numbers.push(Calculate(num1, num2, oper)); } return numbers.top(); } };

这道题只有加减乘除，可以直接使用栈计算：

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

class Solution { public: string GetAnswer(string s,int& pos) { string ret; while(pos<s.size()) { int count=1; string tmp1; string tmp2; string num; while(pos<s.size()) { if(!isalpha(s[pos])) { break; } tmp1+=s[pos++]; } while(pos<s.size()) { if(!isdigit(s[pos])) { break; } num+=s[pos++]; } if(!num.empty()) { count=stoi(num); } if('['==s[pos]) { tmp2=GetAnswer(s,++pos); } ret+=tmp1; while(count--) { ret+=tmp2; } if(']'==s[pos]) { ++pos; break; } } return ret; } string decodeString(string s) { int pos=0; return GetAnswer(s,pos); } }; 946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { int pos1=0; int pos2=0; stack<int> s; while(pos1<pushed.size()){ s.push(pushed[pos1++]); while(!s.empty()&&s.top()==popped[pos2]){ s.pop(); ++pos2; } } if(!s.empty()){ return false; } return true; } };