精华内容
下载资源
问答
  • 堆栈操作合法性

    2021-01-26 21:58:25
    堆栈操作合法性 题目 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请...

    堆栈操作合法性

    题目

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

    输入格式:

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

    输出格式:

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

    输入样例:

    4 10
    SSSXXSXXSX
    SSSXXSXXS
    SSSSSSSSSSXSSXXXXXXXXXXX

    输出样例:

    YES
    NO
    NO

    解析

    这个题目比较简单,主要就是考察对于栈的理解以及认清题目要求。题目中不合法的情况有三种:

    1. 栈满,做入栈操作,栈溢出
    2. 栈为空,做出栈操作
    3. 操作结束后,栈中仍然有元素存在

    所以我们可以直接使用一个标志位和计数值来实现。标志位表示当前的操作是否合法,遇到非法操作就置否。计数值表示栈中元素的个数,进栈时计数值加一,出栈时计数值减一

    #include <cstdio>
    #include <cstring>
    #define MAX 100
    
    int main(){
        int n, m, oLength;
        scanf("%d%d\n", &n, &m);
    
        while(n--){
            int temp = 0; // 记录当前栈已经有多少个元素
            bool flag = true; // 针对错误情况进行判断
            char operate[MAX];
            scanf("%s", operate);
            oLength = strlen(operate);
            for(int index = 0; index < oLength; index++){
                if(operate[index] == 'S'){
                    temp++;
                }else if(operate[index] == 'X'){
                    temp--;
                }
                //错误条件,栈溢出或者栈空时出栈操作。
                if(temp > m || temp < 0){
                    flag = false;
                    break;
                }
            }
            // 判断是否栈内是否有元素,如果有的话就置否
            if(temp != 0){ flag = false; }
            printf(flag?"YES\n":"NO\n");
    
        }
        return 0;
    }
    
    
    展开全文
  • PAT 堆栈操作合法性

    千次阅读 2016-03-24 21:22:32
    PAT 堆栈操作合法性

    5-5 堆栈操作合法性   (20分)

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

    输入格式:

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

    输出格式:

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

    输入样例:

    4 10
    SSSXXSXXSX
    SSSXXSXXS
    SSSSSSSSSSXSSXXXXXXXXXXX
    SSSXXSXXX
    

    输出样例:

    YES
    NO
    NO
    NO


    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    #include <stack> 
    using namespace std;
    stack<char> ss;
    char a[1000];
    int len, sum;
    
    int main(){
    	int N, M, i, count;
    	scanf("%d%d", &N, &M);
    	getchar();
    	while(N--){
    		while(!ss.empty())
    			ss.pop();
    		count = 0;
    		sum = 0;
    		gets(a);
    		//printf("%s\n", a);	
    		len = strlen(a);
    		for(i = 0; i < len; ++i){
    			if(a[i] == 'S'){
    				ss.push(a[i]);
    				++sum;
    				if(sum > M){
    					printf("NO\n");
    					count = 1;
    					break;
    				}
    			}
    			else {
    				if(ss.empty()){
    					printf("NO\n");
    					count = 1;
    					break;
    				}
    				else {
    					ss.pop();
    					--sum;
    				}
    			}
    		}
    		if(count == 0 && ss.empty())
    			printf("YES\n");
    		else if(count == 0 && !ss.empty())
    			printf("NO\n");
    	}
    	return 0;
    } 


    展开全文
  • PTA 堆栈操作合法性

    千次阅读 2018-07-02 02:36:27
    堆栈操作合法性 题目要求: 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作...

    堆栈操作合法性

    题目要求:
    假设以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


    解题思路:
    这题虽然是对堆栈的操作,但其实我们并没必要真的去写一个栈出来,只要去模拟这个过程就可以了。这里我先用了一个一维的字符串数组来接受输入,用sum表示栈区里的元素个数,开始sum初始化为0。然后扫描这个字符串,若字符为’S’,则代表入栈,这时只要sum ++就可以了,同理,字符为’X’时,sum –。在任何一个只要sum < 0或者sum > m,则用flag = 0表示错误,并跳出循环。最后整个字符串扫描完毕后,判断sum是否等于0,并且flag是否为0就可以看出堆栈操作是否合法了。没做完一组数据,记得初始化数据。


    Code:

    #include <stdio.h>
    #include <string.h>
    
    int main()
    {
        int i, n, m, sum;
        char str[101] = {0};
        scanf("%d %d", &n, &m);
        while(n --) {
            int flag = 1;
            sum = 0;
            scanf("%s", str);
            for(i = 0; i < strlen(str); i ++) {
                if(str[i] == 'S') {
                    sum ++;
                    if(sum > m) {
                        flag = 0;
                        break;
                    }
                }
                else if(str[i] == 'X'){
                    sum --;
                    if(sum < 0) {
                        flag = 0;
                        break;
                    }
                }
            }
            if(flag == 0 || sum != 0) {
                printf("NO\n");
            }
            else {
                printf("YES\n");
            }
        }
    
        return 0;
    }
    展开全文
  • PTA - 堆栈操作合法性

    千次阅读 2019-05-02 08:24:32
    堆栈操作合法性 题目:假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。...

    堆栈操作合法性

    题目:假设以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>
    #include <stack>
    
    using namespace std;
    
    bool is_right(string line, int stack_max_size);   // stack_max_size:堆栈的最大容量
    
    int main()
    {
    	int n, m;       
    	cin >> n >> m;
    	cin.ignore();   // 跳过换行符  
    	                // 等同于getchar(); 
        // 输入n行字符串                
    	for (int i = 0; i < n; i++)
    	{
    		string line;
    		getline(cin, line); 
    		
    		// 调用函数 
    		if (is_right(line, m))
    			cout << "YES" << endl;
    		else
    			cout << " NO" << endl;
    	}	 
    }
    
    bool is_right(string line, int stack_max_size)
    { 
    	stack<int> INT_STACK;
    	
    	for (int i = 0; i < line.size(); i++)
    	{
    		if (line[i] == 'S')
    		{
    			// 若当前堆栈长度的大于或等于堆栈的最大容量,return false;否则,压栈 
    			if (INT_STACK.size() >= stack_max_size)
    				return false;
    			INT_STACK.push(i); 
    		}
    		else if (line[i] == 'X')
    		{
    			// 若当前堆栈为空,return false;否则,弹栈 
    			if (INT_STACK.empty())  
    				return false;
    			INT_STACK.pop();
    		}
    	}
    	return INT_STACK.empty();
    }	
    

    解法二:stack法

    #include <iostream>
    #include <stack>
    
    using namespace;
    
    int main()
    {
    	int n, m;
    	cin >> n >> m;  
    	getchar();       
    	
    	string s;
    	while (n--)
    	{
    	    stack<char> c_stack;   // 将堆栈定义在内部,可实现每轮循环字符串的清空
    		//s.clear();           // 若堆栈定义在外部,即可用s.clear()实现每轮字符串的清空 
    		getline(cin, s);
    		
    		int count = 0;   
    		for (int i = 0; i < s.size(); i++)
    		{
    			if (s[i] == 'S')  
    			{
    				c_stack.push(s[i]);   // 压栈     
    				count++; 
    				if(count > m)  
    				{
    					cout << "NO" << endl;
    					break;
    				}         
    			}
    			else if (s[i] == 'X')   
    			{
    				c_stack.pop();   // 弹栈 
    				count--;    
    				if(count < 0)
    				{
    					cout << "NO" << endl;
    					break;
    				}      
    			}
    		}
    		
    		if (c_stack.empty() && count == 0)
    			cout << "YES" << endl; 
    		else
    			cout << "NO"<< endl;
    	}
    	return 0;
     } 
    

    解法三:string法

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
    	int n, m;     //  输入4 10 
    	cin >> n >> m;
    	getchar();
    	
    	string str;
    	while (n--)
    	{
    		int count = 0;
    		str.clear();        // 清空字符串
    		getline(cin, str);  // 输入一行字符串 
    		
    		for (int i = 0; i < str.length(); i++)
    		{
    			if (str[i] == 'S' && count < m)   // S:入栈 
    				count++;
    	
    			else if (str[i] == 'X' && count > 0)   // X:出栈
    				count--;
    			
    			else
    				break; 
    		}
    		
    		if (i == str.length() && count == 0) 
    			cout << "YES" << endl;
    		else
    			cout << "NO" << endl;
    	}
    	return 0; 
    	 
    }
    

    小结

    堆栈

    一.是什么?

    1.堆栈:是一种模板容器适配器,以“先进后出”的方式访问容器内的元素。(简称:LIFO线性表)

    在这里插入图片描述

    二.定义及操作

    1.头文件

    #include <stack>
    

    2.定义

    stack <int> s;
    

    3.操作:(成员函数)【重点】

    s.push();          //  在栈顶压入新元素
    s.top();           //  返回栈顶元素
    s.pop();           //  移除栈顶元素
    s.size();          //  返回栈中元素的数目
    s.empty();         //  堆栈为空返回true
    

    在这里插入图片描述

    三.应用时机及实例

    1.应用时机

    1.1.存储一批数
    1.2.以“先进后出”的顺序访问这批数

    2.实例 【掌握】

    2.1.回文判断
    2.2.括号匹配

    四.大小比较(了解即可)

    1.两个堆栈之间的大小关系基于首对不相等元素之间的比较。
    2.如果两个堆栈具有元素数目相同对应元素具有相同的值,则两个列表相等

    展开全文
  • PTA 习题3.9 堆栈操作合法性

    千次阅读 2020-04-10 21:56:44
    习题3.9 堆栈操作合法性 题目要求: 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的...
  • 7-3 堆栈操作合法性 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请...
  • 7-1 堆栈操作合法性

    2019-03-30 17:00:49
    7-1 堆栈操作合法性 (20 分) 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作...
  • 堆栈操作合法性 我们最近在博客中发表的一篇评论带回了有关特定体验的一些回忆。 我希望我没有经历过的那种经历。 在我们创建Plumbr之前很长时间,我正在调试一个应用程序,该应用程序每次在蓝月亮时都会给我一个...
  • 堆栈操作合法性 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写...
  • 作者: DS课程组单位: 浙江大学时间限制: 400ms内存限制: 64MB代码长度限制: 16KB7-14 堆栈操作合法性(20 分)假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,...
  • 浙大数据结构PTA 习题3.9堆栈操作合法性 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法...
  • 习题3.9 堆栈操作合法性 (20分) 假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 216
精华内容 86
热门标签
关键字:

堆栈操作合法性