数据结构——栈实现括号匹配

红太狼 2022-06-17 08:43 197阅读 0赞

# 数据结构——栈实现括号匹配 #

> 真正学习之后，才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做，原来这么简单。![敲打][knock.gif]
> 
>     #include <stdio.h>
>     #include <stdlib.h>
>     #include <malloc.h>
>     #include <string.h>
>     /**栈的链式存储**/
>     typedef struct Data{
>     	char c;
>     };
>     typedef struct Stack{
>     	Data data;
>     	Stack *top;	//指向栈顶元素
>     };
>     /**初始化空栈**/
>     void InitStack(Stack *S){
>     	S->top = NULL;
>     }
>     /**判断是否为空栈**/
>     int StackEmpty(Stack S){
>     	//为空返回1否则返回0
>     	if(S.top==NULL) return 1;
>     	else return 0;
>     }
>     /**返回栈顶元素**/
>     void GetTop(Stack S,Data *d){
>     	if(StackEmpty(S)==1)
>     		printf("It's an empty stack!");
>     	else{
>     		d->c = S.top->data.c;
>     	}
>     }
>     /**向栈顶插入新元素 入栈**/
>     void PushStack(Stack *S,Data d){
>     	Stack* p = (Stack *)malloc(sizeof(Stack));
>     	p->data.c = d.c;
>     	p->top = S->top;
>     	S->top = p;
>     }
>     /**从栈顶删除元素 出栈**/
>     void PopStack(Stack *S,Data *d){
>     	if(StackEmpty(*S)==1){
>     		printf("It's an empty stack!\n");
>     	}else{
>     		Stack *p = S->top;
>     		S->top = p->top;
>     		d->c = p->data.c;
>     	}
>     }
>     /**清空栈**/
>     void ClearStack(Stack *S){
>     	if(StackEmpty(*S)==1){
>     		printf("It's already an empty stack!\n");
>     	}else{
>     		S->top = NULL;
>     	}
>     }
>     /**打印栈内信息**/
>     void PrintStack(Stack S){
>     	if(StackEmpty(S)==1){
>     		printf("It's an empty stack!\n");
>     	}else{
>     		printf("name----age\n");
>     		while(S.top!=NULL){
>     			printf("%s\n",S.top->data.c);
>     			S.top = S.top->top;
>     		}
>     	}
>     }
>     /**检查右括号与栈顶元素是否匹配**/
>     int Match(Data r,Data s){
>     	//匹配成功返回1
>     	if(r.c==')'&&s.c=='('){
>     		return 1;
>     	}else if(r.c=='}'&&s.c=='{'){
>     		return 1;
>     	}else if(r.c==']'&&s.c=='['){
>     		return 1;
>     	}else{
>     		return 0;
>     	}
>     }
>     /**括号匹配**/
>     void CheckMatch(char *m,Stack *S){
>     	Data r,s;
>     	while(*m){
>     		switch (*m){
>     		case '(':
>     		case '{':
>     		case '[':
>     			s.c = *m;
>     			PushStack(S,s);
>     			*m++;
>     			break;
>     		case ')':
>     		case '}':
>     		case ']':
>     			if(StackEmpty(*S)){
>     				printf("Location %s can't match!\n",*m);
>     				return;
>     			}
>     			GetTop(*S,&s);
>     			r.c = *m;
>     			if(Match(r,s)){
>     				PopStack(S,&s);
>     				*m++;
>     			}else{
>     				printf("Location %c can't match!\n",*m);
>     				return;
>     			}
>     		default:
>     			*m++;
>     		}
>     	}
>     	if(StackEmpty(*S)){
>     		printf("Match successfully!\n");
>     	}else{
>     		printf("Can't match!Lack of right bracket!\n");
>     	}
>     }
>     void main(){
>     	char d[12];
>     	Stack S;
>     	char *p;
>     	printf("Input your expression:");
>     	gets(d);
>     	p = d;	//指向表达式
>     	InitStack(&S);
>     	CheckMatch(p,&S);
>     	system("pause");
>     }

[knock.gif]: /images/20220617/2bee274bc1a044e38007bf714af4b683.png