博客

实现括号匹配算法（顺序表）

括号匹配问题

假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个函数，用来判别表达式中的括号是否正确配对，并设计一个测试主函数。

【算法思想】


在算术表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。

括号匹配共有以下4种情况：

1. 左、右括号配对次序不正确；
2. 右括号多于左括号；
3. 左括号多于右括号：
4. 左、右括号匹配正确。

具体方法如下

：顺序扫描算术表达式（表现为一个字符串），当遇到3种类型括号的左括号时，让该括号进栈。当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配，则退栈继续进行判断：若当前栈顶括号与当前扫描的括号不相同，则左、右括号配对次序不正确；若字符串当前为某种类型右括号而堆栈已空，则右括号多于左括号：字符串循环扫描结束时，若堆枝非空（即堆枝中尚有某种类型左括号），则说明左括号多于右括号；如果未出现


上述3种情况，则说明左、右括号匹配正确。


我定义了新的头文件SeqList.h,再创建C源文件文件。

实际操作如下：

①创建SeqList.h头文件

②创建结构体

#ifndef _SeqStack_H_
#define _SeqStack_H_
#include<stdio.h>
#define MaxStackSize 100 
typedef struct
{
	DataType stack[MaxStackSize];
	int top;
}SeqStack;

③创建顺序表

//初始化
void StackInitiate(SeqStack* S)//初始化顺序堆栈S
{
	S->top = 0;//初始化栈顶下标值
}

int StackNotEmpty(SeqStack S)
//判断顺序堆栈 S 非空否，非空则返回 1，否则返回 0
{
	if (S.top <= 0)return 0;
	else return 1;
}

//入栈
int StackPush(SeqStack* S, DataType x)
//把数据元素值 x 存入顺序堆栈 S 中，入栈成功则返回 1，否则返回 0
{
	if (S->top >= MaxStackSize)
	{
		printf("堆栈已满无法插入！\n");
		return 0;
	}
	else
	{
		S->stack[S->top] = x;
		S->top++;
		return 1;
	}
}

//出栈
int StackPop(SeqStack* S, DataType* d)
//取出顺序堆栈S的栈顶数据元素值由参数d带回，出栈成功则返回1，否则返回0
{
	if (S->top <= 0)
	{
		printf("堆栈已空无数据元素出栈！\n");
		return 0;
	}
	else
	{
		S->top--;
		*d = S->stack[S->top];
		return 1;
	}
}

//取栈顶数据元素
int StackTop(SeqStack S, DataType* d)
{
	if (S.top <= 0)
	{
		printf("堆栈已空！\n");
		return 0;
	}
	else
	{
		*d = S.stack[S.top - 1];
		return 1;
	}
	
}

#endif // ! _SeqStack_H_

主函数，如下：

#include<string.h>
#include<stdio.h>
#define MaxStackSize 100
typedef char DataType;
#include"SeqStack.h"

void ExpIsCorrect(char exp[], int n)
{
	SeqStack myStack;
	int i;
	char c;
	StackInitiate(&myStack);
	for (i = 0; i < n; i++)
	{
		if ((exp[i] == '(') || (exp[i] == '[') || (exp[i] == '{'))
			StackPush(&myStack, exp[i]);
		else if (exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '(')
			StackPop(&myStack, &c);
		else if (exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '(')
		{
			printf("左右括号配对次序不正确！\n");
			return;
		}
		else if (StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '[')
			StackPop(&myStack, &c);
		else if (exp[i] == ']' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '[')
		{
			printf("左右括号次序不正确！\n");
			return;
		}
		else if (StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '{')
			StackPop(&myStack, &c);
		else if (exp[i] == '}' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '{')
		{
			printf("左右括号配对次序不正确！\n");
			return;
		}
		else if (((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}')) && !StackNotEmpty(myStack))
		{
			printf("右括号多于左括号！\n");
			return;
		}
	}
	if (StackNotEmpty(myStack))
		printf("左括号多于右括号！\n");
	else
		printf("左右括号匹配正确！\n");
}
void main(void)
{
	int i,n;
	char x[MaxStackSize];
	SeqStack myStack;
	StackInitiate(&myStack);
	printf("括号匹配器\n");
	printf("输入字符串长度：\n");
	scanf_s("%d", &n);
	printf("输入字符串：\n");
	for (i = 0; i < n; i++)
	{
		scanf_s("%c", &x[i]);
	}
	 
	n = strlen(x);
	ExpIsCorrect(myStack.stack, n);
	return;
}

此方法为我的学习记录，仅供参考。