博客

习题3.9 堆栈操作合法性



题目要求：


假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。


代码：

#include<stdio.h>
#define S 1
#define X -1
int main(){
	char str[100];
	int n,m;
	int i,count;
	scanf("%d %d",&n,&m);
	while(n--){
		scanf("%s",str);
		i=0;
		count=0;
		while(str[i]){
			if(str[i]=='S'){
				count++;
			}
			if(str[i]=='X'){
				count--;
			}
			if(count<0||count>m){
				break;
			}
			i++;
		}
		if(count==0){
			printf("YES\n");
		}
		else{
			printf("NO\n");
		}
	}
	return 0;
}

解题思路：


1、借鉴了大神得思路，比较有启发性的点是：他用了字符串来接收输入串，解决了换行输入的问题。输入一个串，之后直接判断他是否成立并且在第一层循环里输出。还有输出那里，只需要考虑什么时候是正确输出就行，其他都是错误的。