大家好,又见面了,我是你们的朋友全栈君。
例如:{}[()]、{[()]}、()[]{}这种大中小括号成对出现(位置不限)则为括号匹配,反之则不匹配,如{()[
接下来看一下实现方式
栈的定义以及相关操作
//栈的定义
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:如有问题欢迎留言–
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/129041.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...