第一题：
用数组来模拟栈：
题解代码：
class Solution {
public:string removeDuplicates(string s) {// 用数组模拟栈string s1;for (int i = 0; i < s.size(); i++) {if(s1.size() == 0){s1+=s[i];}else if (s1.back() == s[i]) {s1.pop_back();} elses1 += s[i];}return s1;}
};第二题：
还是数组模拟栈
题解代码：
class Solution {
public:bool backspaceCompare(string s, string t) {//同样的用数组来模拟string s1,s2;for(const auto& e:s){//当不为空并且e == #时才尾删if(s1.size()&&e == '#'){s1.pop_back();}//不能将#也➕到串中else if(e != '#') s1+=e;}for(const auto& e:t){if(s2.size()&&e == '#'){s2.pop_back();}else if(e!='#')s2+=e;}return s1 == s2;// if(s1.size() == 0&&s2.size() == 0){// return true;// }// else if(s1.size()!= s2.size()){// return false;// }// else {// int i = 0;// while(i<s1.size()){// if(s1[i] == s2[i]) i++;// else return false;// }// }// return true;}
};第三题：
表达式求值
算法原理：
题解代码：
class Solution {
public:int calculate(string s) {//数组模拟vector<int> st;char op = '+';int i =0;int n = s.size();while(i<n){if(s[i] == ' '){i++;}//数字else if(s[i]>='0'&&s[i]<='9'){int tem = 0;while(i<n&&s[i]>='0'&&s[i]<='9'){tem = tem*10+(s[i++]-'0');}//此时的i指向的是非数字的元素if(op == '+') st.push_back(tem);if(op == '-') st.push_back(-tem);if(op == '*') st.back() *= tem;if(op == '/') st.back() /= tem;}else {op = s[i];i++; }}int ret = 0;for(auto& e:st){ret+=e;}return ret;}
};第四题：
题解思路：
题解代码：
这里我同样采用的vector来模拟栈
class Solution {
public:string decodeString(string s) {vector<int> num;vector<string> st;st.push_back("");int i = 0;int n = s.size();while (i < n) {if (s[i] >= '0' && s[i] <= '9') {int tem = 0;while (i < n && s[i] >= '0' && s[i] <= '9')tem = tem * 10 + (s[i++] - '0');num.push_back(tem);}// i走到这表明不是数字了；else if (s[i] == '[') {i++; // 注意要先加1string s1;while (i < n && s[i] >= 'a' && s[i] <= 'z') {s1 += s[i++];}// 将s尾插到最后；st.push_back(s1);}// 走到这表明不是[;// 若是]，就提出来进行解码else if (s[i] == ']') {// 将栈顶元素提出来；string tmp = st.back();st.pop_back();// 再提取栈顶的数字int nums = num.back();num.pop_back();// 重复；while (nums--) {st.back() += tmp;}i++; // 跳过这个右括号}// 这，纯字符else {string s1;while (i < n && s[i] >= 'a' && s[i] <= 'z') {s1 += s[i];i++;}st.back() += s1;}}return st.back();}
};第五题：
验证栈序列：
题解思路：
1.将入栈序列挨个入栈；
2、判断出栈序列是否与栈顶元素相同，相同就出栈；
3、最后返回栈是否为空；
题解代码：
这里我还是用的vector来模拟的栈：
class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {vector<int> vt;int i = 0;for (const auto& e : pushed) {vt.push_back(e);while (vt.size() && vt.back() == popped[i]) {vt.pop_back();i++;}}return vt.empty();}
};
