スタック操作の正当性
1440 ワード
7-1スタック操作の正当性(20点)
入力形式:
第1の行を入力すると、2つの正の整数NおよびMが与えられ、ここで、Nは測定対象シーケンスの個数であり、M(≦50)はスタックの最大容量である.その後、N行は、
出力フォーマット:
各シーケンスについて、
サンプルを入力:
出力サンプル:
S
およびX
でそれぞれインスタックおよびアウトスタック動作を表すと仮定する.S
およびX
のみからなるシーケンスに従って、1つの空のスタックを操作する場合、対応する操作はいずれも実行可能であり(削除時にスタックが空でない場合)、最後の状態もスタックが空である場合、シーケンスは正当なスタック操作シーケンスと呼ばれる.プログラムを作成し、S
とX
のシーケンスを入力して、そのシーケンスが合法かどうかを判断してください.入力形式:
第1の行を入力すると、2つの正の整数NおよびMが与えられ、ここで、Nは測定対象シーケンスの個数であり、M(≦50)はスタックの最大容量である.その後、N行は、
S
およびX
のみからなるシーケンスを与える.シーケンスは空ではなく、長さが100を超えないことを保証します.出力フォーマット:
各シーケンスについて、
YES
は、シーケンスが正当なスタック動作シーケンスである場合、またはそうでない場合、1行に出力される.サンプルを入力:
4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX
出力サンプル:
YES
NO
NO
NO
#include
#include
using namespace std;
int main(){
int m, n;
char s[101];
scanf("%d%d",&n,&m);
while(n--){
cin >> s;
int top = -1;
int an = 1;
for(int i = 0; s[i]!=NULL; i++){
if(s[i] == 'S')
{
if(top >= m-1)
an = 0;
++top;
}
else if(s[i] == 'X')
{
if(top == -1)
an = 0;
top--;
}
}
if(top != -1 ||an == 0)
printf("NO
");
else
printf("YES
");
}
return 0;
}