文章目录
问题概述算法思路不匹配的情况实现流程图C语言代码结果测试问题概述
检测括号是否成对出现
最后出现的左括号最先匹配(LIFO),和栈的后进先出
异曲同工
每出现一个右括号,就抵消(出栈操作)掉一个左括号
算法思路
遇到左括号就入栈遇到有括号,就抵消一个左括号不匹配的情况
遇到一个右括号,栈内弹出的左括号与之不匹配,例如 此时的右括号是 ] 而栈内的左括号是 {匹配到最后一个括号。栈内已经空了,说明此时多出来了括号处理完所有括号,栈内非空实现流程图
C语言代码
匹配代码实现代码
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(IsEmpty(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 IsEmpty(S);}
完整代码
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <string.h>#define MaxSize 100 //定义栈中元素最大个数typedef struct{char data[MaxSize];int top;}SqStack;//初始化栈void InitStack(SqStack *S){S->top = -1;}//判断栈是否为空bool IsEmpty(SqStack S){if(S.top == -1){return true;}return false;}//新元素入栈void Push(SqStack *S,char x){if(S->top == MaxSize-1){printf("栈已满"); //栈已满return;}S->top += 1;S->data[S->top] = x;}//栈顶元素出栈,用x返回void Pop(SqStack *S,char *x){if(S->top == -1){printf("栈已满");return;}*x = S->data[S->top];S->top -= 1;}//匹配算法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(IsEmpty(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 IsEmpty(S);}int main(){char s[MaxSize];printf("请输入需要判断的括号:\n");scanf("%s",s);int len = strlen(s);printf("当前输入的括号个数为:%d\n",len);printf("--------现在开始进行判断--------\n");if(bracketCheck(s,len)){printf("匹配成功!");}else{printf("匹配失败!");}return 0;}