设为首页 加入收藏

TOP

PTA
2018-11-08 14:11:42 】 浏览:92
Tags:PTA
#include<bits/stdc++.h>
using namespace std;

#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0
#define INFEASIBLE  -1
#define OVERFLOW    -2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef int SElemType;
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
Status InitStack(SqStack &
 
			
">S) { S.
base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status GetTop(SqStack S, SElemType &e) { if (S.top == S.base) return ERROR; e = *(S.top - 1); return OK; } Status Push(SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } Status Pop(SqStack &S, char &e) { if (S.top == S.base) return ERROR; e = *--S.top; return OK; } Status Empty(SqStack &S) { if (S.top == S.base) return OK; else return ERROR; } int main() { int n, m; scanf("%d %d", &n, &m); while (n--) { string s; cin >> s; char e; int len = s.length(); SqStack S; InitStack(S); int flag = 1; int length = 0; for (int i = 0; i < len; i++) { if (s[i] == 'S') { Push(S, s[i]); length++; if (length > m) { //D第一种情况,栈得最大的容量超过m的栈得最大容量, printf("NO\n"); //输出“NO” flag = 0; //用来记录是否已经通过前面的否定情况给输出了 break; } } else { //“X”,先判断是否为空,在判断是否能POp; if (Empty(S)) { printf("NO\n"); //如果为空,就要输出“NO”; flag = 0; //在将标记指为0; break; } else { Pop(S, e); length--; //Pop一个就要栈得容量-1; } } } if (flag) { //如果前面的情况都过了,只需要考虑是不是空就好了 if (Empty(S)) printf("YES\n"); else printf("NO\n"); } } return 0; }
View Code
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

1,需要标记三种不满足的情况,每一种都用一个flag 标记,用一个字符串来存每一串字符,在通过数组的方式来循环读取每一个字符,
判断到“X”的时候要优先考虑是否为空,如果为空就需要直接输出“NO”;在标记一个这个错误已经被排除了,flag = 0;
在删除元素;
2,在读取“S“的时候,要先判断一个当前栈的容量是否已经超过了最大的栈容量,如果超过了最大的栈容量,就需要输出”NO“在标记这个
错误已经被排除了 flag = 0;
3,最后在已经排除了前面的两种情况下,就只需要判断当前栈是否为空就行了,

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇PTA-栈(括弧匹配) 下一篇[20181107][模拟赛]

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }