数据结构（四）：栈的应用——括号匹配

一、算法图解

二、匹配函数

（函数的编写完全与图示相同）

bool bracketCheck(char* ch, int length)
{
	SqStack S;
	InitStack(S);
	for (int i = 0; i < length; i++)
	{
		if (ch[i] == '(' || ch[i] == '[' || ch[i] == '{')
			Push(S, ch[i]);
		else
		{
			if (StackEmpty(S))
				return false;
			elemtype topelem;
			Pop(S, topelem);
			if (ch[i] == '(' && topelem != ')')
				return false;
			if (ch[i] == '[' && topelem != ']')
				return false;
			if (ch[i] == '{' && topelem != '}')
				return false;
		}
	}
	return StackEmpty(S);
}

三、全部代码

输入样例：([[]]{}())(){}[{}{}()][(){}]({}{}[])

#include 
using namespace std;
#define  MaxSize 40
#define elemtype char

typedef struct
{
	elemtype data[MaxSize];
	int top;
} SqStack;

//初始化
void InitStack(SqStack& S)
{
	S.top = -1;
}

//栈判空
bool StackEmpty(SqStack S)
{
	if (S.top == -1)
		return true;
	else
		return false;
}

//进栈
bool Push(SqStack& S, elemtype x)
{
	if (S.top == MaxSize - 1)
		return false;
	S.data[++S.top] = x;
	return true;
}

//出栈
bool Pop(SqStack& S, elemtype& x)
{
	if (S.top == -1)
		return false;
	x = S.data[S.top--];
	return true;
}

//读取栈顶元素
bool GetTop(SqStack& S, elemtype& x)
{
	if (S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
}

//*****匹配函数（主要函数）*******
bool bracketCheck(char* ch, int length)
{
	SqStack S;
	InitStack(S);
	for (int i = 0; i < length; i++)
	{
		if (ch[i] == '(' || ch[i] == '[' || ch[i] == '{')
			Push(S, ch[i]);
		else
		{
			if (StackEmpty(S))
				return false;
			elemtype topelem;
			Pop(S, topelem);
			if (ch[i] == '(' && topelem != ')')
				return false;
			if (ch[i] == '[' && topelem != ']')
				return false;
			if (ch[i] == '{' && topelem != '}')
				return false;
		}
	}
	return StackEmpty(S);
}

int main()
{
	char ch[MaxSize];
	cin >> ch; //输入样例：([[]]{}())(){}[{}{}()][(){}]({}{}[])
	const bool flag = bracketCheck(ch, strlen(ch));
	cout << "匹配结果：" << flag << endl;
}