03-3.3.1 栈在括号匹配中的应用

2024-06-07 20:44

文章标签 应用括号匹配 03 3.3

本文主要是介绍03-3.3.1 栈在括号匹配中的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

引言

void test(){int a[10][10];int x = 10*(20*(1+1)-(3-2));printf("加油！奥里给！");
}

流程应该为：

遇到左括号就入栈
遇到右括号，就“消耗”一个左括号
处理完所有括号后，栈非空——左括号单身
因此写代码的时候，扫描完所有的括号后，还要检查是否栈空
如果栈非空，则匹配失败

算法实现

#define MaxSize 10
typedef struct{char data[MaxSize];int top;
}SqStack;/*
* 考试中可以直接使用栈的这些基本操作
* 但是建议要写上简短的说明接口分别是什么
*///初始化栈
void InitStack(SqStack &S)
//判断栈是否为空
bool StackEmpty(SqStack S)
//新元素入栈
bool Push(SqStack &S, char x)
//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)bool bracketCheck(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(StackEmpty(S))   //扫描到右括号，且当前栈空return false;   //匹配失败char topElem;Pop(S, topElem);    //栈顶元素出栈if(str[i] == ')' && topElem != '(')return false;if(str[i] == ']' && topElem != '[')return false;if(str[i] == '}' && topElem != '{')return false;}}return StackEmpty(S);   //检索完所有括号后，栈空说明匹配成功
}

需要注意的是，当前定义的最大长度是10，如果长度不够了怎么办？
答：可以用链栈的方式来实现，不过在考试中用顺序栈来实现更方便，所以用顺序栈就可以了

练习：去掉代码中的基本操作，把相对应的逻辑换成对数组和top指针直接的判断和操作，动手实现完整代码！
答案：

先将基本操作替换一下

//首先，初始化栈
//将栈的top指针初始化为 -1，表示栈为空
S.top = -1;//判断栈是否为空
//也就是判断top是否为 -1，如果是，表示栈空
if(S.top == -1)//新元素入栈，将元素放在top指针所指位置的下一位，并将top指针 +1
if(S.top < MaxSize - 1){S.data[++S.top] = str[i];
}else{return false;
}//栈顶元素出栈，获取top指针所指位置的元素，并将top指针 -1
if(S.top != -1){topElem = S.data[S.top--];
}else{return false;
}

最终完整代码

#include <stdbool.h>
#include <stdio.h>#define MaxSize 10typedef struct{char data[MaxSize];int top;
}SqStack;bool bracketCheck(char str[], int length){SqStack S;    //声明一个栈S.top = -1;   //初始化栈for(int i = 0; i < length; i++){if(str[i] == '(' || str[i] == '[' || str[i] == '{'){if(S.top < MaxSize - 1){S.data[++S.top] = str[i];  //扫描到左括号，入栈}else{return false;  //栈满，匹配失败}}else if(str[i] == ')' || str[i] == ']' || str[i] == '}'){if(S.top == -1)    //扫描到右括号，且当前栈空return false;  //匹配失败char topElem;if(S.top != -1){topElem = S.data[S.top--];  //栈顶元素出栈}else{return false;  //栈空，匹配失败}if((str[i] == ')' && topElem != '(') ||(str[i] == ']' && topElem != '[') ||(str[i] == '}' && topElem != '{'))return false;  //匹配失败}}return S.top == -1;  //检索完所有括号后，栈空说明匹配成功
}int main(){char str[] = "{[()]}";int length = sizeof(str) / sizeof(str[0]) - 1;bool result = bracketCheck(str, length);if(result)printf("括号都是成对的\n");elseprintf("括号不是成对的\n");return 0;
}