栈的应用-括号匹配的检验 1、算法描述 在括号匹配算法中定义int flag = 1变量来标记匹配结果是成功还是失败！ 2、具体代码如下 —————————————————————————————————————————————————— //括号匹配算法 #include<stdio.h> #include<stdlib.h> //malloc函数的头文件 #define MaxSize 20 #include using namespace std; #define OK 1; #define ERROR 0; //结构体定义 typedef struct{ char *data; //存储空间的基地址 int top; //栈顶指针记录下标 }SqStack; —————————————————————————————————————————————————— //初始化栈 void InitStack(SqStack &s){ s.data = (char *) malloc(sizeof(char)*MaxSize); s.top = -1; } —————————————————————————————————————————————————— //判断栈是否为空 int SqStackIsEmpty(SqStack s) { if (s.top == -1) return OK; //栈空 return ERROR; //栈不为空 } —————————————————————————————————————————————————— //入栈操作 void Push(SqStack &s,char c){ if(s.top == MaxSize – 1) //栈满 printf(“栈满！ ”); s.top = s.top + 1; s.data[s.top] = c; } —————————————————————————————————————————————————— //出栈操作 void Pop(SqStack &s, char &c){ if(SqStackIsEmpty(s)) printf(“栈空！ ”); c = s.data[s.top]; s.top = s.top – 1; } —————————————————————————————————————————————————— //括号匹配函数 void bracketCheck(char str[], int length){ SqStack s; InitStack(s); int flag = 1; //标志是否匹配成功 for(int i = 0; i<length;i++){ if(str[i] == ‘(’ || str[i] == ‘[’ || str[i] == ‘{’){ Push(s,str[i]); //从左到右扫描，遇见左括号就执行入栈操作 } else if(str[i] == ‘)’ || str[i] == ‘]’ || str[i] == ‘}’){ //遇见右括号判断栈中符号 if(!SqStackIsEmpty(s)) { char topElem; Pop(s,topElem); if(str[i] == ‘)’ && topElem != ‘(’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } if(str[i] == ‘]’ && topElem != ‘[’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } if(str[i] == ‘}’ && topElem != ‘{’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } } else { printf(“ 匹配失败，第 %d 个是单身右括号 %c ”,i+1,str[i]); //栈空，存在单身右括号 flag = 0; } } } if(SqStackIsEmpty(s) && flag == 1){ printf(“ 匹配成功!!! ”); } else printf(“ 匹配失败!!! ”); } —————————————————————————————————————————————————— //主函数 int main(){ char str[MaxSize] = “0”; //字符数组初始化0 //puts(str); printf(“请输入您要判断的表达式: ”); gets(str); printf(“ ”); bracketCheck(str,MaxSize); } —————————————————————————————————————————————————— 3、核心代码 —————————————————————————————————————————————————— //括号匹配函数 void bracketCheck(char str[], int length){ SqStack s; InitStack(s); int flag = 1; //标志是否匹配成功 for(int i = 0; i<length;i++){ if(str[i] == ‘(’ || str[i] == ‘[’ || str[i] == ‘{’){ Push(s,str[i]); //从左到右扫描，遇见左括号就执行入栈操作 } else if(str[i] == ‘)’ || str[i] == ‘]’ || str[i] == ‘}’){ //遇见右括号判断栈中符号 if(!SqStackIsEmpty(s)) { char topElem; Pop(s,topElem); if(str[i] == ‘)’ && topElem != ‘(’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } if(str[i] == ‘]’ && topElem != ‘[’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } if(str[i] == ‘}’ && topElem != ‘{’){ flag = 0; printf(“匹配失败，第 %d 个右括号 %c 与栈顶符号 %c 不匹配 ”,i+1,str[i],topElem); } } else { printf(“ 匹配失败，第 %d 个是单身右括号 %c ”,i+1,str[i]); //栈空，存在单身右括号 flag = 0; } } } if(SqStackIsEmpty(s) && flag == 1){ printf(“ 匹配成功!!! ”); } else printf(“ 匹配失败!!! ”); } —————————————————————————————————————————————————— 4、代码演示 
5、算法分析 此算法从头到尾扫描整个算式表达式中的每一个字符，若算式表达式的字符串长度是n，该算法的时间复杂度为O（n）。算法在运行时所占用的辅助空间主要取决于OPTR栈和OPAD栈的大小，显然他们的空间大小之和不会超过n，所以该算法的空间复杂度也是O（n）
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/81842.html
