【数据结构】括号匹配问题

括号匹配

给定一个字符串，其中的字符只包含三种括号：花括号{ }、中括号[ ]、圆括号( )，即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法，判断该字符串是否有效，即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对，如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式，而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

这个问题可以用栈stack来解决，具体的代码如下：

#pragma once

#include<stdio.h>
#include<assert.h>
#include<string.h>



//typedef int DataType;
typedef char DataType;



#define MAX_SIZE 100

typedef struct Stack
{
	DataType _arr[MAX_SIZE];
	int _top;
}Stack;

void StackInit(Stack* s)
{
	assert(s);
	s->_top = 0;
}

int Stackempty(Stack* s)
{
	assert(s);
	return 0 == s->_top;
}

void StackPush(Stack* s, DataType data)
{
	assert(s);
	if (s->_top == MAX_SIZE)
	{
		printf("栈已经满了！\n");
	}
	s->_arr[s->_top] = data;
	s->_top++;
}
void StackPop(Stack* s)
{
	assert(s);
	if (StackEmpty(s))
	{
		printf("栈已经空了！\n");
		return;
	}
	s->_top--;

}
DataType StackTop(Stack* s)
{
	assert(s);
	return s->_arr[s->_top - 1];
}
int StackSize(Stack* s)
{
	assert(s);
	return s->_top;
}


//
void Test()
{
	Stack s;
	StackInit(&s);

	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPush(&s, 6);

	printf("size = %d\n", StackSize(&s));
	printf("top = %d\n", StackTop(&s));


	StackPop(&s);
	printf("size = %d\n", StackSize(&s));
	printf("top = %d\n", StackTop(&s));
}



////括号匹配/////
int isBracket(char ch)
{
	if (('(' == ch || ')' == ch) ||
		('[' == ch || ']' == ch) ||
		('{' == ch || '}' == ch))
		return 1;
	return 0;
}
int MatchBrackets(const char* pStr)
{
	int len = 0, i = 0;
	Stack s;
	if (NULL == pStr)
	{
		return 1;
	}
	StackInit(&s);
	len = strlen(pStr);
	for (; i < len; ++i)
	{
		if (isBracket(pStr[i]))
		{
			if ('(' == pStr[i] || '[' == pStr[i] || '{' == pStr[i])
			{
				StackPush(&s, pStr[i]);
			}
			else
			{
				if (StackEmpty(&s))
				{
					printf("右括号比左括号多！\n");
					return 0;
				}
				else
				{
					//用当前的括号和栈顶元素匹配
					char top = StackTop(&s);
					if ('(' == top && ')' == pStr[i] ||
						'[' == top && ')' == pStr[i] ||
						'{' == top && '}' == pStr[i])
				{
					StackPop(&s);
				}
			
					else
					{
						printf("左右括号次序匹配有误！\n");
						return 0;
					}

				}
			}
		}
	}
	if (!-StackEmpty(&s))
	{
		printf("左括号比右括号多！\n");
		return 0;
	}

	printf("括号匹配正确！！！\n");
	return 1;
}




void TestMatchBrackets()
{
	char a[] = "(())abc{[(])}";
	char b[] = "(()))abc{[]}";
	char c[] = "(()()abc{[]}";
	char d[] = "(())abc{[]()}";
	char e[] = "{}";
	MatchBrackets(a);
	MatchBrackets(b);
	MatchBrackets(c);
	MatchBrackets(d);
	MatchBrackets(e);


}

#include "Stack.h"
int main()
{
	TestMatchBrackets();
	system("pause");
	return 0;
}

以上是用C语言对栈和括号匹配问题的简单实现，代码结果如下：

相关阅读

Office小知识（一）——word插入各种方向和条件个数的大括

Word中插入左右上下，多个单个花括号的总结 一：左右大括号（单个） 点击插入->公式，选择“括号”->“单方括号”，在插入的括号的虚线框中

括号匹配（C++)

算法思想： 将输入的字符串遍历。 遇到左括号就压栈；遇到右括号，若栈不为空，就将栈顶的左括号取出，匹配返回一个bool值。 若直至遍历结

Blue Jeans(最大匹配问题)

Description The Genographic Project is a research partnership between IBM and The National Geographic Society that is an

括号匹配的检验

使用栈的结构检验一串输入的括号和中括号是否匹配，只有()和[]一一对应的时候，该串才算正确的串，如：([]())和[([][])]是正确的串，[(])和

给出一种物质的分子式（不带括号），求分子量。 本题中的分

#include<stdio.h> #include<string.h> void main() { double n=0;int d,i;char p[100]; printf("该物质的分子式是：");scanf("%s"