用栈实现括号匹配算法（超详细，超易懂）-Toy模板网

这篇具有很好参考价值的文章主要介绍了用栈实现括号匹配算法（超详细，超易懂）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先我们要明白栈是如何实现这个算法的，在实现算法的过程当中，栈的作用就是储存左括号，例如储存"[" "}" '(" 这三种左括号
在程序当中，首先遍历传入的算数组，剔除一些其他的数字，在这里只比较左右括号，然后先将左括号储存到栈当中，例如（（（（ ] ] ]，先将前面的三个（压入栈当中，将左括号压入栈当中之后，就开始遍历右括号了
在遍历到右括号的时候，因为如果左右括号是匹配的，那么肯定当遍历到一个右括号的时候，就会有一个左括号在栈顶等着（因为数学当中的括号是相互匹配的，一个最左边的右括号肯定和一个最右边的右括号相互匹配，而这个最右边的左括号又在栈的顶部），如果相互匹配，那么这个时候就是匹配成功的。
根据上面是思想，如果在遍历了传入的算术组之后，栈的元素全部取出来了，那么说明全部的右括号和左括号都是匹配的
然后我们需要注意，当我们将左括号全部压入栈中的时候，可以一开始就判断栈是否是空的，如果是空的，那么就是左括号少于右括号
如果在遍历了全部的算数组之后，栈当中还有左括号，那么就是左括号多于右括号
如果在遍历右括号的时候，发现抽出来的右括号和栈顶的左括号不匹配，那么就是左右括号匹配次序不正确

代码如下：

#include<iostream>
#include<string.h>
using namespace std;
#define ERROR -1
#define CORRECT 1
#define MAXSTACKSIZE 100
typedef struct SqStack {
	char base[MAXSTACKSIZE];
	char* top;
}SqStack;
SqStack MBStack;




//初始化栈
int InitStack(SqStack& s) {
	if (s.base == NULL)
		return ERROR;
	s.top = s.base;
	return CORRECT;
}





//将数据进栈
int Push(SqStack& s, char e) {
	if ((s.top - s.base) >= MAXSTACKSIZE)
		return ERROR;
	s.top++;
	*s.top = e;
	return CORRECT;
}




//将数据出栈
int Pop(SqStack& s, char& e) {
	if (s.top <= s.base)
		return ERROR;
	e = *s.top;
	s.top--;
	return CORRECT;

}



//判断栈是否为空
int StackEmpty(SqStack& s) {
	if (s.top <=s.base)
		return ERROR;
	return CORRECT;

}




//括号匹配
int MatchBracket(SqStack& s, char* BracketString) {
	int i;
	char C, sC;
	InitStack(s);
	for (i = 0; i < strlen(BracketString); i++) {  //先遍历整个传入的数据
		C = BracketString[i];
		if ((C == '(') || (C == '[') || (C == '{')) { 
			//先从左到右遍历，找出算数当中出现的左括号并且将左括号其压入栈当中
			Push(s, C);
		}
		else {
			if ((C == ')') || (C == ']') || (C == '}'))
			{
				//在这里表示没有任何左括号存在，即左括号少于右括号，返回-2
				if (StackEmpty(s) == ERROR) return -2;
				//这个时候的意思就是栈当中存在左括号，这时候已经遍历到一个"]","}",")"等三个右 
                //括号，然后我们想一下，当我们的算数的括号的匹配的时候，
                //那么当抽到一个右括号的时候，肯定是有一个位于栈顶的左括号存在的，然后这时候将
				//栈顶的元素取出来，进行匹配，如果两个都为一个搭配的左右括号，那么这个时候就是 
                //相互匹配的

				Pop(s, sC);  //将栈顶的左括号取出

				//下面这三个判断指的是遍历的算数符号和从栈顶取出的括号进行比对，如果不成功，那 
                //么返回-1，表示左右括号匹配次序不对
				if ((C == ')') && (sC != '(')) return -1;
				if ((C == ']') && (sC != '[')) return -1;
				if ((C == '}') && (sC != '{')) return -1;
			}
		}
	}
	//这个表示栈当中的元素不空，那么就是存在没有匹配完的左括号，也就是左括号比右括号多
	if (StackEmpty(s) != ERROR) return -3;
	//这个时候表示左右括号匹配完全正确，然后栈的元素全部匹配取出完了
	if (StackEmpty(s) == ERROR) return 0;
}




void printResult(SqStack& s, char* BracketString) {
	int result = MatchBracket(s, BracketString);
	if (result == 0) {
		cout << "匹配完全成功" << endl;
	}
	else if (result == -1) {
		cout << "左右括号匹配次序不正确" << endl;
	}
	else if (result == -2) {
		cout << "右括号多于左括号" << endl;
	}
	else {
		cout << "左括号多于右括号" << endl;
	}
}


int main() {
	int i, SampleNum;
	char BracketString[MAXSTACKSIZE];
	cin >> SampleNum;
	for (i = 0; i < SampleNum; i++) {
		cin >> BracketString;
		printResult(MBStack, BracketString);
	}
	return 0;
}

最后运行的结果如下：

如何利用栈结构实现括号匹配问题的方法,java,开发语言文章来源地址https://www.toymoban.com/news/detail-739088.html