|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
4. 判断堆栈操作的合法性
(1)输入说明:第一行给出两个正整数N和M,其中N是待测序列的个数,M(<=50)是栈的最大容量。随后N行,每行中给出一个仅由S和X构成的序列。序列保证不为空,且长度不超过100.
(2)输出说明:对每个序列,若该序列是合法的堆栈操作序列,在一行中输出YES,否则输出NO。
(3)测试用例:
输入 输出
4,10
SSSXXSXXSX YES
SSSXXSXXS NO
SSSSSSSSSSXSSXXXXXXXXXXX NO
SSSXXSXXX NO
说明:NO的情形包括堆栈非空、X空栈、S满栈,非法操作发生在序列中间及结尾
下面是我写的代码。
- #include<stdio.h>
- #include<stdlib.h>
- #define stack_init_size 100
- #define stackincrement 10
- typedef int selemtype;
- typedef int elemtype;
- typedef struct{
- selemtype *base;
- selemtype *top;
- int stacksize;
- }sqstack;
- typedef struct snode{
- elemtype data;
- struct snode *next;
- }snode,*linkstack;
- void initlist1(linkstack &l)//链栈入栈
- {
- elemtype e;
- int n,i;
- l=(linkstack)malloc(sizeof(snode));
- l->next=NULL;
- printf("\n请输入创建栈的长度:");
- scanf("%d",&n);
- for(i=0;i<n;i++){
- scanf("%d",&e);
- linkstack p=(snode*)malloc(sizeof(snode));
- p->data=e;
- p->next=l->next;
- l->next=p;
- }
- }
- void input(linkstack &l)//链栈输出
- {
- linkstack p=l->next;
- while(p!=NULL)
- {
- printf("%d ",p->data);
- p=p->next;
- }
- printf("\n");
- }
- void pop1(linkstack &l)//链栈出栈
- {
- int n,i;
- elemtype x;
- linkstack p;
- printf("\n请输入要出栈的个数:");
- scanf("%d",&n);
- printf("出栈的数为:");
- for(i=0;i<n;i++)
- {
- p=l->next;
- l->next=p->next;
- x=p->data;
- free(p);
- printf("%d ",x);
- }
- }
- void initstack(sqstack &s)
- {
- s.base=(selemtype*)malloc(stack_init_size*sizeof(selemtype));
- s.top=s.base;
- s.stacksize=stack_init_size;
- }
- void push(sqstack &s,selemtype e)//入栈
- {
- if(s.top-s.base>=s.stacksize){
- s.base=(selemtype*)realloc(s.base,(s.stacksize+stack_init_size)*sizeof(selemtype));
- if(!s.base)
- printf("error");
- s.top=s.base+s.stacksize;
- s.stacksize+=stack_init_size;
- }
- *s.top=e;
- s.top++;
- }
- void pop(sqstack &s)//出栈
- {
- selemtype *e=s.top-1;
- int i=0;
- if(s.base==s.top){
- printf("栈为空");
- }
- printf("%d ",*e);
- s.top--;
- }
- void gettop(sqstack &s)//取栈顶元素
- {
- if(s.top!=s.base){
- printf("\n此时栈顶元素为:");
- printf("%d\n",*(s.top-1));
- }
-
- }
- void print(sqstack &s)//输出
- {
- selemtype *e=s.base;
- int i=0;
- while(i<(s.top-s.base))
- {
- printf("%d ",*e);
- i++;
- e++;
- }
- }
- void judge(selemtype q)
- {
- int i,flag=0,a[100];
- sqstack s2;
- selemtype e,f;
- initstack(s2);
- for(i=0;i<q;i++){
- scanf("%d",&f);
- a[i]=f;
- }
- for(i=0;i<q/2;i++){
- push(s2,a[i]);
- }
- if (q % 2 == 0) {
- i = q / 2;
- } else {
- i = q / 2 + 1;
- }
- while(i<q&&flag==0)
- {
- if(*(s2.top-1)!=a[i]){
- flag=1;
- }
- s2.top--;
- i++;
- }
- if(flag==0){
- printf("是回文序列!");
- }
- else {
- printf("不是回文序列");
- }
- }
- void hefa(int N,int M)
- {
- int i,j=0;
- selemtype e=0;
- sqstack s1;
- char y,S,X;
- for(i=0;i<N;i++){
- while(j<M)
- {
- scanf("%c",&y);
- if(y=='S'){
- e=1;
- push(s1,e);
- }
- else if(y=='X'){
- if(s1.top==s1.base){
- e=0;
- }
- s1.top--;
- }
- j++;
- }
- if(e==1){
- printf("YES");
- }
- else
- {
- printf("NO");
- }
-
- }
- }
- int main()
- {
- int n,i,m,a[100],M,N;
- sqstack s,s1;
- linkstack l;
- selemtype e,q,f;
- initstack(s);
- printf("请输入进栈的数量:\n");
- scanf("%d",&n);
- printf("请输入进栈的数字:\n");
- for(i=0;i<n;i++)
- {
- scanf("%d",&e);
- push(s,e);
- }
- printf("请问你想出栈几次:\n");
- scanf("%d",&m);
- if(m>n){
- printf("error");
- }
- else
- {
- for(i=0;i<m;i++){
- pop(s);
- }
- }
- gettop(s);
- if(s.top==s.base){
- printf("栈为空。\n");
- }
- else{
- printf("栈内元素为:");
- print(s);
- }
- printf("\n请输入你想要判断是否为回文的字符序列的长度:");
- scanf("%d",&q);
- judge(q);
- initlist1(l);
- pop1(l);
- printf("\n栈内元素为:");
- input(l);
- scanf("%d,%d",&N,&M);
- hefa(N,M);
- return 0;
- }
复制代码
你的代码看起来已经很复杂了,但是我注意到你的代码并没有完全解决问题。你的代码中的\"hefa\"函数是用来判断堆栈操作的合法性的,但是它并没有正确地处理所有的情况。这个函数需要考虑的情况有:
1. 当输入为'S'时,需要将元素压入栈中。如果栈已满(即栈的大小等于M),则该操作是非法的。
2. 当输入为'X'时,需要从栈中弹出元素。如果栈为空(即没有元素可以弹出),则该操作是非法的。
你的代码没有正确地处理这些情况。你需要修改你的代码,以便正确地处理这些情况。以下是一个简化的版本的代码,它只包含了处理这个问题的部分:
- #include <stdio.h>
- #include <stdlib.h>
- void hefa(int N, int M) {
- int i, j;
- char *seq = (char*)malloc(101 * sizeof(char)); // 序列长度不超过100
- for(i = 0; i < N; i++) {
- scanf("%s", seq);
- int stackSize = 0;
- for(j = 0; seq[j] != '\\0'; j++) {
- if(seq[j] == 'S') {
- if(stackSize == M) {
- printf("NO\
- ");
- break;
- }
- stackSize++;
- } else if(seq[j] == 'X') {
- if(stackSize == 0) {
- printf("NO\
- ");
- break;
- }
- stackSize--;
- }
- }
- if(seq[j] == '\\0') {
- printf("YES\
- ");
- }
- }
- free(seq);
- }
- int main() {
- int N, M;
- scanf("%d %d", &N, &M);
- hefa(N, M);
- return 0;
- }
复制代码
这个代码首先读取N和M的值,然后对每一个序列进行检查。对于每一个序列,它首先读取序列,然后对序列中的每一个字符进行检查。如果字符是'S',它会检查栈是否已满。如果字符是'X',它会检查栈是否为空。如果在任何时候发现一个非法的操作,它会立即停止检查该序列,并输出\"NO\"。如果它成功地检查了整个序列而没有发现任何非法的操作,它会输出\"YES\"。
请注意,本回答来自GPT-4
如果问题已经解决,请设置最佳答案
|
|