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

例如:{}[()]、{[()]}、()[]{}这种大中小括号成对出现(位置不限)则为括号匹配,反之则不匹配,如{()[接下来看一下实现方式栈的定义以及相关操作//栈的定义typedefstruct{ charelem[stack_size]; inttop;}seqStack;//栈的初始化voidinitStack(seqStack*s){ s->top=-…

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

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

接下来看一下实现方式


栈的定义以及相关操作

//栈的定义
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账号...

(0)


相关推荐

  • 数据库的隔离级别

    数据库的隔离级别本文主要介绍了数据库中的隔离级别,以及其会产生的场景。

  • java图片转二进制流_java将文件转化成二进制流

    java图片转二进制流_java将文件转化成二进制流二进制流的主要编码格式是base64码。可以在网上找一些在线转base64编码的网站进行尝试转换。例如:http://imgbase64.duoshitong.com/然后通过前端展现和下载。一、前端查看、下载功能实现前端显示二进制流图片(src中放置base64码及二进制流)<imgsrc=”http://dl.ppt123.net/pptbj/201603/2016030410235232.jpg”alt=””><imgsrc=”data:image/png;base

    2022年10月12日
  • OpenCV学习笔记(30)KAZE 算法原理与源码分析(四)KAZE特征的性能分析与比较

    OpenCV学习笔记(30)KAZE 算法原理与源码分析(四)KAZE特征的性能分析与比较KAZE系列笔记:1. OpenCV学习笔记(27)KAZE算法原理与源码分析(一)非线性扩散滤波2. OpenCV学习笔记(28)KAZE算法原理与源码分析(二)非线性尺度空间构建3. OpenCV学习笔记(29)KAZE算法原理与源码分析(三)特征检测与描述4. OpenCV学习笔记(30)KAZE算法原理与源码分析(四)KAZE特征的性能分析与比较5. OpenCV学习笔记

  • awk 数组排序多种实现方法「建议收藏」

    awk 数组排序多种实现方法「建议收藏」由于awk数组,是关联数组。for…in循环输出时候,默认打印出来是无序数组。 [chengmo@localhost~]$awk’BEGIN{info=”thisisatest”;split(info,tA,””);for(kintA){printk,tA[k];}}’4test1this2is3a 如果需要按照顺序输出,通过

  • 项目分层和解析

    DAO层,Service层,Controller层、View层http://hovertree.com/hvtart/bjae/sko15s3g.htm推荐:http://www.cnblogs.

    2021年12月25日
  • 数据库:实体关系图(ER图)「建议收藏」

    数据库:实体关系图(ER图)「建议收藏」1,组成元素元素 描述 表示形似 实体 客观存在并可以相互区别的事物 用矩形框,矩形框内写明实体名 属性 实体所具有的一个属性 用椭圆型表示,并用无向边将其与相应的实体连接起来 关系 实体和实体之间以及实体内部的关系 用菱形表示,菱形框内写明联系名,并用无向边分别与有关实体连接起来, 同时在无向边旁边标上联系的类型 2,关系详解一,一对一一对一关系是指对于实体集A与实体集B,A中的每一个实体至多与B中

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号