题目

习题3.9 栈操作的合法性 - 浙大版《数据结构（第2版）》题目集

思路

使用堆栈结构，按照输入的字符顺序进行出入栈操作。

注：m是堆栈的容量上限，不是可以读入的字符数上限

代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
typedef struct Stack{
    char ch[200];
    int top;
}Stack,*PtrStack;
PtrStack Init(){
    PtrStack S=(PtrStack)malloc(sizeof(Stack));
    S->top=-1;
    strcpy(S->ch,"");
    return S;
}
bool isFull(PtrStack S,int m){
    if(S->top>=m-1){
        return true;
    }else{
        return false;
    }
} 
bool isEmpty(PtrStack S){
    if(S->top==-1){
        return true;
    }else{
        return false;
    }
}
void Push(PtrStack S,char c){
    S->top++;
    S->ch[S->top]=c;
}
char Pop(PtrStack S){
    if(isEmpty(S)){
        return '\0';
    }else{
        char c=S->ch[S->top];
        S->ch[S->top]='\0';
        S->top--;
        return c;
    }
}
void clean(PtrStack S){
    memset(S->ch,'\0',200);
    S->top=-1;
}
int main(){
    PtrStack S=Init();
    int n,m;
    bool flag;
    char ch,out,tch[200],t;
    scanf("%d %d",&n,&m);
    getchar();
    int k=0;
    for(int i=0;i<n;i++){
        flag=false;
        int k=0;
        memset(tch,'\0',200);
        while((t=getchar())!='\n'&&t!=EOF){
            tch[k]=t;
            k++;
        }
        //printf("%s\n",tch);
        tch[k]='\0';
        k=0;
        while(tch[k]!='\0'){
            ch=tch[k];
            if(ch=='X'){
                out=Pop(S);
                if(out=='\0'){
                    flag=true;
                    break;
                }
            }else if(ch=='S'){
                if(isFull(S,m)){
                    flag=true;
                    break;
                }
                Push(S,ch);
            }
            k++;
        }
        if(flag){
            printf("NO");
        }else{
            if(isEmpty(S)){
                printf("YES");
            }else{
                printf("NO");
            }
        }
        printf("\n");
        clean(S);
    }
}

最终好结局