![PTA](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
#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("non"); //输出“no” flag = 0; //用来记录是否已经通过前面的否定情况给输出了 break; } } else { //“x”,先判断是否为空,在判断是否能pop; if (empty(s)) { printf("non"); //如果为空,就要输出“no”; flag = 0; //在将标记指为0; break; } else { pop(s, e); length--; //pop一个就要栈得容量-1; } } } if (flag) { //如果前面的情况都过了,只需要考虑是不是空就好了 if (empty(s)) printf("yesn"); else printf("non"); } } return 0; }
view code
7-1 堆栈操作合法性 (20 分)
假设以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
1,需要标记三种不满足的情况,每一种都用一个flag 标记,用一个字符串来存每一串字符,在通过数组的方式来循环读取每一个字符,
判断到“x”的时候要优先考虑是否为空,如果为空就需要直接输出“no”;在标记一个这个错误已经被排除了,flag = 0;
在删除元素;
2,在读取“s“的时候,要先判断一个当前栈的容量是否已经超过了最大的栈容量,如果超过了最大的栈容量,就需要输出”no“在标记这个
错误已经被排除了 flag = 0;
3,最后在已经排除了前面的两种情况下,就只需要判断当前栈是否为空就行了,
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606422.html