数据结构06——栈的应用，括号匹配

栈本身上理解起来并不难，但栈之所以应用这么广泛，是因为其先进后出的思想在计算机各个领域都有所影响，这里我们来看它的一个应用——括号匹配。
括号匹配的应用十分广泛，从Word的自动纠错，到我们更加熟悉的编译器检查语法，这些都需要用到括号匹配，那我们究竟如何判断一串字符串中的括号到底对不对呢，这里我们就需要用到栈的思想。
照例，我们先上代码

#include
#include
using namespace std;
#define MaxSize 100

//初始化，压栈，入栈
typedef struct Stack {
	int top;
	char data[MaxSize];
}Stack;

const char brackets[6] = { '(',')','{','}','[',']' };

Stack* Stack_Init()
{
	Stack* temp = new Stack;
	if (!temp)
	{
		cout << "申请内存失败" << endl;
		return NULL;
	}
	temp->top = 0;
	temp->data[temp->top] = '#';
	return temp;
}

void PrintStack(Stack* temp)
{
	int index = temp->top;
	while (index >= 0)
	{
		cout << temp->data[index] << " ";
		index--;
	}
	cout << endl;
}

void push(Stack* temp, char data)
{
	if (temp->top + 1 == MaxSize)
	{
		cout << "栈满" << endl;
		return;
	}
	temp->data[++temp->top] = data;
}

char pop(Stack* temp)
{
	if (temp->top < 0)
	{
		cout << "栈空" << endl;
		return -1;
	}
	temp->top--;
	return temp->data[temp->top + 1];
}

void clear(Stack* temp)
{
	temp->top = 0;
}

bool Matchingtest(string s)
{
	Stack* temp = Stack_Init();
	int i;
	for (i = 0; i < s.length(); i++)
	{
		if (s[i] == brackets[0] || s[i] == brackets[2] || s[i] == brackets[4])
		{
			push(temp, s[i]);
		}
		else if (s[i] == brackets[1])
		{
			if (pop(temp) == brackets[0])
				continue;
			else
				return false;
		}
		else if (s[i] == brackets[3])
		{
			if (pop(temp) == brackets[2])
				continue;
			else
				return false;
		}
		else if (s[i] == brackets[5])
		{
			if (pop(temp) == brackets[4])
				continue;
			else
				return false;
		}
		else continue;
	}
	if (pop(temp) != '#')
		return false;
	else return true;
}

void test()
{
	string str = "(he[([]li{}jdk)])";
	cout << Matchingtest(str) << endl;
}

int main()
{
	test();
	return 0;
}

代码和之前的栈的代码相比只是多了一个函数，这个函数就是我们进行括号匹配的主体。我首先讲一下括号匹配的原理，然后再分析代码。
我们可以思考一下，我们人类如何判断括号是否匹配。当然是找到第一个右括号后看离他最近的左括号是否匹配（符合先进后出的思想）。如此，我们就确定了思路：当扫描一个字符串时，遇到左括号，我们就压栈，遇到一个右括号时，我们就出栈，看出栈元素与这个右括号是否匹配。同样的，为了防止出现左右括号数量不匹配，导致之前的判断条件无效时（比如左括号多于右括号，但是所有右括号都有与其匹配的左括号，但此时我们不能说括号匹配），我们需要在遍历完字符串后检测栈是否为空栈，来判断左右括号数量是否匹配。当然，我这里为了检测方便，所以在初始化的时候，就将栈的第一个元素设置成了‘#’。
接下来我们分析代码：

const char brackets[6] = { '(',')','{','}','[',']' };

这里我为了检测方便，定义了一个放置括号的数组。
首先，我初始化了一个栈，Stack* temp = Stack_Init();，然后利用一个循环遍历整个字符串。这里，我们先检测是否有左括号出现

if (s[i] == brackets[0] || s[i] == brackets[2] || s[i] == brackets[4])
		{
			push(temp, s[i]);
		}

如果有的话就将其入栈，随后的几个分支语句都比较相似，我只讲一个

else if (s[i] == brackets[1])
		{
			if (pop(temp) == brackets[0])
				continue;
			else
				return false;
		}

我们先判断字符串元素是否为右括号，如果是，那么再判断是否与出栈元素匹配，如果匹配，则继续循环，如果不匹配，直接返回错误。

遍历完字符串后，我判断了是否为空栈

if (pop(temp) != '#')
		return false;
	else return true;

到这里，一个字符串括号检测的函数就到此为止了。