7-113 堆栈操作合法性 (20 分)
假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。
输入格式:
输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。
输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。
输入样例：
4 10 SSSXXSXXSX SSSXXSXXS SSSSSSSSSSXSSXXXXXXXXXXX SSSXXSXXX
结尾无空行
输出样例：
YES NO NO NO
结尾无空行
#include<iostream> using namespace std; int main(){ int n,m,i,t=1; cin>>n>>m; getchar(); while(n--){ int s=0,t=1; string a; cin>>a; for(i=0;i<a.size();i++){ if(a[i]=='S')s++; else s--; if(s<0||s>m){ printf("NO\n"); t=0; break; } } if(t==1){ if(s==0)printf("YES\n"); else printf("NO\n"); } } return 0; }
#include<iostream> using namespace std; int main() { int n,m,i; cin>>n>>m; string s; getchar(); while(n--) { int k=0; getline(cin,s); for(i=0;i<s.size();i++) { if(s[i]=='S'&&k<m) k++; else if(s[i]=='X'&&k>0) k--; else break; } if(i==s.size()&&k==0) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
#include<iostream> using namespace std; int main(){ int n,m,i; cin>>n>>m; while(n--){ int s=0,x=0; string a; cin>>a; for(i=0;i<a.size();i++){ if(a[i]=='S'){ s++; if(s>m){ cout<<"NO\n"; break; } }else{ x++; if(s){ x--; s--; } } } if(i==a.size()){ if(!s&&!x)cout<<"YES\n"; else cout<<"NO\n"; } } return 0; }
