栈的介绍和使用（算法）
栈最大的特点是先进先出。利用这个特点应用于我们的日常生活会有很大的便利。下面我们一起来看看吧。
1.
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;
else st.back()/=tmp;
}else{
op=s[i];
i++;
}
}
int sum=0;
for(auto e: st){
sum+=e;
}
return sum;
}
};
2.
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');
}
nums.push(tmp);
}else if(s[i]=='['){
i++;
string;
while(s[i]>='a'&&s[i]<='z'){
tmp+=s[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++];
}
st.top()+=tmp;
}
}
return st.top();
}
};
3.
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int n=popped.size();
stack<int> result;
int i=0;
for(auto e: pushed){
result.push(e);
while(result.size()&&result.top()==popped[i]){
result.pop();
i++;
}
}
return i==n;
}
};