栈实现括号匹配

时间：2025-04-16 08:31:05

栈实现括号匹配

匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。
算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。另外,在算法的开始和结束时,栈都应该是空的.所以匹配到最后还要判断栈是否为空,若非空,则说明匹配失败.

创建一个的文件

//以下是括号匹配具体代码
void BracketMatch(const char *str,int size)
{
	Stack stack;
	char ch;
	char leftBracket;
	int i = 0;
	StackInit(&stack);


	for (i=0;i<size;i++)
	{
		ch = str[i];

		switch(ch)
		{
		case '(':
		case '[':
		case '{':
			StackPush(&stack,(DataType)ch);
			break;
		case ')':
		case ']':
		case '}':
			if (StackEmpty(&stack))
			{
				printf("右括号多\n");
				StackDestory(&stack);
				return;
			}

			leftBracket = (char)StackTop(&stack);
			StackPop(&stack);

			if (leftBracket == '(' && ch != ')')
			{
				printf("不匹配\n");
				return;
			}

			if (leftBracket == '[' && ch != ']')
			{
				printf("不匹配\n");
				return;
			}
			if (leftBracket == '{' && ch != '}')
			{
				printf("不匹配\n");
				return;
			}
		default:
			break;
		}
	}
	if (!StackEmpty(&stack))
	{
		printf("左括号多\n");
		return;
	}
	printf("匹配正常\n");
}

//以下是文件
typedef int DataType;

#define MAX_SIZE (100)

typedef struct Stack{
	
	DataType arr[MAX_SIZE];
	int top;
}Stack;

void StackInit(Stack *stack)
{
	stack->top = 0;
}

void StackDestory(Stack *stack)
{
	stack->top = 0;
}

void StackPush(Stack *stack,DataType data)
{
	assert(stack->top <MAX_SIZE);
	stack->arr[stack->top++] = data;
}


void StackPop(Stack *stack)
{
	assert(stack->top > 0);
	stack->top--;
}

DataType StackTop(const Stack *stack)
{
	assert(stack->top > 0);
	return stack->arr[stack->top-1];
}

int stackSize(Stack *stack)
{
	return stack->top;
}

int StackFull(Stack *stack)
{
	return stack->top >= MAX_SIZE;
}

int StackEmpty(Stack *stack)
{
	return stack->top <= 0;
}

//以下我们测试括号是否匹配
void TestBracket()
{
	const char *seq[]={
		"(())abc{[(])}",
		"(()))abc{[]}",
		"(()()abc{[]}",
		"(())abc{[]()}"
	};
	int i = 0;
	for (i=0;i<4;i++)
	{
		BracketMatch(seq[i],strlen(seq[i]));
	}
}


打印结果：
不匹配   
右括号多  
左括号多  
匹配正常  

//以上就是括号匹配的问题，如有问题望批评指正

相关文章