PTA 堆栈操作合法性(20 分)

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

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

输入格式:

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

输出格式:

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

输入样例:

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例:

YES
NO
NO
NO
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#define EXP_STACK 50
#define ERROR -1
#define OK 1
using namespace std;
typedef int Elemtype;
typedef int Status;
const int maxn = 1010;
int STACK_SIZE;
typedef struct
{
    Elemtype *base;
    Elemtype *top;
    int sta_len;
    int ElemNumber;
}Stack;
Status InitStack(Stack &Sta)
{
    Sta.base = (Elemtype *)malloc(STACK_SIZE*sizeof(Elemtype));
    if(!Sta.base) return -1;
    Sta.top = Sta.base;
    Sta.sta_len = STACK_SIZE;
    Sta.ElemNumber = 0;
}
Status GetTop(Stack sta,Elemtype &e)
{
    if(sta.top==sta.base) return ERROR;
    e = *(sta.top-1);
    return OK;
}
Status Push(Stack &S,Elemtype e)
{
    if(S.top-S.base>=S.sta_len)
    {
        S.base = (Elemtype *)realloc(S.base,(EXP_STACK+S.sta_len)*sizeof(Elemtype));
        S.sta_len+=EXP_STACK;
    }
    *S.top++ = e;
    S.ElemNumber+=1;
    return OK;
}
Status Pop(Stack &S)
{
    if(S.top==S.base) return ERROR;
    --S.top;
    S.ElemNumber--;
    return OK;
}
int main()
{
    int cases;
    int Len;
    scanf("%d%d",&cases,&Len);
    STACK_SIZE = Len;
    while(cases--)
    {
        char opr[110];
        scanf("%s",opr);
        int len = strlen(opr);
        Stack Sta;
        InitStack(Sta);
        //cout<<Sta.sta_len<<" "<<Sta.ElemNumber<<endl;
        bool Fits = true;
        for(int i = 0;i<len;i++)
        {
            if(opr[i]=='S')
            {
                if(Sta.ElemNumber==Len)
                {
                    Fits = false;
                    break;
                }
                Push(Sta,1);
            }
            else if(opr[i]=='X')
            {
                int Ans = Pop(Sta);
                if(Ans==-1)
                {
                    Fits = false;
                    break;
                }
            }
        }
        if(Sta.ElemNumber) Fits = false;
        if(Fits)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素

题目:以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素: (1)该元素比放在它前面的所有元素都大; (2)该元素比放在它后面的所...

1081
来自专栏书山有路勤为径

词语模式_哈希表

已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应...

734
来自专栏数据结构与算法

求细胞个数

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列  4  10 02...

2638
来自专栏http://www.cnblogs.com

python3 re模块

一.常用正则表达式符号和语法: '.' 匹配所有字符串,除\n以外 ‘-’ 表示范围[0-9] '*' 匹配前面的子表达式零次或多次。要匹配 * 字符,请使用 ...

37512
来自专栏技术专栏

Python3入门与实践(一): 基本类型整理

1083
来自专栏北京马哥教育

Python Re 模块最全解读: 11703 字帮你彻底掌握

re模块下的函数 compile(pattern):创建模式对象 import re pat=re.compile('A') m=pat.search('CBA...

32010
来自专栏机器学习算法全栈工程师

动态规划系列之最长递增子序列问题解答

今天和大家分享的是动态规划经典问题:最长递增子序列问题解答。(似乎BAT等各大公司都喜欢在面试的时候对动态规划系列经典问题进行笔试。 题目描述: 给定一个整数序...

2937
来自专栏武培轩的专栏

剑指Offer-数组中重复的数字

package Array; /** * 数组中重复的数字 *在一个长度为n的数组里的所有数字都在0到n-1的范围内。 * 数组中某些数字是重复的,但不...

2854
来自专栏xingoo, 一个梦想做发明家的程序员

最长公共子序列

最长公共子序列问题:给定两个序列X={x1,x2,....xm},    Y={y1,y2,yn},找出XY的最长公共子序列 1 最长公共子序列结构   1 x...

16710
来自专栏数据结构与算法

P1739 表达式括号匹配

题目描述 假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是...

3058

扫码关注云+社区