問題概述

檢測括號是否成對出現(xiàn)

最后出現(xiàn)的左括號最先匹配（LIFO），和棧的后進(jìn)先出異曲同工

每出現(xiàn)一個右括號，就抵消（出棧操作）掉一個左括號

算法思路

• 遇到左括號就入棧
• 遇到有括號，就抵消一個左括號

不匹配的情況

• 遇到一個右括號，棧內(nèi)彈出的左括號與之不匹配，例如 此時的右括號是 ] 而棧內(nèi)的左括號是 {
• 匹配到最后一個括號。棧內(nèi)已經(jīng)空了，說明此時多出來了括號
• 處理完所有括號，棧內(nèi)非空

實(shí)現(xiàn)流程圖

C語言代碼

匹配代碼實(shí)現(xiàn)代碼

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)){ //掃描到右括號，當(dāng)前棧為空，即右括號單身情況
				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 //定義棧中元素最大個數(shù)

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)){ //掃描到右括號，當(dāng)前棧為空，即右括號單身情況
				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āng)前輸入的括號個數(shù)為：%d\n",len);
	printf("--------現(xiàn)在開始進(jìn)行判斷--------\n");
	if(bracketCheck(s,len)){
		printf("匹配成功！");
	}else{
		printf("匹配失敗！");
	}
	return 0;
}

結(jié)果測試

文章來源地址http://www.zghlxwxcb.cn/news/detail-737695.html

到了這里，關(guān)于C語言詳解括號匹配問題（棧的應(yīng)用 ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！