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("请输入需要判断的括号：
");
scanf("%s",s);
int len = strlen(s);
printf("当前输入的括号个数为：%d
",len);
printf("--------现在开始进行判断--------
");
if(bracketCheck(s,len)){
printf("匹配成功！");
}else{
printf("匹配失败！");
}
return 0;
}
