大家好，又见面了，我是你们的朋友全栈君。
例如：{}[()]、{[()]}、()[]{}这种大中小括号成对出现（位置不限）则为括号匹配，反之则不匹配，如{()[
接下来看一下实现方式
栈的定义以及相关操作
//栈的定义
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.net/129041.html原文链接：https://javaforall.net
