训练记录
今天洛谷崩了，先不统计了
A题
栈的模板题，pop出栈并输出栈顶，top输出栈顶，记得输出前判断一下栈内非空
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
stack<int> q;
void solve(){
string s; cin>>s;
if(s == "push"){
int x; cin>>x;
q.push(x);
} else if(s == "pop"){
if(!q.size()) cout<<"error"<<endl;
else cout<<q.top()<<endl,q.pop();
} else if(s == "top"){
if(!q.size()) cout<<"error"<<endl;
else cout<<q.top()<<endl;
}
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
B题
同上一题，多了一个求栈内元素的个数，输出s.size()即可
#include <bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
using namespace std;
void solve(){
stack<int> s;
int n; cin>>n;
for(int i = 1;i<=n;i++){
string opt; cin>>opt;
if(opt == "push"){
int x; cin>>x;
s.push(x);
} else if(opt == "pop"){
if(!s.size()) cout<<"Empty"<<endl;
else s.pop();
} else if(opt == "query"){
if(!s.size()) cout<<"Anguei!"<<endl;
else cout<<s.top()<<endl;
} else if(opt == "size"){
cout<<s.size()<<endl;
}
}
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
C题
经典括号匹配问题，遇到左括号入栈，遇到右括号取栈顶判断是否可以配对，如果可以配对则出栈，不能配对则入栈，如果最后栈内还留有括号就是有括号无法匹配，如果栈为空则代表所有的括号都已经匹配
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
void solve(){
string s; cin>>s;
stack<char> st;
int n = s.size();
for(int i = 0;i<n;i++){
if(s[i] == '(') st.push(s[i]);
else if(s[i] == ')'){
if(st.size() && st.top() == '('){
st.pop();
} else {
st.push(s[i]);
}
}
}
if(st.size()) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
D题
括号匹配的变式题，我们可以把fc和tb看成两种不同的括号，用栈进行一次括号匹配，记录匹配的括号数，最后用字符串的长度减去匹配的括号数就是剩下字符串的最短长度
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
void solve(){
int n; cin>>n;
string s; cin>>s;
int ans = 0;
stack<char> st;
for(int i = 0;i<n;i++){
if(s[i] == 'c'){
if(st.size() && st.top() == 'f'){
ans+=2;
st.pop();
} else {
st.push(s[i]);
}
} else if(s[i] == 'b'){
if(st.size() && st.top() == 't'){
ans += 2;
st.pop();
} else {
st.push(s[i]);
}
} else {
st.push(s[i]);
}
}
cout<<n-ans<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
E题
后缀表达式经典题，遇到数字则数字入栈，字符串转int需要逐位处理，每次变量乘十加上当前位的数字，遇到符号则从栈内取出两个数字进行对应的运算再压栈，最后栈内剩下的那个元素就是后缀表达式的值。
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
void solve(){
string s; cin>>s;
int n = s.size();
stack<int> t;
int num = 0;
for(int i = 0;i<n;i++){
if(s[i] == '.'){
t.push(num);
num = 0;
} else if(isdigit(s[i])){
num = num*10 + (s[i] - '0');
} else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'){
int y = t.top(); t.pop();
int x = t.top(); t.pop();
if(s[i] == '+') t.push(x+y);
else if(s[i] == '-') t.push(x-y);
else if(s[i] == '*') t.push(x*y);
else if(s[i] == '/') t.push(x/y);
}
}
cout<<t.top()<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
F题
众所周知乘法的优先级高于加法，所以我们需要把连续的乘法全部求出来再进行加法，我们可以使用栈先进后出的特性求连续的乘积，遇到乘法取栈顶进行乘法操作，遇到加法直接入栈，最后再将栈内所有元素求和就是答案
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int mod = 10000;
void solve(){
stack<int> s;
int x; cin>>x;
s.push(x%mod);
char a; int b;
while(cin>>a>>b){
if(a == '*'){
int c = s.top(); s.pop();
s.push(b*c%mod);
} else s.push(b%mod);
}
int ans = 0;
while(s.size()) ans += s.top(),ans%=mod,s.pop();
cout<<ans<<endl;
}
signed main(){
// int T; cin>>T; while(T--)
solve();
return 0;
}
G题
判断入出栈序列是否合法，我们按照入栈顺序进行入栈，再开一个指针变量指向第一个出栈序列，用while语句如果匹配则进行出栈操作并指针移动到下一位，如果不匹配则按照入栈顺序继续入栈，如果是合法的入出栈序列，最后的栈必定为空，我们判断最后栈是否为非空输出 No 和 Yes，注意一下出栈前要判断栈是非空的
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
void solve(){
int n; cin>>n;
int a[n+1],b[n+1];
stack<int> s;
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++) cin>>b[i];
int pos = 1;
for(int i = 1;i<=n;i++){
s.push(a[i]);
while(s.top() == b[pos]){
s.pop();
pos++;
if(!s.size()) break;
}
}
if(s.size()) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}