使用栈实现括号匹配

曾经终败给现在 2022-08-19 02:11 204阅读 0赞

![Center][]

#include<stdio.h>
    #include<stdlib.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100
    typedef char Elemtype;
    typedef int Staust;
    typedef struct StackNode{
    	Elemtype *top;
    	Elemtype *base;
    	int stacksize;
    }StackNode;
    Staust InitStack(StackNode &S){
    	S.base = (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE);
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    	return OK;
    }
    Staust Push(StackNode &S, Elemtype e){
    	if(S.top - S.base == S.stacksize){
    		return ERROR;
    	}
    	*S.top++ = e;
    	return OK;
    }
    
    Staust Pop(StackNode &S, Elemtype &e){
    	if(S.top == S.base){
    		return ERROR;
    	}
    	e = *--S.top;
    	return OK;
    }
    
    Staust Gettop(StackNode &S){
    	if(S.top != S.base){
    		return *(S.top - 1);
    	}
    }
    Staust Match(StackNode &S){
    	Elemtype c, a;
    	printf("请输入括号\n");
    	scanf("%c", &c);
    	fflush(stdin);
    	while(c != '#'){
    		if('(' == c || '{' == c ||  '[' == c){
    			Push(S, c);
    		}else if(')' == c){
    			if((S.top != S.base) &&  Gettop(S) == '('){
    				Pop(S, a);
    			}else{
    				return FALSE;
    			}
    		}else if('}' == c){
    			if((S.top != S.base) &&  Gettop(S) == '{'){
    				Pop(S, a);
    			}else{
    				return FALSE;
    			}
    		}else if(']' == c){
    			if((S.top != S.base) &&  Gettop(S) == '['){
    				Pop(S, a);
    			}else{
    				return FALSE;
    			}
    		}
    		printf("请输入括号\n");
    		scanf("%c", &c);
    		fflush(stdin);
    	}
    	
    	//最后判断栈是否为空，为空则匹配成功 
    	if(S.top == S.base){
    		return TRUE;
    	}else{
    		return FALSE;
    	}
    }
    int main(){
    	printf("*****括号匹配，输入#号结束输入*****\n"); 
    	StackNode S;
    	InitStack(S);
    	if(Match(S)){
    		printf("*****括号匹配成功！*****");
    	}else{
    		printf("*****括号匹配失败！*****"); 
    	} 
    	return 0;
    }

[Center]: /images/20220731/bb0e54c9f72e43b0859a0d240684aa8b.png