7-2 堆栈操作合法性 (15 分)

时间:2021-05-07作者:klpeng分类:IT综合浏览:478评论:0

目录

题目:

题解:


题目:

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

输入格式:

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

输出格式:

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

输入样例:

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例:

YES
NO
NO
NO

题解:

做这个题,我一开始是裂开了,没有看懂题哇。 注意看题,M(≤50)是堆栈的最大容量。输入的M是堆栈的最大容量!!!我一开始输入的是SX的最大容量,,然后12分的徘徊。然后就是只需要考虑S入栈X出栈,不需要考虑入栈和出栈的数值变化只需要关系top栈顶指针的数字变化就行啦。我这个解答中的栈的结构体也是多余的,另外入栈没有处理第一个元素的下标,所以top的初始化也可以是-1或者0.

首先是要读取输入的字符,然后扫描字符,假如是S的话,就入栈top++,出栈就top--。对于栈的不合法性考虑就是S入栈时栈已经满了,X出栈时栈已经空了,这个时候就输出NO,假如运行完了之后栈为空的话top==0就是为合法栈。 如果是top==0为初始值的话,top的大小就是栈的当前容量,压入栈的个数

  另外判断栈是否满,就要用到输入的M了!不是SX的长度最大为M,是模拟的栈的最大容量为M,如果本操作是S入栈时top已经等于了M,那么栈就是装不下了,还要进行入栈操作的话就不合法了。如果本操作是X出栈时,top可以代表栈里面有没有多少个元素,假如top为0,那么栈为空,就不可以再出栈元素了,因此这个操作也不合法。我们就用一个标识记录不合法的状态就好了

#include<iostream>
#include<stdlib.h>

using namespace std;
typedef struct LNode{
	char data[10];
	int top;
}LNode,*LinkNode;
int main()
{
	LinkNode L ;
	L=(LinkNode)malloc(sizeof(LNode));
	L->top=0;
	int n,m;
	cin>>n>>m;
	string s[n] ="";
	
	
	for(int i=0;i<n;i++){
	
		cin>>s[i];
	
	}
    for(int i=0;i<n;i++){
        int a=1;
        L->top=0;
        
    	for(int j=0;j<s[i].length();j++){
			
			if(s[i][j]=='S'){
				if(L->top>=m){
					//cout<<"NO"<<endl;
                    a=0;
					break;
				}
			    ++L->top;
			}
			if(s[i][j]=='X'){
				if(L->top==0){
					//cout<<"NO"<<endl;
                    a=0;
					break;
				}
				L->top--;
			}
			
		}
       if(a==1&&L->top==0)
        {
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
	   
    }
	
	
		

	
	
	
}

 

 7-2 堆栈操作合法性 (15 分)

 

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢