数据结构(7)栈的应用——括号匹配问题
2023-02-18 16:42:48 时间
栈的应用——括号匹配问题
什么是括号匹配问题
顾名思义就是把括号组起来,左小括号对右小括号,左中括号对右中括号,左大括号对右大括号,最理想的情况下是匹配成功,即例如以下的括号排列:
( { [ ] } )
和栈的关系
了解什么是括号匹配之后,再来聊聊它和栈的关系。我们知道栈的特性是后进先出,那如果我们这样:把已知的左括号压入栈中,每有一个右括号,就和栈顶元素匹配,如果匹配成功就pop出栈顶元素,这样就把括号匹配问题变为了熟悉的入栈,出栈操作。当然,这只是一个大体思路,具体操作时会有很多临界条件,这里整理出一张流程图:
具体代码实现不算难,但是昨天一直运行出问题,我把每个临界条件都打印输出出来也没找到问题,今早一看原来是入栈函数的临界条件写成了if(S,top = MaxSize-1)….,少了一个等号。
这里直接贴代码了:
- 栈的相关操作
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define MaxSize 10
//建栈
typedef struct {
char data[MaxSize];
int top;
}SqStack;
//初始化
int InitStack(SqStack &S){
S.top = -1;
return OK;
}
//入栈
int Push(SqStack &S,char c){
if(S.top == MaxSize-1){
return ERROR;//栈满
}
S.top = S.top + 1;
S.data[S.top] = c;
return OK;
}
//出栈
int Pop(SqStack &S,char *c){
if(S.top == -1){
return ERROR;
}
*c = S.data[S.top];
S.top = S.top - 1;
return OK;
}
//输出
int Print(SqStack S){
if(S.top == -1){
return ERROR;
}
for(S.top;S.top>-1;S.top--){
printf("%c\t",S.data[S.top]);
}
printf("\n");
return OK;
}
//栈空
bool Empty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
- 匹配函数
bool pipei(char str[],int length){
SqStack S;
InitStack(S);
for(int i=0;i<length;i++){
if(str[i]=='(' || str[i]=='[' || str[i]=='{')
Push(S,str[i]);
else{
if(Empty(S)){
printf("栈空,匹配失败\n");
return false;
}
char ElemTop;
Pop(S,&ElemTop);
if(str[i]==')' && ElemTop!='('){
printf("小括号匹配失败\n");
return false;
}
if(str[i]==']' && ElemTop!='['){
printf("中括号匹配失败\n");
return false;
}
if(str[i]=='}' && ElemTop!='{'){
printf("大括号匹配失败\n");
return false;
}
}
}
if(Empty(S)== true){
printf("匹配成功!!!\n");
return true;
}
if(Empty(S)== false){
printf("匹配失败,栈中还有剩余左括号单身\n");
return false;
}
}
- 主函数及运行
相关文章
- ecshop中smarty比较操作符(eq,ne,neq)含义
- 自定义UEditor右键菜单
- 在UEditor编辑器的工具栏上加一行文字
- 订单号
- 使用自定义函数实现数据编解码、格式处理与业务告警
- html_entity_decode()、空格、 乱码问题
- ecshop中{$lang.}标签的修改
- CSS max-width: 0;
- 城市消费券之地理位置攻防
- HTML表示RGB颜色的方法
- Ecshop模板中html_options用法详解
- CSS自动换行
- 解决HTML select控件 设置属性 disabled 后无法向后台传值的方法
- !DOCTYPE html文档类型声明
- 利用WMITool解决浏览器快捷方式启动参数被篡改以及浏览器主页被劫持的问题
- 关于伪静态的实现方法
- 助力领克汽车工厂智能制造 广域铭岛再度入围工信部“2022年工业互联网平台创新领航应用案例”
- css图片居中(水平居中和垂直居中)
- 如何对 Neuron 源码进行交叉编译
- LayUI之旅-入门