括号匹配问题栈c语言(c语言栈实现括号匹配)

全栈程序员站长

发布于 2022-07-28 20:55:20

2.8K0

发布于 2022-07-28 20:55:20

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

例如：{}[()]、{[()]}、()[]{}这种大中小括号成对出现（位置不限）则为括号匹配，反之则不匹配，如{()[

接下来看一下实现方式

栈的定义以及相关操作

//栈的定义
typedef struct{ 
   
	char elem[stack_size];
	int top;
}seqStack;
//栈的初始化
void initStack(seqStack *s){ 
   
	s->top=-1;
}
//判断栈空
int isEmpty(seqStack *s){ 
   
	if(s->top==-1)
		return 1;
	else
		return 0;
}
//入栈
int push(seqStack *s,char c){ 
   
	if(s->top==stack_size-1)
		return 0;
	else{ 
   
		s->top++;
		s->elem[s->top]=c;
		return 1;
	}
}
//出栈
int pop(seqStack *s,char *x){ 
   
	if(s->top==-1)
		return 0;
	else{ 
   
		*x=s->elem[s->top];
		s->top--;
		return 1;
	}

}

//获取栈顶元素
int gettop(seqStack *s,char *x){ 
   
	if(!isEmpty(s)){ 
   
		*x=s->elem[s->top];
		return 1;
	}
	else
		return 0;
}

括号处理

括号匹配的思想：依次从左至右检查字符串，若为左括号，则入栈，若遇右括号则获取栈顶元素，检查栈顶元素与当前元素是否匹配，若匹配，则栈顶元素出栈。反之，则不匹配，程序结束。 以此类推，直至检查完所有字符串。如果此时栈空则匹配，反之则不匹配。

//成对的左右括号的ASCII码相差1或者2，以此结论来判断左右括号是否成对出现
int match(char a,char b){ 
   
	if(a+1==b||a+2==b)//成对的左右括号的ASCII码相差1或者2
		return 1;
	return 0;
}

int bracketMarch(char a[]){ 
   
	seqStack s;
	char ch;
	int i;
	initStack(&s);
	for(i=0;a[i]!='\0';i++){ 
   
		switch(a[i]){ 
   
		case '{':
		case '[':
		case '(':
			push(&s,a[i]);//遇到左括号则入栈
			break;
		case '}':
		case ']':
		case ')':
			if(isEmpty(&s)){ 
   
				return 0;
			}
			else{ 
   
			gettop(&s,&ch);//遇到右括号获取栈顶元素
			if(match(ch,a[i]))//检查是否匹配
				pop(&s,&ch);//若匹配则栈顶元素出栈
			else
				return 0;
			}
		}
	}
	if(isEmpty(&s))//如果栈空，则括号是匹配的
		return 1;
	else//反之，则不匹配
		return 0;
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define stack_size 100
//有关栈的操作

//栈的定义
typedef struct{ 
   
	char elem[stack_size];
	int top;
}seqStack;
//栈的初始化
void initStack(seqStack *s){ 
   
	s->top=-1;
}
//判断栈空
int isEmpty(seqStack *s){ 
   
	if(s->top==-1)
		return 1;
	else
		return 0;
}
//入栈
int push(seqStack *s,char c){ 
   
	if(s->top==stack_size-1)
		return 0;
	else{ 
   
		s->top++;
		s->elem[s->top]=c;
		return 1;
	}
}
//出栈
int pop(seqStack *s,char *x){ 
   
	if(s->top==-1)
		return 0;
	else{ 
   
		*x=s->elem[s->top];
		s->top--;
		return 1;
	}

}

//获取栈顶元素
int gettop(seqStack *s,char *x){ 
   
	if(!isEmpty(s)){ 
   
		*x=s->elem[s->top];
		return 1;
	}
	else
		return 0;
}
int match(char a,char b){ 
   
	if(a+1==b||a+2==b)//成对的左右括号的ASCII码相差1或者2
		return 1;
	return 0;
}
int bracketMarch(char a[]){ 
   
	seqStack s;
	char ch;
	int i;
	initStack(&s);
	for(i=0;a[i]!='\0';i++){ 
   
		switch(a[i]){ 
   
		case '{':
		case '[':
		case '(':
			push(&s,a[i]);//遇到左括号则入栈
			break;
		case '}':
		case ']':
		case ')':
			if(isEmpty(&s)){ 
   
				return 0;
			}
			else{ 
   
			gettop(&s,&ch);//遇到右括号获取栈顶元素
			if(match(ch,a[i]))//检查是否匹配
				pop(&s,&ch);//若匹配则栈顶元素出栈
			else
				return 0;
			}
		}
	}
	if(isEmpty(&s))//如果栈空，则括号是匹配的
		return 1;
	else//反之，则不匹配
		return 0;
}
int main(){ 
   
	int n;
	char a[25];
	scanf("%d",&n);
	while(n--){ 
   //你想检查几个字符串是否括号匹配？
		scanf("%s",a);
		if(bracketMarch(a))
			printf("Yes\n");
		else
			printf("No\n");
	}
}

ps:如有问题欢迎留言–

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/129041.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年4月1，如有侵权请联系 cloudcommunity@tencent.com 删除

java